Vtgyjfy

This is a known result, but I can't find a proof. Why does
$$
sum_{sigmain S_n}q^{ell(sigma)}=frac{(1-q)(1-q^2)cdots(1-q^n)}{(1-q)^n}?
$$

Here $ell(sigma)$ is the length of $sigma$, equivalently, the number of inversions of $sigma$.

I know you can count the number of permutations on $n$ letters with $k$ inversions $I_n(k)$ recursively by
$$
I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+cdots+I_{n-1}(0)
$$
So you could get some polynomial
$$
sum_{sigmain S_n}q^{ell(sigma)}=1+I_n(1)q+I_n(2)q^2+cdots+q^{n(n-1)/2}
$$
but there's got to be a cleaner way to get the value of the right hand side?

Let $P_n(q)$ be the LHS polynomial and $Q_n(q)$ be the RHS polynomial. Clearly $P_1(q) = Q_1(q)$, and $Q_n(q)$ satisfies the recurrence $$Q_{n+1}(q) = frac{1-q^{n+1}}{1-q} Q_n(q) = (1+q+q^2+cdots+q^n)Q_n(q).$$

The question that remains is why $P_n$ satisfies the same recurrence. To see this, define $s_i in S_n$ by the transposition $s_i = (i quad i+1)$, defined for all (large enough) $n$ via the natural embeddings $S_n hookrightarrow S_{n+1}$. Recall that for $sigma in S_n$, $ell(sigma)$ is equivalently defined as the length of a minimal representative decomposition of $sigma$ as a product of $s_i$'s.

Claim: The set $$C_{n+1} := {1, s_n, s_{n-1}s_{n}, ldots, s_1s_2cdots s_{n}}$$ defines a complete set of left coset representatives of $S_n subset S_{n+1}$. That is, the multiplication map $$C_{n+1} times S_n to S_{n+1}$$ defines a bijection.

Moreover, I claim that for $omega in C_{n+1}$ and $sigma in S_n$, we have $ell(omegasigma) = ell(omega)+ell(sigma)$. Prove these facts, and use this to complete the proof.

Consider a permutation from $S_n.$ First make a choice where on the available $n$ positions you place the value one. All future elements to the left of this value will contribute an inversion. That gives the generating function $$q^{n-1}+q^{n-2}+cdots+1.$$ Having positioned one we position two and once again we have all remaining elements to the left of two will contribute an inversion. This gives the term $$q^{n-2}+q^{n-3}+cdots+1$$ (inversions with one has been counted if indeed it participates). Continuing until we place the $n$ element we obtain the product $$prod_{k=0}^{n-1}left(q^{k}+q^{k-1}+cdots+1right)
= prod_{k=0}^{n-1} frac{1-q^{k+1}}{1-q} = frac{(1-q^n)(1-q^{n-1})cdots (1-q)}{(1-q)^n}.$$

Here we have classified the inversions $(a,b)$ by the right value $b$ and the term for $k=0$ is one which is correct since the element $n$ does not participate in any inversions that haven't been counted before. In general the element $b$ can participate in at most $n-b$ inversions that haven't been counted before.