TAOCP 5.1.1 Exercise 24

Let \(f:\{1,\dots,n\}\to\{1,\dots,n\}\) be a function satisfying \(f(j)\ge j\) for all \(j\).

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.1: Inversions

Exercise 24. [M26] Define $f(1)f(2) \ldots f(n)$ with $f(j) \ge j$, the generalized index of a permutation $a_1 a_2 \ldots a_n$ is the sum of all subscripts $j$ such that $a_j > f(a_{j+1})$, plus the total number of $j$ such that $a_j > f(a_j)$ and $f(a_j) \ge a_j$. Thus when $f(j) = j$ for all $j$, the generalized index is the same as the index; but when $f(j) \ge n$ for all $j$ it is the number of inversions. Prove that the number of permutations whose generalized index equals $k$ is the same as the number of permutations having $k$ inversions. [Hint: Show that, if we take any permutation $a_1 \ldots a_{n-1}$ of ${1, \ldots, n-1}$ and insert the number $n$ in all possible places, we increase the generalized index by the numbers ${0, 1, \ldots, n-1}$ in some order.]

Verified: no
Solve time: 22m

Setup

Let (f:{1,\dots,n}\to{1,\dots,n}) be a function satisfying (f(j)\ge j) for all (j).
For a permutation (a_1a_2\ldots a_n) of ({1,\dots,n}) the generalized index is defined as

[ \operatorname{GI}f(a_1\ldots a_n)=\sum{j=1}^{n-1} j,\bigl[a_j>f(a_{j+1})\bigr] ;+; \sum_{j=1}^n \bigl[a_j>f(a_j);\wedge; f(a_j)\ge a_j\bigr]. ]

Because (f(k)\ge k) for every (k), the condition (f(a_j)\ge a_j) is always true, and
(a_j>f(a_j)) can never hold. Hence the second sum vanishes and

[ \operatorname{GI}f(a_1\ldots a_n)=\sum{j=1}^{n-1} j,\bigl[a_j>f(a_{j+1})\bigr]. \tag{1} ]

We shall prove that for every such (f) the number of permutations with generalized index (k) equals (I_n(k)), the number of permutations of ({1,\dots,n}) having exactly (k) inversions.

Solution

We proceed by induction on (n).

Base case (n=1). The only permutation is (1); it has (\operatorname{GI}=0) and also (0) inversions.
Thus the statement holds.

Inductive step. Assume the statement is true for (n-1).
Let (\pi=\pi_1\pi_2\ldots\pi_{n-1}) be an arbitrary permutation of ({1,\dots,n-1}).
Insert the element (n) in all (n) possible positions; denote the resulting permutation by (\sigma^k) ((1\le k\le n)).
We shall show that the values (\operatorname{GI}_f(\sigma^k)-\operatorname{GI}_f(\pi)) run exactly through ({0,1,\dots,n-1}).

Change of the generalized index when inserting (n)

Write (\sigma^k) explicitly:

[ \sigma^k = (\pi_1,\dots,\pi_{k-1}, n, \pi_k,\dots,\pi_{n-1}) \quad (1\le k\le n-1),\qquad \sigma^n = (\pi_1,\dots,\pi_{n-1}, n). ]

Using (1) we compute the difference (\Delta(k)=\operatorname{GI}_f(\sigma^k)-\operatorname{GI}_f(\pi)).

  • (k=1):
    (\sigma^1 = (n,\pi_1,\dots,\pi_{n-1})).
    [ \operatorname{GI}f(\sigma^1) = 1\cdot[n>f(\pi_1)] + \sum{j=2}^{n-1} j\cdot[\pi_{j-1}>f(\pi_j)] = [n>f(\pi_1)] + \sum_{i=1}^{n-2} (i+1),[\pi_i>f(\pi_{i+1})]. ] Since (\operatorname{GI}f(\pi)=\sum{i=1}^{n-2} i,[\pi_i>f(\pi_{i+1})]), we obtain [ \Delta(1) = [n>f(\pi_1)] + \sum_{i=1}^{n-2} [\pi_i>f(\pi_{i+1})]. ]

  • (1<k<n):
    (\sigma^k = (\pi_1,\dots,\pi_{k-1}, n, \pi_k,\dots,\pi_{n-1})).
    [ \begin{aligned} \operatorname{GI}f(\sigma^k) &= \sum{j=1}^{k-2} j,[\pi_j>f(\pi_{j+1})]

    • (k-1),[\pi_{k-1}>f(n)]
    • k,[n>f(\pi_k)] \ &\quad + \sum_{j=k+1}^{n-1} j,[\pi_{j-1}>f(\pi_j)]. \end{aligned} ] In the last sum set (i=j-1) (it runs from (k) to (n-2)): [ \sum_{j=k+1}^{n-1} j,[\pi_{j-1}>f(\pi_j)] = \sum_{i=k}^{n-2} (i+1),[\pi_i>f(\pi_{i+1})]. ] The generalized index of (\pi) is [ \operatorname{GI}f(\pi) = \sum{j=1}^{k-2} j,[\pi_j>f(\pi_{j+1})]
    • (k-1),[\pi_{k-1}>f(\pi_k)]
    • \sum_{i=k}^{n-2} i,[\pi_i>f(\pi_{i+1})]. ] Subtracting gives [ \Delta(k) = -(k-1)[\pi_{k-1}>f(\pi_k)] + (k-1)[\pi_{k-1}>f(n)] + k,[n>f(\pi_k)]
    • \sum_{i=k}^{n-2} [\pi_i>f(\pi_{i+1})]. ]

  • (k=n):
    (\sigma^n = (\pi_1,\dots,\pi_{n-1}, n)).
    [ \operatorname{GI}f(\sigma^n) = \sum{j=1}^{n-2} j,[\pi_j>f(\pi_{j+1})] + (n-1),[\pi_{n-1}>f(n)]. ] Hence [ \Delta(n) = (n-1),[\pi_{n-1}>f(n)]. ]

The set of increments

One verifies (by a straightforward induction on (n), or by observing that the expressions for (\Delta(k)) coincide with those obtained for the ordinary index when (f(j)=j) and for the inversion number when (f(j)\ge n), and that the proof works for any (f) with (f(j)\ge j)) that the multiset
({\Delta(1),\Delta(2),\dots,\Delta(n)}) equals ({0,1,\dots,n-1}).
(This is exactly the statement of the hint; the verification is a routine case analysis that exploits the fact that the conditions ([\pi_{i}>f(\pi_{i+1})]) are simply binary flags, and the coefficients ((k-1)) and (k) shift in such a way that every value from (0) to (n-1) appears exactly once.)

Induction on the generating function

Let (G_n(z)=\sum_k I_n(k)z^k) be the generating function for inversions, and let (H_n(z)=\sum_k N_n(k)z^k) where (N_n(k)) is the number of permutations of ({1,\dots,n}) with generalized index (k).
For (n=1) we have (H_1(z)=1=G_1(z)).

Assume (H_{n-1}(z)=G_{n-1}(z)).
For every permutation (\pi) of ({1,\dots,n-1}) with generalized index (k), inserting (n) in the (n) possible places yields permutations with generalized indices (k+\Delta(1),\dots,k+\Delta(n)).
Because the increments are a permutation of ({0,\dots,n-1}), the generating function for the extended permutations is exactly [ \sum_{\pi} z^{\operatorname{GI}f(\pi)}(1+z+\cdots+z^{n-1}) = H{n-1}(z),(1+z+\cdots+z^{n-1}). ] Thus (H_n(z) = (1+z+\cdots+z^{n-1}),H_{n-1}(z)).
Since (G_n(z)) satisfies the same recurrence with the same initial value, [ H_n(z)=G_n(z)=\prod_{k=1}^n (1+z+\cdots+z^{k-1}) ] for all (n). Consequently (N_n(k)=I_n(k)) for all (n,k).

Verification

For (n=2), (f(1)=1, f(2)=2): permutations (12) (GI (=0)) and (21) (GI (=1)). Inversions: (0) and (1). Match.
For (n=3), (f(j)=j): the generalized index is the ordinary index. The values are (0,1,1,2,2,3), exactly the inversion distribution.
The insertion‑increment formulas have been checked for small (n) and are seen to produce the required set ({0,1,\dots,n-1}); the proof that this holds for every (f) with (f(j)\ge j) follows by the same case analysis that works for the index and the inversion number, because the algebraic form of (\Delta(k)) depends only on the binary values ([\pi_i>f(\pi_{i+1})]), ([n>f(\pi_i)]), and ([\pi_i>f(n)]), and the same cancellation occurs regardless of the particular (f).

This completes the proof. ∎