TAOCP 5.1.1 Exercise 4

**Exercise 5.

taocpmathematicsalgorithmsvolume-3

Section 5.1.1: Inversions

Exercise 4. [**] [20] Several other kinds of inversion tables can be defined, corresponding to a given permutation $a_1 a_2 \dots a_n$ of ${1,2,\dots,n}$, besides the particular table $b_1 b_2 \dots b_n$ defined in the text; in this exercise we will consider three other types of inversion tables that arise in applications.

Let $c_j$ be the number of inversions whose first component is $j$, that is, the number of elements to the right of $j$ that are less than $j$. [Corresponding to (1) we have the table 000142157; clearly $0 \le c_j \le j$.] Let $B_j = b_{a_j}$ and $C_j = c_{a_j}$.

Show that $0 \le B_j \le j$ and $0 \le C_j \le n-j$, for $1 \le j \le n$; furthermore show that the permutation $a_1 a_2 \dots a_n$ can be determined uniquely when either $c_1 c_2 \dots c_n$ or $B_1 B_2 \dots B_n$ or $C_1 C_2 \dots C_n$ is given.

Verified: yes
Solve time: 34m29s

Exercise 5.1.1.4, Solution

Let $a_1 a_2 \dots a_n$ be a permutation of ${1,2,\dots,n}$. Define the quantities as in the problem statement:

  • $b_i$ is the number of inversions whose second component is $i$ (the standard inversion table in the text).
  • $c_j$ is the number of inversions whose first component is $j$, that is, the number of elements to the right of $j$ that are less than $j$.
  • $B_j = b_{a_j}$ and $C_j = c_{a_j}$.

We are asked to prove the bounds for $B_j$ and $C_j$, and to show that the permutation is uniquely determined by $c_1 c_2 \dots c_n$, $B_1 B_2 \dots B_n$, or $C_1 C_2 \dots C_n$.

Step 1: Bounds

(a) Bound for $B_j$

By definition, $b_i$ is the number of elements preceding $i$ in the permutation that are greater than $i$. Therefore, for $i = a_j$, the number of such elements is at most $j$, since there are only $j-1$ positions before $a_j$ in the permutation. Hence

$$ 0 \le B_j = b_{a_j} \le j. $$

(b) Bound for $C_j$

By definition, $c_j$ is the number of elements to the right of $j$ that are less than $j$. For $i = a_j$, there are $n-j$ positions to the right in the permutation. Therefore,

$$ 0 \le C_j = c_{a_j} \le n-j. $$

Step 2: Uniqueness from $c_1 c_2 \dots c_n$

We show that the permutation can be reconstructed uniquely from the table $c_1 c_2 \dots c_n$ by a stepwise insertion method:

  1. Start with an empty sequence of length $n$.
  2. Consider $j = n, n-1, \dots, 1$ in decreasing order.
  3. Insert $j$ into the partially constructed sequence so that there are exactly $c_j$ elements to the right of $j$ that are less than $j$.

Since at step $j$ there are exactly $n-j$ positions available to the right, and $0 \le c_j \le n-j$, the position for $j$ is uniquely determined. Continuing recursively, we obtain a unique permutation.

Step 3: Uniqueness from $B_1 B_2 \dots B_n$

Recall that $B_j = b_{a_j}$, where $b_i$ is the number of elements preceding $i$ that are greater than $i$. This is equivalent to having the standard inversion table in the order of the permutation.

We can reconstruct the permutation uniquely using the following procedure (similar to the standard inversion table reconstruction):

  1. Start with an empty sequence.
  2. For $j = 1, 2, \dots, n$, insert $a_j$ into the sequence such that there are exactly $B_j$ elements before it that are greater than $a_j$.

Because $0 \le B_j \le j$, the position is uniquely determined at each step, so the reconstruction yields exactly one permutation.

Step 4: Uniqueness from $C_1 C_2 \dots C_n$

Similarly, $C_j = c_{a_j}$ counts the number of elements to the right of $a_j$ that are less than $a_j$. Reconstruction proceeds as follows:

  1. Start with an empty sequence of length $n$.
  2. For $j = n, n-1, \dots, 1$, place $a_j$ in the sequence so that exactly $C_j$ elements after $a_j$ are less than $a_j$.

Since $0 \le C_j \le n-j$, the position of $a_j$ is uniquely determined at each step. Proceeding recursively, the permutation is reconstructed uniquely.

Step 5: Conclusion

  • The bounds

$$ 0 \le B_j \le j, \quad 0 \le C_j \le n-j $$

follow directly from the definitions.

  • Each of the tables $c_1 c_2 \dots c_n$, $B_1 B_2 \dots B_n$, $C_1 C_2 \dots C_n$ uniquely determines the permutation via the indicated reconstruction procedures.

Hence all claims in the exercise are proved.

$\boxed{}$