Quantum factorials

Lemma 3.4 in this interesting paper by A. Kleshchev and D. Nash requires a combinatorial result that I hadn’t seen before. Here is a version of it, converted into a typical mathematical game (i.e. only entertaining for people who have nothing better to do).

We work in the ring $\mathbf{Z}[q,q^{-1}]$ where $q$ is an indeterminate. Imagine a row of $n$ coins, numbered from $1$ at the far left to $n$ at the far right. Your task is to remove all $n$ coins. As you do this, you must keep track of an element $f(q) \in \mathbf{Z}[q,q^{-1}]$. At the start of the game $f(q) = 1$. If, after taking coin $i$, there are $r$ coins to its left, and $s$ empty gaps, then the rules of the game require you to multiply $f(q)$ by $q^{r-s}$.

For example, if $n=5$ and we take coins in the order $5, 1, 3, 4, 2$, then at the end of the game $f(q) = q^4 \times q^0 \times q^0 \times q^{-1} \times q^{-1} = q^2$.

Now let $F(q)$ be the sum of the final outcomes $f(q)$ over all $n!$ orders in which we might remove the coins. The remarkable result is $F(q)$ is the quantum generalization of the factorial function, i.e.

$F(q) = [n]_q! = [n]_q [n-1]_q \ldots [2]_q [1]_q$

where the quantum number $[r]_q \in \mathbf{Z}[q,q^{-1}]$ is defined by

$[r]_q = \frac{q^r - q^{-1}}{q-q^{-1}}.$

It is often useful to write $[r]_q$ in the alternative form

$[r]_q = q^{r-1} + q^{r-3} + \cdots + q^{-(r-3)} + q^{-(r-1)}.$

In this form the important property that $[r]_q \rightarrow r$ as $q \rightarrow 1$ is obvious. It follows that $\lim_{q \rightarrow 1} F(q) = n!$. Correspondingly, if we play the game with $q=1$, then the final outcome is always $1$, so this limit recovers the obvious fact that there are $n!$ different ways in which we may remove the coins.

The result that $F(q) = [n]_q!$ is easily proved by induction on $n$. If there is just one coin then the final outcome is always $q^0 = 1 = [1]_q$. Now suppose the result holds for $n-1$ coins, and suppose that we begin an $n$-coin game by removing coin $k$. This gives us an immediate contribution of $q^{k-1}$. Imagine that we ignore the gap at coin $k$ and continue playing the game as if we had started with $n-1$ coins. By induction, the sum of $F(q)$ over all possible continuations is $[n-1]_q!$. This has to be scaled by $q^{-(n-k)}$ to take into account the gap we ignored when removing coins $k+1, \ldots, n$. (The order in which we remove these coins is irrelevant.) Hence

$F(q) = [n-1]_q! \sum_{k=1}^n q^{k-1} q^{-(n-k)}.$

Since $\sum_{k=1}^n q^{2k-n-1} = [n]_q$, it follows that

$F(q) = [n-1]_q! [n]_q = [n]!_q,$

as required.