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\).
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 number corresponding to the above questions are the following:
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.
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\).
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 number corresponding to the above questions are the following:
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.
