For a permutation $\pi$ of $\{1,2,3,\ldots,n\}$, let $\text{Inv}(\pi)$ be the number of pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) > \pi(j)$. Given $n$, what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$? Given $n$, what is $\sum \left(\text{Inv}(\pi)\right)^2$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$? Brian Hamrick.
Problem
Source: ELMO Shortlist 2010, C1
Tags: function, probability, expected value, combinatorics, combinatorics solved, Summation, permutations
06.07.2012 19:26
(a) The sum is \[\frac{n(n - 1)}{4} \cdot n!.\] (This is sequence A001809 in the OEIS. There is a nice counting argument there.) (b) After a tedious calculation using the generating function for inversions, I have found that the sum is \[\frac{n(n - 1)(9n^2 - 5n + 10)}{144} \cdot n!.\] I suspect there is a nice counting argument for this part as well.
06.07.2012 20:08
Yes. $\textrm{Inv}(\pi)^2$ is the number of ordered pairs of inversions of $\pi$. Let's compute the expected value $E(\textrm{Inv}(\pi)^2)$. For any two values $i < j$, the pair $((i, j), (i, j))$ is an counted half the time, so we have expected contribution $\frac{1}{2} \cdot \binom{n}{2}$. (This is essentially the counting argument you mention for part (a).) For any three values $i < j < k$, we have that the pairs $((i, j), (i, k))$, $((i, k), (i, j))$, $((i, k), (j, k))$ and $((j, k), (i, k))$ are each counted one third of the time and the pairs $((i, j), (j, k))$ and $((j, k), (i, j))$ are counted one sixth of the time, so the expected contribution here is $\left( \frac{4}{3} + \frac{2}{6}\right) \binom{n}{3}$. For four values $i, j, k, \ell$ such that $i < j$ and $k < \ell$, the pair $((i, j), (k, \ell))$ is counted one quarter of the time, for an expected contribution of $\frac{1}{4} \binom{n}{2;2;n - 4}$. Finally, everything counted in $E(\textrm{Inv}(\pi)^2)$ is of one of these forms. Adding up, the expected number of ordered pairs of inversions is exactly $\frac{n(n - 1)(9n^2 - 5n + 10)}{144}$, as claimed.
20.05.2019 20:09
14.06.2019 21:50
Can someone explain how JBL gets: JBL wrote wrote: For any two values $i < j$, the pair $((i, j), (i, j))$ is an counted half the time.
20.09.2019 05:40
19.10.2021 10:18
For a) define $\text{Inv'}(\pi)$ as the number of pairs pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) < \pi(j)$. Now, $\sum \text{Inv}(\pi)=\sum \text{Inv'}(\pi)$, since we can create a bijection by changing $\pi(i)$ and $\pi(n-i)$. Further, $$2\sum \text{Inv}(\pi)=\sum \text{Inv}(\pi)+\sum \text{Inv'}(\pi)=\binom{n}{2} n!$$since it is the sum of all pairs $(i, j)$ ($i\neq j$) over all permutations $\pi$. Thus $$\sum \text{Inv}(\pi)=\frac{n(n-1)}{4}n!$$
06.12.2021 10:10
To find $\sum \text{Inv}(\pi_n)$, we can count the number of times each pair $(i, j)$ is inverted across all permutations $\pi_n$. By symmetry, this is just $$\binom{n}{2} \cdot \frac{n!}{2} = \frac{n! \cdot n \cdot (n - 1)}{4}.$$ To find $\sum (\text{Inv}(\pi_n))^2$, we can count the number of ordered pairs of not necessarily distinct inverted pairs across all permutations $\pi_n$. Instead of considering each individual permutation, we will perform casework on the number of overlapping elements between a pair of inverted pairs and use symmetry to consider all possible permutations $\pi_n$. If our two inverted pairs share two elements, i.e. the are the same pair, then there are $\sum \text{Inv}(\pi_n)$ possible ordered pairs across all permutations. If our two inverted pairs share one element, then there are three cases: The two pairs are $(a_1, a_3)$ and $(a_2, a_3)$, where $a_1, a_2 < a_3$. The two pairs are $(a_1, a_2)$ and $(a_2, a_3)$, where $a_1 < a_2 < a_3$. The two pairs are $(a_1, a_2)$ and $(a_1, a_3)$, where $a_1 < a_2, a_3$. Now, basic constructive counting and symmetry gives $$2 \left( \binom{n}{3} \cdot 2 \binom{n}{3} \cdot (n - 3)! \right) + 2 \left( \binom{n}{3}^2 \cdot (n - 3)! \right) + 2 \left( \binom{n}{3} \cdot 2 \binom{n}{3} \cdot (n - 3)! \right)$$$$= 10 \binom{n}{3}^2 \cdot (n - 3)!$$possible ordered pairs across all permutations for this case. If our two inverted pairs are disjoint, then there are clearly $$\binom{n}{2}^2 \cdot \sum \text{Inv}(\pi_{n - 2}) = \frac{\binom{n}{2}^2 \binom{n - 2}{2} \cdot (n - 2)!}{2}$$possible ordered pairs across all permutations. Now, some non-trivial simplification yields $$\sum (\text{Inv}(\pi_n))^2 = \frac{n! \cdot n \cdot (n - 1) \cdot (9n^2 - 5n + 10)}{144}$$which finishes. $\blacksquare$ Remark: The crux of this problem is determining how we can interpret $\sum (\text{Inv}(\pi_n))^2$ from a combinatorial standpoint. Also, I wasted $40$ minutes repeatedly miscomputing my final answer for $\sum (\text{Inv}(\pi_n))^2$... .
07.12.2021 18:56
$(a)$ Number of $(i,j)$ satisfying the desired condition is $\binom{n}{2}(n-2)!$ and there are $\binom{n}{2}$ different $(i,j)$ which implies $\sum \text{Inv}(\pi)=\frac{n(n-1)}{4}\cdot n!$. $(b)$ $A_n$ is the sum for $n$. $$A_n=\sum_{\pi(n)=n} (\text{Inv}(\pi)_{\{1,2,...,n-1\}})^2+\sum_{\pi(n)=n-1} (\text{Inv}(\pi)_{\{1,2,...,n-1\}} +1)^2+...+\sum_{\pi(n)=1} (\text{Inv}(\pi)_{\{1,2,...,n-1\}} +n-1)^2$$$$=nA_{n-1}+n(n-1)\text{Inv}(\pi)_{\{1,2,...,n-1\}}+(n-1)! \sum_{k=1}^{n-1} k^2$$$$=nA_{n-1}+\frac{n!(n-1)(3n^2-5n+4)}{4}$$ We count the sum for the permutations with condition $\pi(n)=n, \pi(n)=n-1,...,\pi(n)=1$ and add them. When $\pi(n)=m$ there are $n-m$ extra numbers satisfying the condition $m < n$ and $\pi(m) > \pi(n)$. To find the $A_n$ put $A_n=f_n\cdot n!$. At last we will have $A_n=\frac{n(n - 1)(9n^2 - 5n + 10)}{144} \cdot n!$.
08.01.2023 06:21
Let $S_n$ denote the set of permutations on $\{1, 2, \ldots, n\}$, and suppose $X$ is a uniformly randomly selected permutation. 1. We have \[ \sum_{\pi \in S_n} \operatorname{inv} (\pi) = n! \cdot \mathbb E[\operatorname{inv} (X)] = n! \sum_{i < j} \mathbb E[[\pi (i) > \pi(j)]] = n! \cdot \frac{n(n-1)}{2} \cdot \frac12 = n! \cdot \frac{n^2 - n}{4},\]where $[\bullet]$ denotes the Iverson Bracket. 2. Note that \[ \sum_{\pi \in S_n} \operatorname{inv} (\pi)^2 = n! \operatorname{Var} [\operatorname{inv} (X)] - n! \cdot \mathbb E[\operatorname{inv} (X)]^2,\]so it suffices to find $\operatorname{Var} [\operatorname{inv} (X)]$. To do this, note that we can construct a uniformly random permutation by starting with $1$, placing $2$ uniformly randomly in one of $2$ spots (before or after $1$), placing $3$ uniformly randomly in one of $3$ spots, and so on. At each step, if we place the number $k$, the number of new inversions is a uniformly random nonnegative integer from $0$ to $k-1$, i.e. from $\operatorname{Unif} [0, k)$. Finally, the number of new inversions is independent of the number produced in previous steps; therefore, \[ \operatorname{Var} [\operatorname{inv} (X)] = \sum_{k=1}^n \operatorname{Var} [\operatorname{Unif} [0, k)] = \sum_{k=1}^n \frac{k^2-1}{12} = \frac{n(n+1)(2n+1)}{72} - \frac{n}{12}.\]Thus, \[ \sum_{\pi \in S_n} \operatorname{inv} (\pi)^2 = n! \left( \frac{n(n+1)(2n+1)}{72} - \frac{n}{12} - \left( \frac{n(n-1)}{4} \right)^2 \right) = n! \cdot \frac{9n^4 - 14n^3 + 15n^2 - 10n}{144}. \]
08.01.2023 10:46
Here is a nice related inequality: Let $\text{inv} (\sigma)$ be the random variable where $\sigma \in S_n$ is a random permutation of $[n]$ chosen uniformly and $\text{inv} (\sigma)$ is its inversion number. Show that $$Pr \left( \text{inv} (\sigma) > \frac{n^2}{3} \right) < \frac{C}{n}$$for some absolute constant $C > 0.$
25.01.2023 21:32
this felt more like computational combo bash than anything, i can see why this didn't make it onto the test (a) By LOE, a random permutation has an expected inversion count of ${n \choose 2}/2$, so the answer is $$n!\cdot\frac{n(n-1)}{4}.$$ (b) Let's try to find $$E({Inv(\pi) \choose 2}).$$Consider pairs of inversions instead. They fall into two categories: Category 1 inversion pairs: the two inversions share an element. If the two left endpoints match, then the 3 numbers chosen must have the left element be the highest, so it has a 1/3 chance of working, so the expected number of such inversion pairs in a random permutation is $$\frac{1}{3}{n\choose 3}.$$ If the left endpoint of one inversion shares the right endpoint of the other inversion, then the 3 numbers chosen must be in decreasing order, so the chance of this happening is 1/6, so the expected number of this type is $1/6{n\choose 3}.$ Finally, if the right endpoints match, is is analogous to the first case, so this is also $\frac{1}{3}{n\choose 3}.$ Therefore, the expected number of Category 1 inversion pairs is $$\frac{5}{6}{n\choose 3}.$$ Category 2 inversion pairs: The two inversions do not share an element. If the two intervals of inversion are entirely non-overlapping, then it has a 1/4 chance of working given any 4 numbers since the first has to be larger than the second and the third has to be larger than the fourth, so there are $1/4 {n\choose 4}$ on average for this. If the two intervals partially intersect, then it is still a 1/4 chance, so again $1/4 {n\choose 4}$. Finally, if one of the two intervals is contained within the other interval, then it again has a 1/4 chance of working, so another $1/4 {n\choose 4}$. Therefore, the expected number of Category 2 inversion pairs is $$\frac{3}{4}{n \choose 4}.$$ Therefore, $$E({Inv(\pi) \choose 2})=\frac{5}{6}{n\choose 3}+\frac{3}{4}{n \choose 4}.$$ Putting this all together... $$E(Inv(\pi)^2)=2E({Inv(\pi) \choose 2})+E(Inv(\pi))$$$$=2(\frac{5}{6}{n\choose 3}+\frac{3}{4}{n \choose 4})+\frac{n(n-1)}{4}$$$$=\frac{n(n-1)(9n^2-5n+10)}{144}.$$Therefore, finally, the answer is $$\frac{n!n(n-1)(9n^2-5n+10)}{144}$$