# Number of permutations with k inversions

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?

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.".