MA 415G course notes

The base cases \(I(0,0)\) is defined to be \(1\text{,}\) and \(I(n,0)=1\text{,}\) and \(I(n,k)=0\) for \(k\lt 0\) and \(k\gt \binom{n}{2}\) follow directly from the definition of inversion. To prove the recurrence, observe that every permutation in \(\ss_n\) is obtainable from a permutation \(\pi\in\ss_{n-1}\) by inserting \(n\) at some point in the one-line representation of \(\pi\text{.}\) Inserting \(n\) at the end of \(\pi\) adds \(0\) inversions. Inserting \(n\) one place from the end adds \(1\) inversion. Similarly, inserting \(n\) to the position \(i\) places from the end adds \(i\) inversions. In order to obtain a permutation with \(k\) inversions, one must insert \(n\) to the position \(i\) places from the end in a permutation \(\pi\in\ss_{n-1}\) with \(k-i\) inversions. The recursion counts the number of such permutations for each \(i\text{.}\)

We first show that \(I^{-1}\) exists. Given a vector \((a_i,a_2,\ldots,a_n)\in T_n\text{,}\) we first write \(n\) by itself. Second, we place \(n-1\text{,}\) where if \(a_{n-1}=0\) then we place it before \(n\text{,}\) and if \(a_{n-1}=1\) then we place it after \(n\text{.}\) Continue in this way, where we inductively assume that \(n,n-1,n-2,n-3,\ldots,n-i+1\) have all been placed in such a way that the partially constructed word has inversions counted by \(a_{n-i+1},\ldots,a_n\text{.}\) Next, insert \(n-i\) so that there are \(a_{n-i}\) elements in the word (so far) to its left.

By construction, we have that this map sends \(a\) to a permutation \(\pi\) with \(I(\pi)=a\text{.}\) To see that \(I^{-1}\) is one-to-one, note that if \(a\neq b\text{,}\) then some \(a_i\neq b_i\text{.}\) Thus, \(n-i\) is placed in a different order relative to \(n,n-1,n-2,n-3,\ldots,n-i+1\) for the two corresponding permutations. Thus, those permutations are different, and hence \(I^{-1}\) is one-to-one and well-defined. Since \(|T_n|=n!=|\ss_n|\text{,}\) it follows that \(I\) is a bijection.

It is immediate that \(A(n,0)=1=A(n,n-1)\) for \(n\geq 1\) because the only permutation with \(0\) descents is the identity and the only permutation with \(n-1\) descents is the reverse of the identity, i.e., the identity permutation written backwards.

To see that the recurrence holds, we consider what happens when we start with a permutation \(\pi\in \ss_n\) with \(k\) descents and remove \(n\) from the permutation. If \(\pi_i=n\text{,}\) then one of three situations can occur. The first possibility is that \(\pi_{i-1}\gt \pi_{i+1}\text{,}\) in which case removing \(n\) results in a permutation \(\pi'\in \ss_{n-1}\) with \(k\) descents. The second possibility is that \(\pi_{i-1}\lt \pi_{i+1}\text{,}\) in which case removing \(n\) results in a permutation \(\pi'\in \ss_{n-1}\) with \(k-1\) descents. The third possibility is that \(n\) occurs at either the beginning or end of the word, in which case removing \(n\) either decreases the number of descents by one or leaves it the same, respectively.

The proof proceeds by reversing this observation. For each permutation in \(\ss_{n-1}\) with \(k\) descents, inserting \(n\) in the "middle" of a descent or at the end of the permutation creates a permutation in \(\ss_n\) with \(k\) descents, and there are \(k+1\) ways to insert \(n\) into such a permutation. For each permutation in \(\ss_{n-1}\) with \(k-1\) descents, inserting \(n\) either at the beginning of the word or in the middle of an ascending pair adds a new descent, creating a permutation in \(\ss_n\) with \(k\) descents. The recurrence follows.