Vrftsjtryk

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

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(sigmadelta) = 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.