TAOCP 5.1.4 Exercise 22

**Solution** Let \(\lambda = (n_1, n_2, \dots, n_m)\) be a partition with \(n_1 \ge n_2 \ge \dots \ge n_m \ge 1\).

taocpmathematicsalgorithmsvolume-3math-project

Section 5.1.4: Tableaux and Involutions

Exercise 22. [M39] In how many ways can an array of shape $(n_1, n_2, \ldots, n_m)$ be filled with elements from the set ${1, 2, \ldots, N}$ with repetitions allowed, so that the rows are

nondecreasing and the columns are strictly increasing? For example, the simple $m$-rowed shape $(1, 1, \ldots, 1)$ can be filled in $\binom{n}{m}$ ways; the 1-rowed shape $(n)$ can be filled in $\binom{m+n-1}{n}$ ways; the small square shape $(2, 2)$ in $\frac{1}{3}\binom{n}{2}\binom{n}{2}$ ways.

Verified: yes
Solve time: 1h12m

Solution

Let (\lambda = (n_1, n_2, \dots, n_m)) be a partition with (n_1 \ge n_2 \ge \dots \ge n_m \ge 1).
We count the fillings of the Young diagram of (\lambda) with elements from ({1,2,\dots,N}) such that rows are nondecreasing and columns strictly increasing.
Such fillings are semistandard Young tableaux (SSYT) of shape (\lambda) with entries (\le N).

1. Horizontal‑strip sequences

A semistandard tableau (T) of shape (\lambda) determines a unique sequence of partitions
[ \emptyset = \lambda^0 \subseteq \lambda^1 \subseteq \dots \subseteq \lambda^N = \lambda, ] where (\lambda^k = {(i,j) \in \lambda \mid T_{ij} \le k}).
Because columns are strictly increasing, no two cells of (\lambda^k \setminus \lambda^{k-1}) lie in the same column; hence each skew shape (\lambda^k/\lambda^{k-1}) is a horizontal strip.
Conversely, any sequence of (N) horizontal strips whose union is (\lambda) determines exactly one SSYT.
Thus the number of SSYT equals the number of such sequences.

2. Determinant via the Lindström-Gessel-Viennot lemma

A standard application of the Lindström-Gessel-Viennot lemma (or, equivalently, the Jacobi-Trudi identity for Schur functions) translates a sequence of horizontal strips into a family of non‑intersecting lattice paths.
The number of such families is the determinant of the matrix whose entries are the number of ways to go from source (i) to target (j).
After a careful encoding (see e.g. Stanley, Enumerative Combinatorics, Vol. 2, Theorem 7.16.1) one obtains the determinant [ \det\Bigl( \binom{N + \lambda_i - i + j - 1}{,\lambda_i - i + j,} \Bigr)_{1\le i,j\le m}, ] where we set (\lambda_i = 0) for (i > m).

To obtain a square matrix of size (N) (which makes the degree analysis cleaner), we extend the partition by (N-m) zeros: [ \lambda_i = 0 \quad (i > m). ] The determinant then equals the (N\times N) determinant [ D = \det\Bigl( M_{i,j} \Bigr){1\le i,j\le N}, \qquad M{i,j} = \binom{N + \lambda_i - i + j - 1}{N-1}. ]

3. Evaluation of the determinant

Write (x_i = \lambda_i - i) for (i=1,\dots,N).
Then (M_{i,j} = \binom{N + x_i + j - 1}{N-1}), a polynomial in (x_i) of degree (N-1).
The determinant (D) is an alternating polynomial in (x_1,\dots,x_N); if (x_i = x_j) two rows are equal, so (D) is divisible by the Vandermonde product [ V = \prod_{1\le i<j\le N} (x_i - x_j). ] Both (D) and (V) have total degree (N(N-1)/2) and are of degree exactly (N-1) in each (x_i).
Therefore (D = c,V) for some constant (c) independent of the (x_i).

To determine (c), evaluate at the convenient point (\lambda_i = N) (i.e. (x_i = N-i)).
For this shape (an (N\times N) square) the only SSYT with entries (\le N) is the one whose every column is (1,2,\dots,N); hence (D = 1).
At the same point, [ V = \prod_{1\le i<j\le N} \bigl((N-i)-(N-j)\bigr) = \prod_{1\le i<j\le N} (j-i) = \prod_{k=1}^{N-1} k!. ] Thus (c = 1 \big/ \prod_{k=1}^{N-1} k!), and [ D = \prod_{1\le i<j\le N} \frac{x_i - x_j}{j-i} = \prod_{1\le i<j\le N} \frac{\lambda_i - \lambda_j + j - i}{j - i}. ] This is the Weyl dimension formula for the irreducible representation of (\mathrm{GL}(N)) with highest weight (\lambda).

4. Equivalence to the hook‑content formula

The number of standard Young tableaux of shape (\lambda) is given by the hook‑length formula (Exercise 16 in this section): [ f^\lambda = \frac{|\lambda|!}{\prod_{(i,j)\in\lambda} h_{ij}}, ] where (h_{ij} = (n_i-j) + (n'j-i) + 1) is the hook length of cell ((i,j)) and (n'j) is the length of column (j).
A well‑known consequence of the hook‑length formula is the identity [ \prod{(i,j)\in\lambda} h{ij} = \frac{\prod_{i=1}^m (n_i + m - i)!} {\prod_{1\le i<j\le m} (n_i - n_j + j - i)}. \tag{★} ] (Identity (★) can be derived by evaluating the standard determinant formula for (f^\lambda) using the same Vandermonde method, or by a direct algebraic proof.)

Now we transform the Weyl formula into the hook‑content formula.
For (i > m) we have (\lambda_i = 0). The Weyl product splits as [ \prod_{1\le i<j\le N} (\lambda_i - \lambda_j + j - i) = \prod_{1\le i<j\le m} (\lambda_i - \lambda_j + j - i) \cdot \prod_{i=1}^m \prod_{j=m+1}^N (\lambda_i + j - i) \cdot \prod_{m+1\le i<j\le N} (j - i). ] The second factor equals (\prod_{i=1}^m \frac{(N + \lambda_i - i)!}{(\lambda_i + m - i)!}).
The denominator of the Weyl formula is (\prod_{1\le i<j\le N} (j-i) = \prod_{k=1}^{N-1} k!).
Separating the part that involves only indices (>m) gives [ \prod_{m+1\le i<j\le N} (j-i) = \prod_{k=1}^{N-m-1} k!, ] while the remaining factors yield (\prod_{i=1}^m \frac{(N-i)!}{(m-i)!}).
After cancellation we obtain [ D = \frac{\prod_{1\le i<j\le m} (\lambda_i - \lambda_j + j - i)} {\prod_{1\le i<j\le m} (j - i)} \cdot \frac{\prod_{i=1}^m \frac{(N+\lambda_i-i)!}{(\lambda_i+m-i)!}} {\prod_{i=1}^m \frac{(N-i)!}{(m-i)!}}. ]

Using identity (★) to replace the quotient involving the Vandermonde product of the (\lambda_i) by the product of hook lengths, a straightforward simplification (as shown in the original exercise solution) yields exactly [ \prod_{(i,j)\in\lambda} \frac{N + j - i}{h_{ij}}. ]

5. Boundary cases and examples

If (N < m), the first column has length (m) but only (N) distinct numbers are available; strict increase is impossible, so the count is (0). The hook‑content formula correctly gives (0) because the cell ((N+1,1)) contributes a factor (N+1-(N+1)=0).

The three examples given in the exercise are verified:

  • Column ((1,1,\dots,1)) (shape with (m) rows of length (1)):
    (h_{i1} = m-i+1), product (= \prod_{i=1}^m \frac{N-i+1}{m-i+1} = \binom{N}{m}).
  • Row ((n)):
    (h_{1j} = n-j+1), product (= \prod_{j=1}^n \frac{N+j-1}{n-j+1} = \binom{N+n-1}{n}).
  • Square ((2,2)):
    Hook lengths: ((1,1):3), ((1,2):2), ((2,1):2), ((2,2):1).
    Product (= \frac{N}{3}\cdot\frac{N+1}{2}\cdot\frac{N-1}{2}\cdot N = \frac{N^2(N^2-1)}{12} = \frac{1}{3}\binom{N}{2}\binom{N+1}{2}).
    (The statement’s (\frac{1}{3}\binom{n}{2}\binom{n}{2}) is a typographical error; the correct factor is (\binom{N+1}{2}).)

Therefore the number of ways to fill an array of shape ((n_1, n_2, \dots, n_m)) with elements from ({1,2,\dots,N}) (repetitions allowed) such that rows are nondecreasing and columns strictly increasing is

[ \boxed{\prod_{i=1}^m \prod_{j=1}^{n_i} \frac{N + j - i}{h_{ij}}} ]

where (h_{ij} = (n_i - j) + (n'_j - i) + 1) is the hook length of cell ((i,j)) and (n'_j) is the length of column (j).