Let $I_{n, k}$ denote the number of permutations $\pi \in S_n$ with exactly $k$ inversions. Using the convention $I_{n, k} = 0$ for $k < 0$ and $\displaystyle k > \frac{n(n - 1)}{2}$, we first have the well-known sum

$\displaystyle I_{n, k} = \sum_{j = 0}^{n - 1} I_{n - 1, k - j}$

which can be derived by considering the position of element $1$. But there is a second recurrence:

$\displaystyle I_{n, k} = I_{n, k - 1} + I_{n - 1, k} - I_{n - 1, k - n}$

How to derive this formula? Is there a way to obtain it from the above sum using algebraic reasoning?


Here is an algebraic proof using

$$I_{n,k} = [x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$

We show that

$$I_{n,k} - I_{n,k-1} = I_{n-1,k} - I_{n-1, k-n}.$$

We get for the LHS

$$[x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q - [x^{k-1}] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q = [x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q - [x^k] x \prod_{p=0}^{n-1} \sum_{q=0}^p x^q \\ = [x^k] (1-x) \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$

For the RHS we find

$$[x^k] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q - [x^{k-n}] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q = [x^k] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q - [x^k] x^n \prod_{p=0}^{n-2} \sum_{q=0}^p x^q \\ = [x^k] (1-x^n) \prod_{p=0}^{n-2} \sum_{q=0}^p x^q = [x^k] (1-x) \sum_{q=0}^{n-1} x^q \prod_{p=0}^{n-2} \sum_{q=0}^p x^q \\ = [x^k] (1-x) \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$

This is the same as the LHS as claimed.


This is sort of an extended hint. Given a combinatorial interpretation of the summands in $$ I_{n, k} = \sum_{j = 0}^{n - 1} I_{n - 1, k - j}, $$ try to use that to interpret combinatorially the following: $$ \begin{split} I_{n, k} &= I_{n-1,k} + \sum_{j=1}^{n-1}{I_{n-1,k-j}}\\ &= I_{n-1,k} + \sum_{j=0}^{n-2}{I_{n-1,k-j-1}}\\ &= I_{n-1,k} + \sum_{j=0}^{n-1}{I_{n-1,k-1-j}}-I_{n-1,k-n}\\ &=I_{n-1,k}+I_{n,k-1}-I_{n-1,k-n}. \end{split} $$


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.