Sample space for following problem is S4. And the probability $p(\sigma)$ of a permutation is $\alpha$ times the number of inversions of $\sigma$ for suitable $\alpha$. We have to find the value of $\alpha$.

b) Expected value of $X$ in this probability space where $X(\sigma)$ is number of inversions of $\sigma$.

My try: This is the second part of the question. I found for the first part that total number of inversions that appear in the elements of $S_n$ are $(n!n(n-1))/4$

Therefore, for $n=4$ the total inversions will be $72$.

As there are $4$ elements in $S4$, there will be $4!= 24$ different ways and that will lead to $\frac{1}{24}$ probability for each case.


Your count of the total number of inversions is right. There are $\binom n2$ pairs of elements that can be inverted, each of them is inverted in half of all permutations, and there are $n!$ permutations, for a total of $\frac14n!n(n-1)$.

Given that $p(\sigma)=\frac{\def\inv{\operatorname{inv}}\inv\sigma}{\sum_\sigma\inv\sigma}$, we have

$$ E[\inv\sigma]=\frac{\sum_\sigma(\inv\sigma)^2}{\sum_\sigma\inv\sigma}\;, $$

so we need the sum of the squares of the inversion counts, which is the total number of ordered pairs of inversions in all permutations. There are three types of ordered pairs, with $0$, $1$ or $2$ elements coinciding.

For $2$ elements to coincide, the inversions must be the same, so this contribution is simply $\sum_\sigma\inv\sigma$.

If $1$ element coincides, there are three elements, and two pairs must be inverted. If the shared element is in the middle, $1$ of $6$ orders inverts both pairs (the inverted one), whereas if the shared element is the least or the greatest, then $2$ of $6$ orders invert both pairs (the ones where the shared element is the greatest or the least, respectively). There are $\binom n3$ ways to pick three elements, $2$ ordered pairs with the middle element shared and $4$ ordered pairs with one of the other elements shared, for a contribution of

$$ n!\binom n3\left(\frac16\cdot2+\frac26\cdot4\right)=\frac5{18}n!n(n-1)(n-2)\;. $$

If no elements coincide, there are $\binom42\binom n4$ ways to pick the elements, and the inversions are independent so both pairs are inverted in $1$ of $4$ orders, for a contribution of

$$ \frac{n!}4\binom42\binom n4=\frac1{16}n!n(n-1)(n-2)(n-3)\;. $$

Thus in total we have

\begin{align} \sum_\sigma(\inv\sigma)^2 &= n!n(n-1)\left(\frac14+\frac5{18}(n-2)+\frac1{16}(n-2)(n-3)\right) \\ &=\frac1{144}n!n(n-1)(9n^2-5n+10)\;, \end{align}

and dividing by $\sum_\sigma\inv\sigma$ yields

$$ E[\inv\sigma]=\frac{9n^2-5n+10}{36}\;. $$

For $n=4$, this is

$$ \frac{9\cdot4^2-5\cdot4+10}{36}=\frac{67}{18}\;. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.