# Permutations with k inversions. Combinatorial proof.

Let $i (n, k)$ denote the number of permutations  $\sigma \in S_n$ with $i (\sigma) = k$ that is with $k$ inversions. Thus we have $$\sum\limits_{\sigma \in S_n} q^{i(\sigma)} = \sum\limits_{k=0}^{\binom n 2} i(n,k) q^k$$

$i(n,k)=0$ unless $0 \le k \le \binom n 2$. We need to find the combinatorial proofs of the following identities:

1)$$\sum\limits_{\sigma \in S_n} i(\sigma) = \frac{n!}{2} \binom n 2$$ 2)$$i(n,k) = i \left( n,\binom n 2 -k\right)$$

3)For any $k$

$i(n+1,k) = i(n,k) + i(n,k-1) + i(n,k-2)+\cdots+ i(n,k-n)$

-
Hint to 1) and 2): what happens to $i\left(\sigma\right)$ if you "revert" the permutation (i. e., write it in one-line form and read it backwards)? – darij grinberg Apr 9 '13 at 6:16
Hint to 3): What happens to the number of inversions of a permutation in $S_{n+1}$ if you put the $n+1$ into its right (i. e., hindmost) place while leaving the order of all the other letters (in the one-line form) invariant? – darij grinberg Apr 9 '13 at 6:18

I am not sure whether you admit generating functions into your solution machinery, in case you do, here are some hints. (Use capital $Q$ for the number of inversions because the solution later uses complex numbers.)

First, we have for the OGF $g_n(z)$ of the inversions $$g_n(z) = \sum_{\sigma\in S_n} z^{Q(\sigma)} = \prod_{k=0}^{n-1} \sum_{j=0}^k z^j.$$

To see that this holds, note that the sum term corresponding to $k$ represents the number of possible inversions of the element $k+1$.

Now to answer the first question, differentiate by $z$ and substitute $z=1$, getting $$\left.\prod_{k=0}^{n-1} \sum_{j=0}^k z^j \sum_{k=0}^{n-1} \frac{\sum_{j=0}^k j z^{j-1}}{\sum_{j=0}^k z^j}\right|_{z=1} = n! \sum_{k=0}^{n-1} \frac{\frac{1}{2} k(k+1)}{k+1} \\= n! \frac{1}{2}\sum_{k=0}^{n-1}k = n! \frac{1}{2} \frac{1}{2} (n-1) n = \frac{1}{2} n! \binom{n}{2}.$$

For the second question, consider two polynomials $Q_1(z)$ and $Q_2(z)$ of degree $d_1$ and $d_2$ whose coefficients are the same whether read left to right or right to left.

This means that $$z^{d_1} Q_1(1/z) = Q_1(z) \quad \text{and} \quad z^{d_2} Q_2(1/z) = Q_2(z).$$

Then the coefficient $[z^n] Q_1(z) Q_2(z)$ with $0\le n\le d_1+d_2$ is given by $$\frac{1}{2\pi i} \int_{|z|=1} \frac{Q_1(z)Q_2(z)}{z^{n+1}} dz = -\frac{1}{2\pi i} \int_{|1/w|=1} \frac{Q_1(1/w)Q_2(1/w)}{w^{-n-1}} \frac{1}{w^2}dw \\= \frac{1}{2\pi i} \int_{|w|=1}\frac{w^{d_1} Q_1(1/w)w^{d_2}Q_2(1/w)}{w^{d_1+d_2-n+1}} dw = \frac{1}{2\pi i} \int_{|w|=1} \frac{Q_1(w) Q_2(w)}{w^{d_1+d_2-n+1}} dw,$$ i.e. the coefficient $[z^{d_1+d_2-n}] Q_1(z) Q_2(z).$ This means that the product of the two inherits the symmetry of the coefficients. The question now becomes trivial, since $g_n(z)$ is the product of $n$ such polynomials with symmetric coefficients.

For the third part, this is simply the Cauchy product applied to $$g_{n+1}(z) = g_n(z) \sum_{j=0}^n z^j,$$ giving $$[z^k] g_{n+1}(z) = \sum_{j=0}^{\min(k,n)} [z^{k-j}] g_n(z) \times 1 = \sum_{j=0}^{\min(k,n)} [z^{k-j}] g_n(z).$$ Your equation is not quite complete in that it assumes that negative numbers of inversions contribute zero to the recurrence.

-