Simplify Permutation Inversion Count Recurrence

Question

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?

Answer 1

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

Answer 2

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.