Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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