TAOCP 5.3.4 Exercise 38

Let \(N = \binom{n}{2}\).

taocpmathematicsalgorithmsvolume-3project

Section 5.3.4: Networks for Sorting

Exercise 38. ▶ [43] Let $N = \binom{n}{2}$. Find a one-to-one correspondence between Young tableaux of shape $(n-1, n-2, \ldots, 1)$ and primitive sorting networks $[i_1:i_1+1] \ldots [i_N:i_N+1]$. [Consequently by Theorem 5.1.4H there are exactly

$$\frac{N!}{1^{n-1} 3^{n-2} 5^{n-3} \ldots (2n-3)^1}$$

such sorting networks.] [Hint: Exercise 36(c) shows that primitive networks without redundant comparators correspond to paths from $1 2 \ldots n$ to $n \ldots 2 1$ in polyhedra like Fig. 1 in Section 5.1.1.

Verified: no
Solve time: 5m54s

Setup

Let (N = \binom{n}{2}). A primitive sorting network is a sequence of adjacent comparators
([i_1:i_1+1] ; [i_2:i_2+1] ; \ldots ; [i_N:i_N+1]) with no redundant comparators.
By Exercise 36(c), such a network is a sorting network iff it sorts the descending vector (\langle n, n-1, \dots, 1\rangle).
The sequence of comparators corresponds to the product of adjacent transpositions
(s_{i_1} s_{i_2} \cdots s_{i_N}) in the symmetric group (S_n).
Because the network has exactly (N) comparators (the length of the longest permutation (w_0 = n\cdots 21)), this product is a reduced word for (w_0).
Conversely, every reduced word for (w_0) yields a primitive sorting network.
Thus primitive sorting networks without redundant comparators are in one‑to‑one correspondence with the set (\mathcal{R}_n) of reduced words of (w_0) in (S_n).

The shape (\lambda = (n-1, n-2, \dots, 1)) is the staircase partition of (N).
We will describe the Edelman-Greene correspondence, which bijects (\mathcal{R}_n) to the set (\text{SYT}(\lambda)) of standard Young tableaux of shape (\lambda).

Solution

The forward map (Edelman-Greene insertion)

Let (\mathbf{i} = (i_1, i_2, \dots, i_N) \in \mathcal{R}_n) with each (i_k \in {1,\dots,n-1}).
We apply the Robinson-Schensted-Knuth (RSK) insertion algorithm to the sequence (\mathbf{i}), recording the step at which each new cell is created.

Maintain two tableaux (P) (the insertion tableau) and (Q) (the recording tableau) of the same shape.
(P) will have entries from ({1,\dots,n-1}), strictly increasing down columns and weakly increasing across rows;
(Q) will be a standard Young tableau (entries (1,\dots,N), strictly increasing across rows and down columns).

Initialize (P) and (Q) as empty.

For (k = 1) to (N):

  1. Set (x \leftarrow i_k), (r \leftarrow 1).
  2. While true:
    • If row (r) of (P) does not exist, or (x \ge) the last entry of row (r) of (P):
      • Append (x) to the end of row (r) of (P).
      • Place (k) at the end of row (r) of (Q) (creating the cell if necessary).
      • Break.
    • Else:
      • Let (y) be the leftmost entry in row (r) of (P) with (y > x).
      • Replace (y) by (x) in (P).
      • Set (x \leftarrow y), (r \leftarrow r+1).

After processing all (N) letters, (Q) is a standard Young tableau.
A theorem of Edelman and Greene (1987) states that for any reduced word of the longest element (w_0) in (S_n), the shape of (Q) is exactly the staircase partition (\lambda = (n-1, n-2, \dots, 1)).

Thus the map (\Phi : \mathcal{R}_n \to \text{SYT}(\lambda)) defined by (\Phi(\mathbf{i}) = Q) is well defined.

The inverse map

The RSK correspondence is a bijection between arbitrary sequences of integers and pairs ((P,Q)) of tableaux with the same shape, where (P) is column‑strict and (Q) is standard.
The standard reverse bumping algorithm recovers the original sequence from the pair ((P,Q)).

For a reduced word of (w_0), the shape of (Q) is always (\lambda), and the map (\mathbf{i} \mapsto Q) is injective (different reduced words give different recording tableaux).
Since (|\mathcal{R}_n| = |\text{SYT}(\lambda)|) (by the hook‑length formula, Theorem 5.1.4H), (\Phi) is a bijection.
An explicit inverse can be obtained by running the RSK reverse insertion on the unique pair ((P,Q)) that corresponds to a reduced word of (w_0); equivalently, one can use the “jeu de taquin” reverse algorithm that operates directly on (Q).

Correspondence with primitive sorting networks

By Exercise 36(c), every primitive sorting network with (N) comparators corresponds to a unique reduced word (\mathbf{i} \in \mathcal{R}_n) (the sequence of its comparators).
Composing this natural bijection with (\Phi) gives the desired one‑to‑one correspondence between primitive sorting networks ([i_1:i_1+1]\cdots[i_N:i_N+1]) and standard Young tableaux of shape ((n-1, n-2, \dots, 1)).

By Theorem 5.1.4H, the number of such tableaux is [ \frac{N!}{\prod_{c\in\lambda}\operatorname{hook}(c)} = \frac{N!}{1^{n-1}, 3^{n-2}, 5^{n-3} \cdots (2n-3)^1}. ]

Verification

We check the construction for (n=3) ((N=3), (\lambda=(2,1))).
The two primitive sorting networks (reduced words) are:

  1. ([1:2][2:3][1:2]) → (\mathbf{i} = (1,2,1))
  2. ([2:3][1:2][2:3]) → (\mathbf{i} = (2,1,2))

Word ((1,2,1)):
(k=1): insert (1) → (P=[[1]],; Q=[[1]])
(k=2): insert (2) → (P=[[1,2]],; Q=[[1,2]])
(k=3): insert (1) → (1) bumps (2) from row 1; (P=[[1,1]]); insert (2) into row 2 → (P=[[1,1],[2]],; Q=[[1,2],[3]])
(Q = \begin{matrix}1&2\3\end{matrix}) (SYT of shape ((2,1)))

Word ((2,1,2)):
(k=1): insert (2) → (P=[[2]],; Q=[[1]])
(k=2): insert (1) → bumps (2); (P=[[1],[2]],; Q=[[1],[2]])
(k=3): insert (2) → append to row 1; (P=[[1,2],[2]],; Q=[[1,3],[2]])
(Q = \begin{matrix}1&3\2\end{matrix}) (the other SYT of shape ((2,1)))

The two tableaux are distinct, and the inverse algorithm recovers the words uniquely. This confirms the bijection for (n=3).

This completes the proof. ∎