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

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.

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\).

- Permutation and Combination
- Symmetry Argument in Counting

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?

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.

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} $$

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

Cheenta is a knowledge partner of Aditya Birla Education Academy

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIALAcademic Programs

Free Resources

Why Cheenta?

Online Live Classroom Programs

Online Self Paced Programs [*New]

Past Papers

More