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
The problem may seem mind boggling at first, when you will even try to do it for , instead of
.
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.
is sort of a cycle right?
Now, the symmetry argument starts from this symmetric figure.
We will do the problem for general .
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 times.
By the symmetry argument, every edge [], will occur
times.
Thus, when we sum over all such permutations, we get the following
Now, there are permutations in total. So, to take the average, we divide by
to get
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
The problem may seem mind boggling at first, when you will even try to do it for , instead of
.
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.
is sort of a cycle right?
Now, the symmetry argument starts from this symmetric figure.
We will do the problem for general .
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 times.
By the symmetry argument, every edge [], will occur
times.
Thus, when we sum over all such permutations, we get the following
Now, there are permutations in total. So, to take the average, we divide by
to get
One of the readers, Vishal Routh has shared his solution using Conditional Expectation, I am sharing his solution in picture format.