4
$\begingroup$

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?

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

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.