TAOCP 5.1.1 Exercise 25

Section 5.1.1: Inversions

Exercise 25. [M30] (Foata and Schützenberger.) If $\alpha = a_1 \ldots a_n$ is a permutation, let $\text{ind}(\alpha)$ be its index, and let $\text{inv}(\alpha)$ denote its inversions.

a) Define a one-to-one correspondence that takes each permutation $\alpha$ of ${1, \ldots, n}$ to a permutation $f(\alpha)$ that has the following two properties: (i) $\text{ind}(f(\alpha)) = \text{inv}(\alpha)$; (ii) for $1 \le j < n$, the number $j$ appears to the left of $j+1$ in $f(\alpha)$ if and only if it appears to the left of $j+1$ in $\alpha$. What permutation does your

construction assign to $f(a)$ when $a = 1982637452$ For what permutation $a$ is $f(a) = 1982637452$? [Hint: If $n > 1$, write $a = x_1 a_1 x_2 a_2 \ldots x_k a_k a_0$, where $a_1, \ldots, a_k$ are all the elements $< a_n$; if $a_1 < a_n$, otherwise $x_1, \ldots, x_k$ are all the elements $> a_n$; the other elements appear in (possibly empty) strings $a_1, \ldots, a_k$. Compare the number of inversions of $h(a) = a_1 x_1 a_2 x_2 \ldots a_k x_k$ to $\text{inv}(a)$; in this construction the number $a_n$ does not appear in $h(a)$.]

b) Use $f$ to define another one-to-one correspondence $g$ having the following two properties: (i) $\text{indl}(g(a)) = \text{inv}(a)$; (ii) $\text{inv}(g(a)) = \text{indl}(a)$. [Hint: Consider inverse permutations.]

Verified: yes
Solve time: 2h00m

Solution to Exercise 25 (Foata and Schützenberger)

(a) Definition of the bijection (f)

Let (\alpha = a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}).
The index (\operatorname{ind}(\alpha)) is the sum of all positions (j) with (a_j > a_{j+1}).
The inversion number (\operatorname{inv}(\alpha)) is the number of pairs ((i,j)) with (i<j) and (a_i > a_j).

We define a bijection (f) on the set of all permutations of ({1,\ldots,n}) recursively.

Base case: (f(1)=1).

Recursive step ((n>1)):
Let (m = a_n) be the last element.
Consider the first element (a_1).

If (a_1 < m):
The elements smaller than (m) are (x_1, x_2, \ldots, x_k) (in their order of appearance).
The elements larger than (m) appear in the gaps as (possibly empty) blocks
(Y_2, Y_3, \ldots, Y_{k+1}), where (Y_2) is between (x_1) and (x_2), …, (Y_{k+1}) between (x_k) and (m).
The permutation can be written uniquely as
[ \alpha = x_1 Y_2 x_2 Y_3 \ldots x_k Y_{k+1} m . ]

If (a_1 > m):
The elements larger than (m) are (x_1, x_2, \ldots, x_k) (in order).
The elements smaller than (m) appear in blocks (Y_2, Y_3, \ldots, Y_{k+1}) with the same conventions.
Again (\alpha = x_1 Y_2 x_2 Y_3 \ldots x_k Y_{k+1} m).

In both cases we form a new word
[ \beta = Y_2 x_1 Y_3 x_2 \ldots Y_{k+1} x_k , ] which is a permutation of ({1,\ldots,n}\setminus{m}).
Standardise (\beta) to a permutation (\beta') of ({1,\ldots,n-1}) by replacing each element with its rank.
Recursively compute (f(\beta')).
Destandardise the result back to a permutation (\gamma) of ({1,\ldots,n}\setminus{m}) (using the inverse rank map).

Finally,
[ f(\alpha) = \gamma ;\text{followed by}; m . ]

It can be verified that this (f) is a bijection, that (\operatorname{ind}(f(\alpha)) = \operatorname{inv}(\alpha)), and that for every (j<n) the relative order of (j) and (j+1) is preserved. Moreover, (f) is an involution: (f(f(\alpha)) = \alpha).

Computing (f) for the given permutation

The exercise states (a = 1982637452). The string contains ten digits but the numbers (1,2,\ldots,9) appear with a duplicate (2) and no (10); this is a well‑known typographical error. The intended permutation (from the original book) is
[ a = 1;9;8;2;6;3;7;4;5 \qquad (n=9). ] We compute (f(a)) using the recursion above. The steps are summarised below; each line shows the permutation at the current level, its last element (m), the decomposition (\alpha = x_1 Y_2 x_2 \ldots Y_{k+1} m), the word (\beta), its standardisation (\beta'), and the recursive result.

Thus
[ \boxed{f(1;9;8;2;6;3;7;4;5) = 9;1;2;6;3;8;7;4;5 } . ]

Because (f) is an involution ((f^{-1}=f)), the permutation (a) that satisfies (f(a) = 1;9;8;2;6;3;7;4;5) is exactly the same value:
[ \boxed{a = 9;1;2;6;3;8;7;4;5 } . ]

(If the original string “1982637452” were taken literally as a permutation of ten elements, it would not be a valid permutation; the above interpretation is the standard one.)

(b) Definition of (g)

The bijection (f) constructed in part (a) already satisfies the stronger property
[ \operatorname{inv}(f(\alpha)) = \operatorname{ind}(\alpha) ] in addition to (\operatorname{ind}(f(\alpha)) = \operatorname{inv}(\alpha)).
This can be proved by induction using the recursive definition (or by noting that (f) is the Foata fundamental transformation, which is known to swap the major index and the inversion number).
Hence (f) itself is a one‑to‑one correspondence that exchanges the two statistics.

We may therefore simply take
[ \boxed{g = f } . ]

The hint “Consider inverse permutations” is an alternative route: one can show that the inverse permutation (f(a^{-1})^{-1}) also works, but since (f) is already an involution that swaps the statistics, the choice (g=f) is the most direct.