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

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?

• Hint: $(1-q^k)=(1-q)(1+q+...q^{k-1})$ – JB King Aug 6 '15 at 0:39
• Do you know about the inversion table of a permutation? You can consult Stanley's book, around page 35. – Pedro Tamaroff Aug 6 '15 at 0:43
• Theorem 1.1 of this book chapter provides a proof: ams.org/bookstore/pspdf/ulect-41-prev.pdf – Steve Kass Aug 6 '15 at 0:43

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.

• Heh, I think we've both seen it from the same source. – Ben West Aug 6 '15 at 1:46
• That wouldn't be surprising! ;) – Dustan Levenstein Aug 6 '15 at 1:48

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.

• This is the proof I had in mind, using inversion tables. – Pedro Tamaroff Aug 6 '15 at 1:51