Why $(1+x)(1+x+x^2)\cdots(1+x+x^2+\cdots+x^n)$ gives the Poincare series?

Question

I am looking for an explanation of the fact that the polynomial $$(1+x)(1+x+x^2)...(1+x+x^2+...+x^n)$$ with Mahonian numbers gives the Poincare series for the symmetric group $S_{n+1}$ considered as a Coxeter group of type $A_n$. (see answer) Any further references are highly welcomed

Answer 1

Here's a sketch of an explanation.

For $n \in \mathbb N = \{1, 2, \ldots \}$, let us identify $S_n$ with the subgroup of $S_{n+1}$ that fixes $n+1$. This gives us a chain of inclusions $$ S_1 \subseteq S_2 \subseteq \cdots . $$ I assume that you're familiar with the concept of length of a permutation. For $\sigma \in S_n$, we denote its length by $\ell(\sigma)\in \mathbb N_0 = \{ 0, 1, \ldots \}$.

With that, we can define for a subset $M \subseteq S_n$ its Poincare polynomial as follows. $$ P_M(x) = \sum_{j = 0}^\infty \Bigl|\{\sigma \in M | \ell(\sigma) = j \}\Bigr| \cdot x^j = \sum_{\sigma \in M} x^{\ell(\sigma)} $$

Now, for $n > 1$, out of our magic hat, we pull the subset $D_n \subseteq S_n$ defined as follows.

$$ D_n = \Bigl\{id, (n (n-1)), (n (n-2)(n-1)), \ldots, (n 2 3 \ldots (n-1)), (n 1 2 \ldots (n-1)) \Bigr\} \subseteq S_n $$ You $\it{are}$ familiar with cycle notation of permutations, aren't you? :-)

I'll say more about $D_n$ later. First, let's use it to calculate $P_{S_n}$.

$D_n$ has the following properties.

(i) $D_n$ is a set of right coset representatives of $S_{n-1}\backslash S_n$. Here we consider $S_{n-1}$ a subgroup of $S_n$ as explained above. In more detail, $$ S_n = \bigcup^\cdot_{\delta \in D_n} S_{n-1} \delta $$ where the union is disjoint.

(ii) For any $\sigma \in S_{n-1}$ and any $\delta \in D_n$, we have $\ell(\sigma\delta) = \ell(\sigma) + \ell(\delta)$.

(iii) The lenghts of the elements of $D_n$ are as follows.

$\qquad \ell(id) = 0,$

$\qquad \ell((n (n-1))) = 1,$

$\qquad \ell((n (n-2)(n-1))) = 2,$

$\qquad \cdots$

$\qquad \ell((n 2 3 \ldots (n-1))) = n-2,$

$\qquad \ell((n 1 2 \ldots (n-1))) = n-1.$

Now, we will derive some facts (a), (b), (c), $\ldots$ from these properties (i), (ii), (iii).

From (iii) we get

(a) $\qquad P_{D_n}(x) = 1 + x + \cdots + x^{n - 2} + x^{n - 1}$.

This is just the definition of the Poincare Polynomial.

Next, by iterating (i), we get

(b) $\qquad S_n = S_{n-1} \cdot D_n = S_{n-2} \cdot D_{n-1} \cdot D_n = \cdots = D_2 \cdot D_3 \cdots D_{n-1} \cdot D_n$.

Moreover, every $\sigma \in S_n$ has a $\bf unique$ representation

(c) $\qquad \sigma = \delta_{(2)}\delta_{(3)} \cdots \delta_{(n-1)} \delta_{(n)} \quad with \quad \delta_{(j)} \in D_j \quad for \quad j \in \{2,\ldots,n\}$.

Facts (b) and (c) are just basic facts about cosets and representatives from general group theory.

Finally, from (ii) we get for the decomposition in (c)

(d) $\qquad \ell(\sigma) = \ell(\delta_{(2)}) + \ell(\delta_{(3)}) + \cdots + \ell(\delta_{(n-1)}) + \ell(\delta_{(n)})$.

Now, by combining facts (a) to (d) and the definition of the Poincare Polynomial, we calculate $$ P_{D_2}(x) \cdot P_{D_3}(x) \cdots P_{D_{n-1}}(x) \cdot P_{D_n}(x) = P_{D_2 \cdot D_3 \cdots D_{n-1} \cdot D_n}(x) = P_{S_n}(x), $$ which is exactly what we want.

Let me conclude with some remarks about the mysterious set $D_n$.

Property (ii) shows that $\delta \in D_n$ is uniquely shortest in its coset. Such a set of coset representatives is called a set of $\it distinguished$ representatives.

Such sets of distinguished representatives exist for more general Weyl groups and can be used to calculate their Poincare Polynomials. If you're interested, do some research on Weyl groups and Coxeter groups.

If you want to prove properties (i), (ii), (iii), it's very helpful to represent permutations as braids (see picture in this post). If you draw the strands of the braid as straight lines, the number of crossings is the length of the permutation.