Get inspired by the success stories of our students in IIT JAM MS, ISI  MStat, CMI MSc DS.  Learn More 

Cycles, Symmetry, and Counting | ISI MStat 2016 PSB | Problem 2

This problem is a beautiful and elegant application of basic counting principles, symmetry and double counting principles in combinatorics. This is Problem 2 from ISI MStat 2016 PSB.

Problem

Determine the average value of

    \[i_{1} i_{2}+i_{2} i_{3}+\cdots+i_{9} i_{10}+i_{10} i_{1}\]

taken over all permutations i_{1}, i_{2}, \ldots, i_{10} of 1,2, \ldots, 10.

Prerequisites

Solution

The problem may seem mind boggling at first, when you will even try to do it for n = 4, instead of n = 10.

But, in mathematics, symmetry is really intriguing. Let's see how a symmetry argument holds here. It is just by starting to count. Let's see this problem in a geometrical manner.

i_{1}\to i_{2} \to i_{3} \to \cdots \to i_{9} \to i_{10} \to i_{1} is sort of a cycle right?

A hexagon
n = 6

Now, the symmetry argument starts from this symmetric figure.

We will do the problem for general n.

Central Idea: Let's fix a pair say [ 4 - 5 ], we will see in all the permutations, in how many times, [ 4 - 5 ] can occur.

We will see that there is nothing particular about [ 4 - 5 ], and this is the symmetry argument. Therefore, the number is symmetric along with all such pairs.

Observe, along every such cycle containing [ 4 - 5 ], there are three parameters:

  • The position of the [ 4 - 5 ] in which edge of the cycle?
  • The permutation of that [ 4 - 5 ], as [ 4 - 5 ] or [ 5 - 4 ].
  • The number of arrangements of the remaining n - 2 numbers.

The number corresponding to the above questions are the following:

  • n options of position of edge since, there are n edges.
  • 2! = 2 ways of arranging.
  • (n-2)! ways of arranging the rest of the n -2 numbers.
Basic Counting Principle in a Hexagon

So, in total [ 4 - 5 ] edge will occur n \times 2! \times (n-2)! times.

By the symmetry argument, every edge [i  - j], will occur n \times 2! \times (n-2)! times.

Thus, when we sum over all such permutations, we get the following

    \[\sum_{i, j = 1; i \neq j}^{n} {ij} \times \text{number of times [i - j] pair occur}\]

    \[= \sum_{i, j = 1; i \neq j}^{n} {ij} \times n \times 2! \times (n-2)!  = n \times (n-2)! \times  \sum_{i, j = 1; i \neq j}^{n} {2ij}\]

Now, there are n! permutations in total. So, to take the average, we divide by n! to get

    \[\frac{\sum_{i, j = 1; i \neq j}^{n} {2ij}}{n-1}\]

    \[= \frac{(\sum_{i}^{n} i)^2 - \sum_{i}^{n} i^2 }{n-1}\]

    \[= \frac{\frac{n^2(n+1)^2}{4} -  \frac{n(n+1)(2n+1)}{6}}{n-1} = \frac{n(n+1)(3n+2)}{12}\]

Edit 1:

One of the readers, Vishal Routh has shared his solution using Conditional Expectation, I am sharing his solution in picture format.

Video Solution:

This problem is a beautiful and elegant application of basic counting principles, symmetry and double counting principles in combinatorics. This is Problem 2 from ISI MStat 2016 PSB.

Problem

Determine the average value of

    \[i_{1} i_{2}+i_{2} i_{3}+\cdots+i_{9} i_{10}+i_{10} i_{1}\]

taken over all permutations i_{1}, i_{2}, \ldots, i_{10} of 1,2, \ldots, 10.

Prerequisites

Solution

The problem may seem mind boggling at first, when you will even try to do it for n = 4, instead of n = 10.

But, in mathematics, symmetry is really intriguing. Let's see how a symmetry argument holds here. It is just by starting to count. Let's see this problem in a geometrical manner.

i_{1}\to i_{2} \to i_{3} \to \cdots \to i_{9} \to i_{10} \to i_{1} is sort of a cycle right?

A hexagon
n = 6

Now, the symmetry argument starts from this symmetric figure.

We will do the problem for general n.

Central Idea: Let's fix a pair say [ 4 - 5 ], we will see in all the permutations, in how many times, [ 4 - 5 ] can occur.

We will see that there is nothing particular about [ 4 - 5 ], and this is the symmetry argument. Therefore, the number is symmetric along with all such pairs.

Observe, along every such cycle containing [ 4 - 5 ], there are three parameters:

  • The position of the [ 4 - 5 ] in which edge of the cycle?
  • The permutation of that [ 4 - 5 ], as [ 4 - 5 ] or [ 5 - 4 ].
  • The number of arrangements of the remaining n - 2 numbers.

The number corresponding to the above questions are the following:

  • n options of position of edge since, there are n edges.
  • 2! = 2 ways of arranging.
  • (n-2)! ways of arranging the rest of the n -2 numbers.
Basic Counting Principle in a Hexagon

So, in total [ 4 - 5 ] edge will occur n \times 2! \times (n-2)! times.

By the symmetry argument, every edge [i  - j], will occur n \times 2! \times (n-2)! times.

Thus, when we sum over all such permutations, we get the following

    \[\sum_{i, j = 1; i \neq j}^{n} {ij} \times \text{number of times [i - j] pair occur}\]

    \[= \sum_{i, j = 1; i \neq j}^{n} {ij} \times n \times 2! \times (n-2)!  = n \times (n-2)! \times  \sum_{i, j = 1; i \neq j}^{n} {2ij}\]

Now, there are n! permutations in total. So, to take the average, we divide by n! to get

    \[\frac{\sum_{i, j = 1; i \neq j}^{n} {2ij}}{n-1}\]

    \[= \frac{(\sum_{i}^{n} i)^2 - \sum_{i}^{n} i^2 }{n-1}\]

    \[= \frac{\frac{n^2(n+1)^2}{4} -  \frac{n(n+1)(2n+1)}{6}}{n-1} = \frac{n(n+1)(3n+2)}{12}\]

Edit 1:

One of the readers, Vishal Routh has shared his solution using Conditional Expectation, I am sharing his solution in picture format.

Video Solution:

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
Menu
Trial
Whatsapp
rockethighlight