Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

A better way: Carlitz's bijection

In my previous post on the major index, I mentioned the statistics $\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\code}{code} \inv$ and $\maj$ on permutations, and the fact that they were equidistributed. I have since learned of a more enlightening way of proving this result, due to Carlitz.

Let’s start by recalling the definitions of $\inv$ and $\maj$. An inversion of a permutation of the numbers $1,2,\ldots,n$ is a pair of numbers which appear ``out of order’’ in the sequence, that is, with the larger number appearing first. For instance, for $n=4$, the permutation $3,1,4,2$ has three inversions: $(3,1)$, $(3,2)$, and $(4,2)$. We write \[\inv(3142)=3.\]

For the major index, define a descent of a permutation to be an index $i$ for which the $i$th number is greater than the $(i+1)$st. The major index is defined to be the sum of the descents. For instance, the permutation $3,1,4,2$ has two descents, in positions $1$ and $3$, so the major index is $4$. We write \[\maj(3142)=4.\]

It turns out that \begin{eqnarray} \sum_{w\in S_n} q^{\inv(w)} &=& (1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1}) \label{eqn} \\ &=& \sum_{w\in S_n}q^{\maj(w)}, \end{eqnarray} so we say that $\inv$ and $\maj$ are equidistributed, that is, the number of permutations having $\maj w=k$ is equal to the number having $\inv w=k$ for all $k$.

Carlitz’s proof, which is explained beautifully on pages 5 and 6 of this paper of Mark Skandera, cleanly shows each equality directly, without first requiring any algebraic manipulation. (Carlitz’s original paper can be found here, and it seems that by creating a MyJSTOR account, you can now access this article online for free! Thumbs up to this recent step towards open access.)

The main idea of Carlitz’s bijection is to consider an intermediate combinatorial object called a permutation code. Given a permutation $w=w_1, w_2,\ldots,w_n$ of $\{1,2,\ldots,n\}$, define $\code(w)=a_1a_2\cdots a_n$ where $a_i$ is the number of entries of $w$ to the right of $w_i$ which are less than $w_i$. For instance, we have \[\code(41532)=30210,\] since the $4$ is part of an inversion with three entries to its right, the $1$ with none, and so on. It is not hard to see that each permutation has a unique code, and a sequence is the code of some permutation if and only if its last entry is (at most) $0$, its second-to-last entry is at most $1$, its third-to-last entry is at most $2$, and so on.

To formalize this, we define a code of length $n$ to be a sequence of $n$ nonnegative integers such that the $i$th entry is no larger than $n-i$. There are clearly $n!$ codes (one choice for the last digit, two choices for the second-to-last, and so on), and furthermore the $q$-series that counts codes by the sum of their entries is given by \[\sum_{c\text{ code}\\ |c|=n} q^{\sum c_i}=(1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1}).\] The bijection $\code$ described above sends a permutation $w$ with $\inv w=k$ to a code having sum $k$, and so this immediately shows that \begin{eqnarray*} \sum_{w\in S_n} q^{\inv w}&=&\sum_{c\text{ code} |c|=n} q^{\sum c_i} \\ &=&(1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1}). \end{eqnarray*}

So, it now suffices to find a bijection between codes of length $n$ and permutations of $n$, which I’ll call $\phi$, which sends the sum of the code to $\maj$ of the permutation. Given a code of length $n$, we read it backwards, and at each step insert the numbers $n, n-1,\ldots$ successively to form a permutation, so that at each step, the major index of the resulting word increases by precisely the code number read at each step. For example, consider the code $30210$ from above. We read it backwards, so the first entry is $0$, and we first place a $5$ in our permutation. So our first step yields the sequence: \[5\] The next code entry from the right is $1$, so we must insert the $4$ in a way that increases the major index by exactly one. We see that the only way to do this is to insert it to the right of the $5$: \[5,4\] The next code entry is $2$, so we insert the $3$ to the right of the $4$, as this is the only way to increase the major index by $2$: \[5,4,3\] The next entry is $0$, and the only place to insert a $2$ so that the major index does not change is before the $3$. So our sequence is now: \[5,4,2,3\] Finally, we insert the $1$ so as to increase the major index by $3$: \[5,4,2,1,3\]

So $\phi(30210)=54213.$ It is not hard to show that there is always exactly one valid insertion of the next number at each step in the process, and hence $\phi$ is a bijection, with the property that $\sum(c)=\maj(\phi(c))$ for any code $c$ of length $n$. This implies immediately that \begin{eqnarray*} \sum_{w\in S_n} q^{\maj w}&=&\sum_{c\text{ code} |c|=n} q^{\sum c_i} \\ &=&(1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1}), \end{eqnarray*} and the desired equation follows.