TAOCP 5.1.1 Exercise 22

Let $a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.1: Inversions

Exercise 22. ▶ [M26] Given a permutation $a_1 a_2 \ldots a_n$ of ${1, 2, \ldots, n}$, let $h_j$ be the number of indices $i < j$ such that $a_i \in {a_j + 1, a_j + 2, \ldots, a_{j+1}}$. (If $a_{j+1} < a_j$, the elements of this set "wrap around" from $n$ to 1. When $j = n$ we use the set ${a_n + 1, a_n + 2, \ldots, n}$.) For example, the permutation $5,9,1,8,2,6,4,7,3$ leads to $h_1 \ldots h_9 = 0,0,1,2,1,1,4,1,6$.

a) Prove that $a_1 a_2 \ldots a_n$ can be reconstructed from the numbers $h_1 h_2 \ldots h_n$.

b) Prove that $h_1 + h_2 + \cdots + h_n$ is the index of $a_1 a_2 \ldots a_n$.

Verified: yes
Solve time: 1h06m

Setup

Let $a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$. For $1 \le j < n$ define the cyclic interval $$ (a_j, a_{j+1}] = \begin{cases} {a_j+1, a_j+2, \ldots, a_{j+1}}, & \text{if } a_j < a_{j+1},\[2mm] {a_j+1, \ldots, n, 1, \ldots, a_{j+1}}, & \text{if } a_j > a_{j+1}. \end{cases} $$ For $j=n$ we set $(a_n, n] = {a_n+1, \ldots, n}$. The numbers $h_j$ in the exercise are then $$ h_j = \bigl|{ i < j \mid a_i \in (a_j, a_{j+1}] }\bigr| \quad (1 \le j < n), \qquad h_n = \bigl|{ i < n \mid a_i > a_n }\bigr| = \bigl|{ i < n \mid a_i \in (a_n, n] }\bigr|. $$ The index of the permutation is $\operatorname{ind}(a) = \sum_{j=1}^{n-1} j,[a_j > a_{j+1}]$.

Solution

Part (a): Reconstruction from $h_1,\ldots,h_n$

We describe an algorithm that recovers $a_1,\ldots,a_n$ uniquely from $h_1,\ldots,h_n$.

Algorithm.

  1. Set $U = {1,2,\ldots,n}$.
  2. Let $a_n = n - h_n$ and remove $a_n$ from $U$.
  3. For $j = n-1$ down to $1$:
    • The already chosen elements are $a_{j+1},\ldots,a_n$; the remaining set is $U$ (which has size $j$).
    • Consider the cyclic order $1,2,\ldots,n$ (with $n$ followed by $1$). The element $a_{j+1}$ lies between two elements of $U$ in this order. Traverse $U$ counterclockwise starting from $a_{j+1}$ (i.e. repeatedly move to the next smaller number, wrapping from $1$ to $n$). Let the encountered elements be $u_1, u_2, \ldots, u_j$ in that order.
    • Set $a_j = u_{h_j+1}$ and remove $a_j$ from $U$.
  4. Output $a_1 a_2 \ldots a_n$.

Proof of correctness.
We show by induction on $k = n-j$ that after step $j$ the chosen elements $a_{j+1},\ldots,a_n$ together with the set $U$ of remaining elements will eventually form a permutation whose $h$-sequence is the given one.

For $j=n$ the definition of $h_n$ gives $h_n = |{i<n \mid a_i > a_n}| = n - a_n$, so $a_n = n - h_n$ is forced and unique. The set $U$ becomes ${1,\ldots,n} \setminus {a_n}$.

Now assume we have already fixed $a_{j+1},\ldots,a_n$ and the current $U$ consists of exactly those elements that will occupy positions $1,\ldots,j$. The elements that will be placed before $a_j$ are $U \setminus {a_j}$. According to the definition of $h_j$, we need $$ h_j = \bigl| { x \in U \setminus {a_j} \mid x \in (a_j, a_{j+1}] } \bigr|. $$ In the cyclic order of ${1,\ldots,n}$, the placed elements $a_{j+1},\ldots,a_n$ are interspersed with the elements of $U$. The interval $(a_j, a_{j+1}]$ contains $a_{j+1}$ and some subset of $U$. Since $a_{j+1}$ is placed, the number of elements of $U$ in $(a_j, a_{j+1}]$ is exactly the number of elements of $U$ that lie strictly between $a_j$ and $a_{j+1}$ when moving clockwise from $a_j$ to $a_{j+1}$. Equivalently, if we list the elements of $U$ in counterclockwise order starting from $a_{j+1}$, the first element has $0$ elements of $U$ between it and $a_{j+1}$, the second has $1$, …, the $j$-th has $j-1$. Therefore the value $h_j$ determines $a_j$ uniquely as the $(h_j+1)$-st element in that counterclockwise list. This choice always exists because $0 \le h_j \le j-1$ (there are $j-1$ earlier positions). The element is removed from $U$ and the induction continues.

Thus the algorithm produces a unique permutation for every admissible sequence $h_1,\ldots,h_n$. Consequently the mapping $a_1\ldots a_n \mapsto h_1\ldots h_n$ is injective, and because both sets have cardinality $n!$, it is a bijection. In particular the permutation can be reconstructed from its $h$-sequence. ∎

Part (b): $\sum_{j=1}^n h_j = \operatorname{ind}(a)$

We prove the identity by induction on $n$. For $n=1$ both sides are $0$.

Assume $n \ge 2$ and let $a = a_1\ldots a_n$. Write $m = a_n$. Remove $a_n$ from the sequence and decrease every remaining element that is larger than $m$ by $1$; this yields a permutation $b = b_1\ldots b_{n-1}$ of ${1,\ldots,n-1}$. Let $h'1,\ldots,h'{n-1}$ be the $h$-sequence of $b$.

Lemma 1. For $1 \le j \le n-2$ we have $h_j(a) = h'_j(b)$.

Proof. The elements involved in the definition of $h_j$ are $a_1,\ldots,a_{j+1}$, none of which equals $m = a_n$. The cyclic intervals $(a_j, a_{j+1}]$ in ${1,\ldots,n}$ and $(b_j, b_{j+1}]$ in ${1,\ldots,n-1}$ contain exactly the same elements after the standardization (the only difference is that $m$ is removed, but $m$ is not in the earlier set ${a_1,\ldots,a_{j-1}}$). Hence the counts are equal. ∎

Lemma 2. $h_{n-1}(a) + h_n(a) = h'{n-1}(b) + (n-1)[a{n-1} > m]$.

Proof. Let $x = a_{n-1}$ and let $E = {a_1,\ldots,a_{n-2}}$. We distinguish two cases.

Case $x < m$.
Then $b_{n-1} = x$. For $y \in E$ the standardized value is $y' = y$ if $y < m$, otherwise $y' = y-1$.
$h_n(a) = |{y \in E \mid y > m}|$ (since $x < m$).
$h_{n-1}(a) = |{y \in E \mid x < y < m}|$.
Hence $h_{n-1}(a)+h_n(a) = |{y \in E \mid y > x}|$.
In $b$ we have $h'{n-1}(b) = |{y' \in E' \mid y' > x}|$. Because $x < m$, the standardization maps exactly the elements $y > x$ to values $> x$ (if $y < m$ then $y'=y>x$; if $y > m$ then $y' = y-1 \ge m > x$). Thus $h'{n-1}(b) = |{y \in E \mid y > x}|$, and the difference is $0$. Since $[x>m]=0$, the formula holds.

Case $x > m$.
Then $b_{n-1} = x-1$.
$h_n(a) = |{y \in E \mid y > m}| + 1$ (the $+1$ comes from $x$ itself).
$h_{n-1}(a) = |{y \in E \mid y > x}| + |{y \in E \mid y \le m}|$ (the cyclic interval $(x,m]$ consists of elements $>x$ and elements $\le m$).
Summing: $h_{n-1}(a)+h_n(a) = |{y \in E \mid y > x}| + |E| + 1 = |{y \in E \mid y > x}| + n - 1$.
In $b$, $h'{n-1}(b) = |{y' \in E' \mid y' > x-1}|$. For $y \in E$ with $y < m$ we have $y' = y \le m-1 \le x-1$; for $y > m$ we have $y' = y-1 > x-1 \iff y > x$. Thus $h'{n-1}(b) = |{y \in E \mid y > x}|$. Therefore $h_{n-1}(a)+h_n(a) = h'_{n-1}(b) + n - 1$, and since $[x>m]=1$ the formula holds again. ∎

Now sum the $h$-sequences. By Lemma 1, $$ \sum_{j=1}^n h_j(a) = \sum_{j=1}^{n-2} h'j(b) + h{n-1}(a) + h_n(a). $$ Using Lemma 2 this equals $$ \sum_{j=1}^{n-1} h'j(b) + (n-1)[a{n-1} > m]. $$ By the induction hypothesis $\sum_{j=1}^{n-1} h'j(b) = \operatorname{ind}(b)$. The index of $a$ is $\operatorname{ind}(a) = \operatorname{ind}(b) + (n-1)[a{n-1} > m]$ because the descents of $a$ are exactly the descents of $b$ together with a possible descent at position $n-1$ (which occurs iff $a_{n-1} > a_n$). Hence $$ \sum_{j=1}^n h_j(a) = \operatorname{ind}(a). $$ This completes the induction and the proof. ∎

Verification

We verify the key combinatorial identity of Lemma 2 with a concrete example.
Take $a = 5;9;1;8;2;6;4;7;3$ (the permutation from the exercise, with corrected $h$-sequence). Here $n=9$, $a_8=7$, $a_9=3$, so $x=7$, $m=3$, and $x>m$.
$E = {5,9,1,8,2,6,4}$.
$h_9(a) = |{y \in E \cup {7} \mid y > 3}| = 6$ (all except $1,2$).
$h_8(a) = |{y \in E \mid y > 7}| + |{y \in E \mid y \le 3}| = |{8,9}| + |{1,2}| = 2+2=4$.
Sum = $10$.
Standardize by removing $3$ and decreasing $>3$: $b = 4;8;1;7;2;5;3;6$.
$b_7 = 6$ (since $7 \mapsto 6$). $E' = {4,8,1,7,2,5,3}$.
$h'_7(b) = |{y' \in E' \mid y' > 6}| = |{8,7}| = 2$.
Difference $10 - 2 = 8 = n-1$, matching Lemma 2.

The right-to-left reconstruction algorithm was also tested on this example and recovered the original permutation exactly.

Notes

The example in the exercise statement contains a typo: the correct $h$-sequence for $5,9,1,8,2,6,4,7,3$ is $0,0,1,2,1,4,2,4,6$, not $0,0,1,2,1,1,4,1,6$. The sum of the correct sequence is $20$, which equals the index $2+4+6+8=20$.