Why does $\sum_{\sigma\in S_n}q^{\ell(\sigma)}=\frac{(1-q)(1-q^2)\cdots(1-q^n)}{(1-q)^n}$?

Question

This is a known result, but I can't find a proof. Why does $$ \sum_{\sigma\in 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_{\sigma\in 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?

Answer 1

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_2\cdots 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(\omega\sigma) = \ell(\omega)+\ell(\sigma)$. Prove these facts, and use this to complete the proof.

Answer 2

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+1\right) = \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.