TAOCP 5.1.4 Exercise 15

We are given the multiset \(M = \{1\cdot a,\; m\cdot b,\; n\cdot c\}\) and we want to count its permutations that satisfy the following prefix condition: > reading the permutation from left to right,...

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.4: Tableaux and Involutions

Exercise 15. [M29] How many permutations of the multiset ${1 \cdot a, m \cdot b, n \cdot c}$ have the property that, as we read the permutation from left to right, the number of $c$'s never exceeds the number of $b$'s, and the number of $b$'s never exceeds the number of $a$'s? (For example, $a, a, b, c, b, b, c, a, c, a$ is such a permutation.)

Verified: yes
Solve time: 44m12s

Setup

We are given the multiset (M = {1\cdot a,; m\cdot b,; n\cdot c}) and we want to count its permutations that satisfy the following prefix condition:

reading the permutation from left to right, at every step the number of (c)'s never exceeds the number of (b)'s, and the number of (b)'s never exceeds the number of (a)'s.

Equivalently, after mapping (a\to 1), (b\to 2), (c\to 3), we consider words (w = w_1 w_2 \ldots w_N) of length (N = 1+m+n) with exactly one (1), (m) copies of (2), and (n) copies of (3), such that for every prefix (k)

[ #{i\le k : w_i = 3} ;\le; #{i\le k : w_i = 2} ;\le; #{i\le k : w_i = 1}. ]

We will solve this using the Robinson-Schensted-Knuth (RSK) correspondence as developed in the text (Algorithm I, Theorem A).

Solution

1. RSK correspondence for the word

Write the word (w) as a two‑line array

[ \begin{pmatrix} 1 & 2 & \cdots & N \ w_1 & w_2 & \cdots & w_N \end{pmatrix}. ]

Applying the insertion algorithm (Algorithm I) to the bottom row yields a pair of tableaux ((P,Q)) of the same shape (\lambda).
(P) is a semistandard Young tableau with entries in ({1,2,3}) and weight ((1,m,n)) (one (1), (m) twos, (n) threes).
(Q) is a standard Young tableau with entries (1,2,\ldots,N) (it records the positions of the inserted elements).

2. Characterisation of the prefix condition

A fundamental property of the RSK correspondence (provable by induction on the length of the word using the bumping rules of Algorithm I) is:

A word (w) satisfies (#3 \le #2 \le #1) in every prefix if and only if its insertion tableau (P) is the superstandard tableau of shape (\lambda), i.e. the tableau whose first row consists entirely of (1)'s, second row entirely of (2)'s, and third row entirely of (3)'s.

In particular, the shape (\lambda) must be a partition with (\lambda_1 = 1), (\lambda_2 = m), (\lambda_3 = n) and we must have (1 \ge m \ge n). If these inequalities fail, no such superstandard tableau exists, hence no permutation can satisfy the condition.

3. Counting the valid permutations

When the condition holds, the superstandard tableau (P) is uniquely determined. Because the RSK correspondence is a bijection, the number of words with the given prefix property equals the number of standard Young tableaux (Q) of shape ((1,m,n)).

The number of standard Young tableaux of a given shape is given by the hook‑length formula. For the partition ((1,m,n)) with (1\ge m\ge n) the only possibilities are:

  • (m=0,; n=0) : shape ((1)) → 1 tableau.
  • (m=1,; n=0) : shape ((1,1)) → 1 tableau.
  • (m=1,; n=1) : shape ((1,1,1)) → 1 tableau.

All other ((m,n)) give 0 tableaux because the sequence ((1,m,n)) is not a partition (rows would increase) or the prefix condition itself is impossible.

Therefore the number of permutations of ({1\cdot a,; m\cdot b,; n\cdot c}) satisfying the required condition is

[ \boxed{ \begin{cases} 1 & \text{if } (m,n) \in {(0,0),;(1,0),;(1,1)},\ 0 & \text{otherwise.} \end{cases} } ]

Verification

We check each case by direct enumeration of the multiset:

  • (m=0,; n=0) : multiset ({a}). Only permutation (a). Prefixes: (a) → (#c=0\le#b=0\le#a=1). ✓
  • (m=1,; n=0) : multiset ({a,b}). Permutations: (ab), (ba).
    (ab): (a) (1,0,0) ok; (ab) (1,1,0) ok.
    (ba): (b) (0,1,0) violates (#b\le#a).
    Count = 1. ✓
  • (m=1,; n=1) : multiset ({a,b,c}). Must start with (a) (otherwise (#a=0) violated).
    If second is (c): (a,c) gives (#c=1>#b=0) violation.
    Only (abc) works. Count = 1. ✓
  • (m=2,; n=0) : ({a,b,b}). Two (b)'s force (#b\ge2) while (#a=1) always. Impossible. Count = 0. ✓
  • (m=0,; n=1) : ({a,c}). First letter (c) gives (#c=1>#b=0). Count = 0. ✓
  • All other ((m,n)) similarly fail because (#b) would exceed 1 or (#c) would exceed (#b).

All cases match the formula.

Notes

The same method applies to a multiset ({l\cdot a,; m\cdot b,; n\cdot c}) with general (l,m,n). The number of such permutations is the number of standard Young tableaux of shape ((l,m,n)), which by the hook‑length formula equals

[ \frac{(l+m+n)!}{(l+2)!,(m+1)!,n!};(l-m+1)(m-n+1)(l-n+2) \qquad\text{if } l\ge m\ge n, ]

and 0 otherwise. The example “(a;a;b;c;b;b;c;a;c;a)” has (l=4,;m=3,;n=3) and gives 210 permutations.

This completes the proof. ∎