Length function on Weyl group $S_n$ gives part of the Pascal's triangle

Question

$$ \begin{matrix} \ell&\mathbf 0&\mathbf 1&\mathbf 2&\mathbf 3&\mathbf 4&\mathbf 5&\mathbf 6&\mathbf 7&\mathbf 8&\cdots\\ \hline \color{gray}{A_0|}&\color{gray}1\\ A_1|&1&1\\ A_2|&1&2&2&\color{red}1\\ A_3|&1&3&5&6&\color{red}5&\color{red}3&\color{red}1\\ A_4|&1&4&9&15&20&\color{red}{22}&\color{red}{20}&\color{red}{15}&\color{red}9&\color{red}\cdots\\ A_5|&1&5&14&29&49&71&\color{red}{90}&\color{red}{101}&\color{red}{101}&\color{red}\cdots\\ A_6|&1&6&20&49&98&169&259&360&\color{red}{455}&\color{red}\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{matrix} $$ In the above table,

1. The $(A_k,\mathbf l)$-th entry denotes the number of Weyl group elements with length $l$ in $S_{k+1}$.
2. Each entry with black colour admits the rule of Pascal's triangle, that is, it equals the sum of the entries to its left and above.
3. Each entry with red colour fails to satisfy the rule of Pascal's triangle.

For instance, part of the table $\begin{matrix}20&\color{red}{22}\\49&71\end{matrix}$ shows that $71=22+49$, thus $71$ is in black colour; whereas we learn from $\begin{matrix}\color{red}1&\\6&\color{red}5\end{matrix}$ that $5\neq 6+0=6$, thus $5$ is in red colour.

---

My questions are:

1. Is such phenomenon already documented?
2. Is there any existing algorithm to compute $|\{u\in W\mid \ell(u)=l_0\}|$, the number of Weyl group elements (in $W$) with length $l_0$?
3. How to find the first red entry in each row?

Answer 1

There is the so called Poincare polynomial associated to a (finite) Coxeter group $W$, as follows

$$P_{W}(q) = \sum_{w \in W} q^{\ell(w)}$$

These polynomials have a remarkable factorization. In the case $W= S_n$ we have

$$P_W(q) =[1][2] \cdots [n]$$

where $[m] \colon = \frac{q^m-1}{q-1}$ is the the "modified" $m$.

One can show explicitly such a factorization in the case of $S_n$. So this can help with your problem.

$\bf{Added:}$ Let's prove the formula for the Poincare polynomial. Consider the generators of the group $S_n$ to be, like in its Coxeter diagram, $s_1 = (1,2)$, $s_2= (2,3)$, $\ldots$, $s_{n-1} = (n-1, n)$.

We have the following equality

$$\sum_{w \in S_n} w = (e + s_{n-1})(e + s_{n-2} + s_{n-2} s_{n-1}) (e + s_{n-3} + s_{n-3} s_{n-2} + s_{n-3} s_{n-2} s_{n-1}) \cdots (e + s_1 + s_1 s_2 + \cdots + s_1 s_2 \cdots s_{n-1})$$

This means that every element of $w$ has a unique expression as a product of some factors from RHS $$w = w_{n-1} w_{n-2} \cdots w_1$$

(this is not that hard to prove, it's basically "naive" sorting)

But note that moreover we have

$$\ell(w) = \ell(w_{n-1}) + \ell(w_{n-2}) + \cdots + \ell(w_1)$$

( so this decomposition preserves the length, in general it would be $\le $).

Now just consider the morphism $w \mapsto \ell(w)$ ( this in from $W$ with a partially defined operation ( only for pairs where the length of product $=$ sum of lengthes -- a useful idea) $\&$ c.