Number of permutations with k inversions

Question

Let: $P_n(x) = 1(1+x)(1+x+x^2)+ \dots +(1+x+x^2+ \dots +x^n)$

I heard that the $k$-th coefficient of $P_n(x)$ is the number of permutations $\sigma \in S_n$ with $k$ inversions and I want to prove that, but I got stuck.

My work:

The $k$-th coefficient of $P_n(x)$ (which I will call $c_k$) is the number of ways in which we can choose a term of the form $x^a$ from each paranthesis such that their product is $k$. We will call the term we choose from the $i$-th paranthesis $x^{a_i}$. This means that: $$ c_k = |\{ (a_i)_{0\leq i\leq n} | a_i \leq i, a_i \in \mathbb{N}, \sum a_i = k\}|$$

Let $\sigma \in S_n$ such that $\sigma$ has $k$ inversions and $A_i = |\{ j | j < i, \sigma(j) > \sigma(i) \}|$. That means that: $$\sum A_i = k$$

So what I need to prove is that: $$c_k = \sum A_i$$ which I don't know how to do. Can you help me?

Answer 1

1. A correction: the number of permutations $\sigma\in S_n$ with $k$ inversions (let's still denote this number by $c_k$) is equal to the coefficient of $x^k$ in $P_{\color{red}{n-1}}(x)=(1+x)\ldots(1+x+\ldots+x^{\color{red}{n-1}})$.
2. Writing your $A_i$ as functions of $\sigma$, the crucial fact is that the map $\sigma\mapsto\big(\color{gray}{A_1(\sigma),{}}A_2(\sigma),\ldots,A_n(\sigma)\big)$ is a bijection between $S_n$ and $\color{gray}{[0,1)\times{}}[0,2)\times\ldots\times[0,n)$: given a tuple $(\color{gray}{a_1,{}}a_2,\ldots,a_n)$ of integers satisfying $0\leqslant a_k\leqslant k-1$ for $1\leqslant k\leqslant n$, one can construct a permutation $\sigma$ with $A_k(\sigma)=a_k$.
3. "So what I need to prove is..." - not quite, thus. From "2.", $c_k$ is the number of tuples $(a_1,\ldots,a_n)$ with $0\leqslant a_i\leqslant i-1$ and $a_1+\ldots+a_n=k$. Which, as we see, is exactly what's stated in "1.".