TAOCP 5.1.4 Exercise 14

Exercise 14. [M43] Find a more direct proof of Theorem D, part (c).

Verified: no
Solve time: 20m52s

Setup

We state Theorem D(c) in the notation of Section 5.1.4.

Theorem D(c). Let (\pi) be a permutation of ({1,2,\ldots,n}) and let ((P,Q)) be the corresponding tableaux under the Robinson-Schensted correspondence of Theorem A. If the shape of (P) is ((n_1,n_2,\ldots,n_m)), then for every (k) with (1\le k\le m) the maximum cardinality of a union of (k) increasing subsequences of (\pi) is (n_1+n_2+\cdots+n_k).

We denote by (f_k(\pi)) the maximum size of a union of (k) increasing subsequences of (\pi). The theorem claims (f_k(\pi) = \sum_{i=1}^k \lambda_i) where ((\lambda_1,\lambda_2,\ldots)) is the shape of the (P)-tableau of (\pi).

Solution

We prove Theorem D(c) by induction on the length (n) of the permutation. The case (n=0) is trivial ((f_k(\emptyset)=0) and the empty tableau has shape with all parts zero).

Assume the theorem holds for all permutations of length (n-1). Let (\pi) be a permutation of length (n). Write (\pi = \sigma \cdot x) where (\sigma) is the prefix of length (n-1) and (x) is the last element. Let (P(\sigma)) be the insertion tableau of (\sigma) with shape (\mu = (\mu_1,\mu_2,\ldots)). Insert (x) into (P(\sigma)) using Algorithm I; let the resulting tableau be (P(\pi)) with shape (\lambda = (\lambda_1,\lambda_2,\ldots)).

During the insertion of (x) the algorithm produces a bumping sequence [ x_1 = x < x_2 < \cdots < x_s < x_{s+1} = \infty ] and auxiliary column indices (r_1 \ge r_2 \ge \cdots \ge r_s = t) as described in (9)-(10). The insertion terminates at row (s); element (x_s) is appended to row (s). Consequently the shape changes as [ \lambda_i = \mu_i ;;(i<s),\qquad \lambda_s = \mu_s+1,\qquad \lambda_i = \mu_i ;;(i>s). \tag{*} ]

By the induction hypothesis (f_k(\sigma) = \sum_{i=1}^k \mu_i) for all (k). To complete the induction we must show [ f_k(\pi) = f_k(\sigma) + \delta,\qquad \delta = \begin{cases} 1 & \text{if } s\le k,\ 0 & \text{if } s > k. \end{cases} \tag{1} ]

Because adding one element can increase the size of a union of (k) increasing subsequences by at most one, we always have (f_k(\pi) \le f_k(\sigma)+1). Hence (1) will follow from two lemmas.

Lemma 1. If (s > k) then (f_k(\pi) \le f_k(\sigma)) (and therefore (f_k(\pi)=f_k(\sigma))).

Lemma 2. If (s \le k) then (f_k(\pi) \ge f_k(\sigma)+1) (and therefore (f_k(\pi)=f_k(\sigma)+1)).

Proof of Lemma 1 ((s > k))

Assume (s > k) and suppose, for a contradiction, that (f_k(\pi) = f_k(\sigma)+1). Then there exists a union (\mathcal{U} = I_1 \cup \cdots \cup I_k) of (k) increasing subsequences of (\pi) with (|\mathcal{U}| = f_k(\sigma)+1). Since (|\pi| = |\sigma|+1), the union (\mathcal{U}) must contain (x). Removing (x) yields a union (\mathcal{U}' = I_1' \cup \cdots \cup I_k') of (k) increasing subsequences of (\sigma) with (|\mathcal{U}'| = f_k(\sigma)); hence (\mathcal{U}') is optimal for (\sigma).

The bumping sequence (x_2 < x_3 < \cdots < x_{k+1}) exists because (s > k). In (P(\sigma)) these elements lie in rows (1,2,\ldots,k) respectively. Being an increasing sequence, the (k) elements (x_2,\ldots,x_{k+1}) must belong to (k) distinct subsequences of (\mathcal{U}'). Relabel the subsequences so that (x_{i+1} \in I_i') for (i=1,\ldots,k).

Consider the element (x_2). It is the leftmost element in row (1) of (P(\sigma)) that is greater than (x). In the optimal union (\mathcal{U}'), the subsequence (I_1') contains (x_2). Let (y_1) be the last element of (I_1') (possibly (y_1 = x_2)). Because (I_1') is increasing and contains (x_2), we have (x_2 \le y_1). If (y_1 > x_2), then in row (1) of (P(\sigma)) the element (y_1) would appear to the right of (x_2) (since row entries increase). But then (x_2) would not be the leftmost element (>x) in row (1), contradiction. Hence (y_1 = x_2).

Now consider (x_3) in (I_2'). The last element of (I_2') is (y_2 \ge x_3). During insertion, after bumping (x_2) we go to row (2) with (x_2) and find the leftmost element (x_3) in row (2) that is greater than (x_2). If (y_2 > x_3), then (y_2) would be an element in row (2) greater than (x_2) and to the right of (x_3), contradicting the definition of (x_3). Therefore (y_2 = x_3).

Continuing this argument up to (i=k) we obtain (y_i = x_{i+1}) for (i=1,\ldots,k). In particular the last element of (I_k') is (y_k = x_{k+1}). But the bumping sequence continues because (s > k): we have (x_{k+2}) defined and (x_{k+1} < x_{k+2}). The element (x_{k+2}) is the leftmost in row (k+1) greater than (x_{k+1}). However, (\mathcal{U}') contains (k) subsequences and we have already used all of them; the element (x_{k+2}) must belong to some subsequence of (\mathcal{U}'), but then that subsequence would have a last element (> x_{k+1}), contradicting the fact that we already assigned the last elements to be exactly (x_2,\ldots,x_{k+1}). This contradiction shows that no such optimal union (\mathcal{U}) can contain (x); hence (f_k(\pi) \le f_k(\sigma)). ∎

Proof of Lemma 2 ((s \le k))

Take an optimal union (\mathcal{U} = I_1 \cup \cdots \cup I_k) of (k) increasing subsequences of (\sigma) with (|\mathcal{U}| = f_k(\sigma)). If some (I_j) is empty or its last element is smaller than (x), we can simply append (x) to that subsequence and obtain a union of size (f_k(\sigma)+1) for (\pi), which proves the lemma.

Assume therefore that all (I_j) are nonempty and end with elements (y_j > x). We will transform (\mathcal{U}) by a sequence of “bumps” that mirrors the insertion of (x) into (P(\sigma)). The bumping sequence is (x_1 = x < x_2 < \cdots < x_s) with (s \le k). We describe the transformation step by step.

Set (i = 1) and (z_1 = x). At step (i) ((1 \le i \le s)), we have an element (z_i) that is smaller than the last elements of all current subsequences. Because the subsequences form an optimal union, we can find a subsequence whose last element is the smallest possible among those greater than (z_i); call that last element (y). Since (x_{i+1}) is the leftmost element in row (i) of (P(\sigma)) that is greater than (z_i), the same argument as in Lemma 1 shows that the last element of the subsequence containing (x_{i+1}) must be exactly (x_{i+1}). We replace that last element by (z_i) (which maintains the increasing property because (z_i < x_{i+1}) and all earlier elements in the subsequence are (\le x_{i+1})). The removed element (x_{i+1}) becomes the new (z_{i+1}). We now have a new union of (k) increasing subsequences of (\sigma) that is still optimal (same total size), and we proceed with (i \leftarrow i+1).

After (s) steps we have performed the replacements [ x_2 \leftarrow x_1,; x_3 \leftarrow x_2,; \ldots,; x_s \leftarrow x_{s-1} ] and the element (x_s) has been removed from its subsequence. At this point the subsequence that lost (x_s) is non‑empty (because it originally contained (x_s) as its last element) and its new last element is the one immediately before (x_s) in that subsequence; call it (w). By the insertion algorithm, (x_s) is appended to row (s) of (P(\sigma)), which means that in row (s) there is no element greater than (x_s). The same reasoning as before shows that (w \le x_s). But (w \neq x_s) because (x_s) was the last element; hence (w < x_s). Since (x_s) was the last element of that subsequence and we have removed it, the subsequence now ends with (w) which is strictly less than (x_s). Because (s \le k), we still have at least (k) subsequences; we can now append (x = x_1) to the subsequence that ended with (w) (or to any subsequence whose last element is (< x)). This yields a union of (k) increasing subsequences of (\pi) of size (f_k(\sigma)+1).

Thus (f_k(\pi) \ge f_k(\sigma)+1). ∎

With Lemmas 1 and 2 established, (1) holds. By induction, [ f_k(\pi) = f_k(\sigma) + \delta = \sum_{i=1}^k \mu_i + \delta = \sum_{i=1}^k \lambda_i, ] where the last equality uses the shape change ((*)). This completes the proof of Theorem D(c). ∎

Verification

We verify the argument on the permutation (\pi = (2,3,1)) of length (3).
Insert (2): (P = \boxed{2}).
Insert (3): (P = \boxed{2;3}).
Insert (1): bumps (2) from row (1); row (2) gets (2). Final (P = \begin{array}{|c|c|}\hline 1 & 3 \ \hline 2 & \ \hline\end{array}). Shape (\lambda = (2,1)).

Compute (f_k):

(k=1): LIS length is (2) (subsequence (2,3)). (\lambda_1 = 2).
(k=2): Maximum union of two increasing subsequences is the whole set ({1,2,3}) (e.g., (2,3) and (1)). (\lambda_1+\lambda_2 = 2+1 = 3).

The induction step for (n=3): (\sigma = (2,3)), (x=1). (P(\sigma)) has shape (\mu = (2)). Inserting (1) gives bumping sequence (1 < 2 < \infty), so (s=2). Since (s=2):

For (k=1): (s > 1), Lemma 1 applies, (f_1(\pi)=f_1(\sigma)=2).
For (k=2): (s \le 2), Lemma 2 applies, (f_2(\pi)=f_2(\sigma)+1=2+1=3). Both match the shape sums. The constructive transformation in Lemma 2 can be traced: optimal union for ((2,3)) is ({2,3}) (one subsequence, but we use (k=2) so we have an empty second subsequence). Appending (1) to the empty subsequence gives the union ({2,3}\cup{1}) of size (3). The proof works.

Notes

The proof uses only the basic properties of the Robinson-Schensted insertion algorithm (the bumping sequence and the shape change) and a direct manipulation of optimal unions of increasing subsequences. It avoids the “class (t)” machinery of the text and is therefore more direct. The same idea proves the full Greene-Kleitman theorem, but for Theorem D(c) the induction on the permutation length suffices.