TAOCP 5.1 Exercise 4

We start from the standard interpretation of inversions in a permutation $a_1 a_2 \dots a_n$, where an inversion is a pair $(i,j)$ with $i<j$ and $a_i>a_j$.

taocpmathematicsalgorithmsvolume-3

Section 5.1: Combinatorial Properties of Permutations

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: no
Solve time: 3m09s

We start from the standard interpretation of inversions in a permutation $a_1 a_2 \dots a_n$, where an inversion is a pair $(i,j)$ with $i<j$ and $a_i>a_j$.

Define:

  • $b_k$: number of inversions in which $k$ appears as the second component, i.e. number of $i<j$ with $a_j=k$ and $a_i>k$. Equivalently, number of elements to the left of $k$ that are larger than $k$.
  • $c_k$: number of inversions in which $k$ appears as the first component, i.e. number of $j>i$ with $a_i=k$ and $a_j<k$. Equivalently, number of elements to the right of $k$ that are smaller than $k$.

Let $a_j=k$. Define:

$$ B_j = b_{a_j}, \qquad C_j = c_{a_j}. $$

1. Bounds for $C_j$

Since $C_j$ counts elements to the right of position $j$ that are smaller than $a_j$, it is immediate that all such elements lie among the $n-j$ positions to the right of $j$. Hence

$$ 0 \le C_j \le n-j. $$

2. Bounds for $B_j$

Now $B_j = b_{a_j}$ counts elements to the left of position $j$ that are larger than $a_j$.

There are exactly $j-1$ positions to the left of $j$, hence

$$ 0 \le B_j \le j-1. $$

This bound is sharp because every left position may potentially contain a value larger than $a_j$.

Thus we may also state the weaker form

$$ 0 \le B_j \le j. $$

3. Reconstruction from $c_1 c_2 \dots c_n$

We reconstruct the permutation using a standard insertion process.

Maintain an ordered list of available values $S = {1,2,\dots,n}$, initially sorted increasingly.

Process $k = n, n-1, \dots, 1$.

When inserting $k$, we place it so that exactly $c_k$ elements smaller than $k$ lie to its right in the final permutation. At the moment of insertion, all numbers $<k$ are still unused, and they will eventually appear somewhere in the remaining positions. Therefore, among the available slots, we choose the position where exactly $c_k$ unused smaller elements remain to its right.

Equivalently (standard formulation), we build the permutation from right to left: at step $k$, there are exactly $k$ available positions, and $c_k \le k-1$ determines uniquely which position from the right $k$ must occupy.

Uniqueness follows because at each step the condition specifies a unique slot among the available positions, and no later insertion can affect relative order of already placed elements.

Hence $c_1,\dots,c_n$ determines a unique permutation.

4. Reconstruction from $B_1 B_2 \dots B_n$

We construct $a_1,a_2,\dots,a_n$ left to right.

At step $j$, we choose $a_j$ from the remaining unused numbers so that exactly $B_j$ previously placed elements are larger than it.

Let $R_j$ be the set of remaining numbers before choosing $a_j$. Let $L_j$ be the set of already placed values.

Among all candidates $x \in R_j$, define

$$ \phi_j(x) = |{y \in L_j : y > x}|. $$

We need $\phi_j(a_j)=B_j$.

Key invariant: at step $j$, the multiset of values in $R_j$ is known, and the map $x \mapsto \phi_j(x)$ is strictly monotone with respect to the natural order of $x$: smaller $x$ has at least as many larger elements in $L_j$ above it.

As a consequence, the values $\phi_j(x)$ for $x \in R_j$ are all distinct and range over a contiguous set of integers starting at $0$. Since

$$ 0 \le B_j \le j-1 = |L_j|, $$

there is exactly one $x \in R_j$ satisfying $\phi_j(x)=B_j$.

Thus $a_j$ is uniquely determined at each step, yielding a unique permutation.

5. Reconstruction from $C_1 C_2 \dots C_n$

We reconstruct symmetrically from right to left.

At step $j$, we choose $a_j$ so that exactly $C_j$ unused smaller elements will appear to its right.

Maintain the set of unused numbers $R_j$. When placing $a_j$, the number of available smaller elements in $R_j$ is exactly $|{x \in R_j : x < a_j}|$, which can be enforced uniquely because the values of $C_j$ range over $0,\dots,n-j$.

Again, monotonicity of this count in $a_j$ ensures a unique choice at each step.

Hence $C_1,\dots,C_n$ determines a unique permutation.

Conclusion

  • $0 \le B_j \le j-1$ (hence $0 \le B_j \le j$).
  • $0 \le C_j \le n-j$.
  • Each of the three sequences $c_1 \dots c_n$, $B_1 \dots B_n$, and $C_1 \dots C_n$ determines the permutation uniquely via a deterministic reconstruction process based on strictly monotone constraints at each step.