The r-major index

In this post and this one too, we discussed the inv and maj statistics on words, and two different proofs of their equidistribution. In fact, there is an even more unifying picture behind these statistics: they are simply two different instances of an entire parameterized family of statistics, called $r\text{-maj}$, all of which are equidistributed!

Rawlings defined an $r$-inversion of a permutation $\pi$ to be a pair of entries $(\pi_i,\pi_j)$ with $i\lt j$ and \[0\lt \pi_i-\pi_j\lt r.\] For instance, $21534$ has three total inversions, $(2,1)$, $(5,4)$, and $(5,3)$, but only the first two have $\pi_i-\pi_j<2$, so it has two $2$-inversions.

He also defined an $r$-descent to be an index $i$ for which \[\pi_i\ge \pi_{i+1}+r,\] so that $21534$ has only position $3$ as a $2$-descent.

Finally, he defines the $r\text{-maj}$ of a permutation to be \[r\text{-}\mathrm{maj}(\pi)=\left(\sum_{\pi_i\ge \pi_{i+1}+r}i\right)+\#r\text{-}\mathrm{inversions}.\] Thus $2\text{-}\mathrm{maj}(21534)=3+2=5$. Notice that $1\text{-maj}$ is the usual major index, and $n\text{-maj}$ is the inv statistic!

Rawling’s result is that these statistics all have the same distribution: for any $r,s\ge 1$, the number of permutations of $\{1,2,\ldots,n\}$ having $r\text{-maj}$ value $k$ is the same as the number of them having $s\text{-maj}$ value $k$ for any $k$. More succinctly, \[\sum_{\pi\in S_n} q^{r\text{-maj}(\pi)}=\sum_{\pi\in S_n} q^{s\text{-maj}(\pi)}.\]

A colleague of mine mentioned this result and challenged me to prove it without reading the proof first, so here goes. I challenge the reader to do the same before turning to the next page. Good luck!

In order to prove they are all equidistributed, it suffices to show that for any $r\ge 1$, we have \[\sum_{\pi\in S_n} q^{r\text{-maj}(\pi)}=(n)_q!=(1+q)(1+q+q^2)\cdots (1+q+q^2+\cdots + q^{n-1}).\] It is easy to see that the $q$-factorial $(n)_q!$ can also be defined by the recursion \[(n)_q!=(1+q+q^2+\cdots+q^{n-1})\cdot (n-1)_q!,\] with initial condition $(1)_q!=1.$ Thus it suffices to show that the generating function \[F_n(q)=\sum_{\pi\in S_n} q^{r\text{-maj}(\pi)}\] also satisfies this recursion.

Clearly $F_1(q)=1$, since there is one permutation of $1$ and it has no inversions or descents of any type. Now for the recursion: we want to show \[F_n(q)=(1+q+q^2+\cdots +q^{n-1})\cdot F_{n-1}(q),\] which is combinatorially equivalent to finding a way of producing, from a permutation $\pi\in S_{n-1}$, a collection of $n$ permutations $a_0(\pi),a_1(\pi),\ldots,a_{n-1}(\pi)$ in $S_n$ such that $r\text{-maj}(a_i(\pi))-r\text{-maj}(\pi)=i$ for all $i$, and such that every permutation in $S_n$ occurs exactly once among the $a_i(\pi)$’s.

To do so, consider a permutation $\pi\in S_{n-1}$. For instance, if $n=8$, we might have $\pi=5246731$, and $r=3$. We will form each of $a_0(\pi),\ldots,a_{n-1}(\pi)$ by inserting an $n$ (in this case $8$) between two of the elements of $\pi$ to form a partition in $S_n$. To make our construction clear, let us underline the numbers $1,\ldots,n-r$ in $\pi$, and boldface the $r$-descents, in this case: \[\underline{\mathbf{5}}\, \underline{2}\,\underline{4}\,6\,\mathbf{7}\,\underline{3}\,\underline{1}\] The underlined numbers are those for which, if the $n$ was inserted just to its left, it would create a new $r$-descent (and possibly break one existing $r$-descent with that entry). The non-underlined numbers are those which the $n$ can make new $r$-inversions with.

If we insert the $n$ at the end of the sequence, it does not add descents or inversions and so does not change the $r$-maj; we therefore define $a_0(\pi)$ to be the permutation formed by inserting the $n$ at the end of $\pi$.

Now, consider the gaps that are either (a) just preceding a number which is not underlined, or (b) just after an $r$-descent, as shown by the arrows: \[\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ & &\uparrow & & & &\uparrow & &\uparrow & &\uparrow & & & & \end{array} \]

Suppose there are $t$ such gaps, of type (a) or (b). If the $n$ is inserted in the rightmost such gap, it would add $1$ to the $r$-maj, since either it would form a new $r$-inversion (if the gap was type (a)) or shift the rightmost $r$-descent’s location over by $1$ (if type (b)). Since none of the non-underlined entries can be the smaller entry of an $r$-descent, no gap can be simultaneously of type (a) and (b). Thus as we move to the left along these gaps, each either successively adds an extra $r$-inversion or shifts over another $r$-descent (in addition to those already formed or shifted to its right). It follows that the $r\text{-maj}$ would increase by $i$ when inserting the $n$ in the $i$th such gap from the right:

\[\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ & &\uparrow & & & &\uparrow & &\uparrow & &\uparrow & & & & \uparrow \\ & &\small 4 & & & &\small 3 & &\small 2 & &\small 1 & & & & \small 0 \end{array} \]

and so we define $a_i(\pi)$ accordingly for $1\le i\le t$.

As for the remaining gaps, we claim that labeling them from left to right now will increase the difference by $1$ each time, starting from $t+1$. Indeed, in all other gaps the $n$ will form a new descent, with a value of $1$ in the leftmost column added to the same number of new $r$-inversions and shifted $r$-descents as for the gap of $a_t$. As we move it to the right, the position will dictate both how many of those $r$-inversions and shifted $r$-descents are undone, and the value contributed by the new $r$-descent that $n$ forms. This will have the effect of adding one each time, and so our gaps contribute differences as follows:

\[\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ \uparrow & &\uparrow & &\uparrow & &\uparrow & &\uparrow & &\uparrow & & \uparrow & & \uparrow \\ \small 5 & &\small 4 & &\small 6 & &\small 3 & &\small 2 & &\small 1 & & \small 7 & & \small 0 \end{array} \]

We define the remaining $a_i(\pi)$’s accordingly. Note that this correspondence is reversible, since we can recover $\pi$ from any $a_i(\pi)$ by simply removing the entry $n$. This completes the proof!