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
nsato
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.
JBL
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.
aops29
20.05.2019 20:09
The answer for the first part is \(\frac{1}{2}n!\binom{n}{2}\). Let \(\mathcal{P}\) be
the set of all permutations of \([n]\). For each \(\pi\in\mathcal{P}\), define
\(\text{Inv}'(\pi)\) to be the number of pairs \((i,j)\), \(1\leq i < j \leq n\), such
that \(\pi(i) < \pi(j)\). Define
\[S_k = \{\pi\in\mathcal{P} \colon \text{Inv}(\pi) = k\} \text{ and }
T_k = \{\pi\in\mathcal{P} \colon \text{Inv}'(\pi) = k\}\]for \(k=0,1,2,\ldots,\binom{n}{2}\). For every \(\pi\in S_k\), if we reverse the order
of the numbers, we get a unique element of \(T_k\). Conversely, we can reverse the
ordering of any \(\pi\in T_k\) to get a unique element in \(S_k\). Thus, we have a
bijection between the two sets \(S_k\) and \(T_k\) for each \(k\). In particular, we must
have \(\lvert S_k \rvert=\lvert T_k \rvert\).
Now, observe that
\begin{align}
\sum_{\pi\in\mathcal{P}} \text{Inv}(\pi) &= \sum_{k=0}^{\binom{n}{2}} k\lvert S_k \rvert \\
&= \sum_{k=0}^{\binom{n}{2}} k\lvert T_k \rvert \\
&= \sum_{\pi\in\mathcal{P}} \text{Inv}'(\pi)
\end{align}
However, for any \(\pi\in\mathcal{P}\), we must have
\[\text{Inv}(\pi) + \text{Inv}'(\pi) = \binom{n}{2}\]and upon summing over \(\mathcal{P}\), we obtain
\[\sum_{\pi\in\mathcal{P}} \text{Inv}(\pi) +
\sum_{\pi\in\mathcal{P}} \text{Inv}'(\pi) = n!\binom{n}{2}\]from which the result is immediate.
Plops
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.
AIME12345
20.09.2019 05:40
Part 1:
Let $Y_n$ be the value of $\sum Inv(\pi)$ for a given $n$. Note that $Y_n=0$. Then to get from $Y_n$ to $Y_{n+1}$, we do casework on where the value $n+1$ is in the permutation. If $n+1$ is in the $k$th position of the permutation, then we add $k-1$ to the value of $Inv(\pi)$ for the digits in the permutation without $n+1$. There are $n!$ permutations for each position that $n+1$ is fixed, and each permutation in $Y_n$ is used $n+1$ times, so $Y_{n+1}=(n+1)Y_n+n!(0+1+\cdots+n)=(n+1)(Y_n+\frac{n!n}{2})=\frac{(n+1)!n}{2}+(n+1)(nY_{n-1}+\frac{(n-1)!(n-1)n}{2})=\frac{(n+1)!n}{2}+\frac{(n+1)!(n-1)}{2}+(n+1)nY_{n-1}+\cdots=\frac{(n+1)!}{2}(1+2+\cdots+n)=\frac{(n+1)!n(n+1)}{4}$. So $Y_n=\frac{n!n(n-1)}{4}$.
Part 2:
Let $X_n$ be the value of $\sum Inv(\pi)$ for a given $n$. Note that $X_n=0$. Then to get from $X_n$ to $X_{n+1}$, we do casework on where the value $n+1$ is in the permutation. For cases where $n+1$ is in the $k$th position, then if $A_1,A_2,\cdots,A_{n!}$ are the values of $Inv(\pi)$ for each permutation in $\{1,2,\cdots,n\}$, we add $k$ to each of the values, so we have $(A_1+k)^2+(A_2+k)^2+\cdots+(A_{n!}+k)^2$ contributed to the total value, and this expression simplifies as $X_n+2k(Y_n)+n!k^2$. Summing this up among all $k$ from $0$ to $n$, this becomes $(n+1)X_n+n(n+1)Y_n+n!\frac{n(n+1)(2n+1)}{6}=(n+1)X_n+\frac{n(n+1)n!n(n-1)}{4}+\frac{n!n(n+1)(2n+1)}{6}=(n+1)(\frac{n!n(2n+1)}{6}+nY_n+X_n)=(n+1)(\frac{n!n(3n^2+n+2)}{12}+n(\frac{(n-1)!(n-1)(2n-1)}{6}+(n-1)Y_{n-1}+X_{n-1}))=\cdots=(n+1)! \cdot \sum_{k=1}^{n} \frac{k(3k^2+k+2)}{12}=(n+1)! \cdot \sum_{k=1}^{n} (\frac{k^3}{4}+\frac{k^2}{12}+\frac{k}{6})=(n+1)!(\frac{(\frac{n(n+1)}{2})^2}{4}+\frac{\frac{n(n+1)(2n+1)}{6}}{12}+\frac{\frac{n(n+1)}{2}}{6})=(n+1)! \cdot \frac{9n^4+22n^3+27n^2+14n}{144}$. So $X_n=\frac{n!n(n-1)(9n^2-5n+10)}{144}$.
Ru83n05
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!$$
ike.chen
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$... .
SerdarBozdag
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!$.
Vitriol
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}. \]
MelonGirl
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.$
john0512
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}$$