TAOCP 5.1.4 Exercise 19

Section 5.1.4: Tableaux and Involutions

Exercise 19. [M40] Find a formula for the number of ways to fill an array that is like a tableau but with two boxes removed at the left of row 1; for example,

$$ \begin{array}{l} n_1 - 2 \text{ boxes} \ n_2 \text{ boxes} \ n_3 \text{ boxes} \ \vdots \end{array} $$

is such a shape. (The rows and columns are to be in increasing order, as in ordinary tableaux.)

In other words, how many tableaux of shape $(n_1, n_2, \ldots, n_m)$ on the elements ${1, 2, \ldots, n_1 + \cdots + n_m}$ have both of the elements 1 and 2 in the first row?

Verified: yes
Solve time: 1h01m

Setup

We are asked for the number of ways to fill an array whose first row has (n_1-2) boxes, second row (n_2) boxes, third row (n_3) boxes, …, with the numbers (1,2,\dots,N-2) (where (N=n_1+\cdots+n_m)) such that rows and columns are strictly increasing. This is exactly the number of standard Young tableaux of the skew shape (\lambda/\mu) where
[ \lambda = (n_1,n_2,\dots,n_m),\qquad \mu = (2,0,\dots,0) ] (i.e. we remove the first two cells of the first row).

Equivalently, by deleting the two leftmost entries (1) and (2) from a standard Young tableau of shape (\lambda) that has both (1) and (2) in its first row, and then subtracting (2) from every remaining entry, we obtain a bijection with the tableaux of the skew shape (\lambda/\mu). Hence the desired number equals the number of standard Young tableaux of shape (\lambda) with (1,2) in the first row.

Solution

The number of standard Young tableaux of a skew shape (\lambda/\mu) is given by Aitken’s determinantal formula (a special case of the Frobenius formula for skew Schur functions). For (\lambda = (\lambda_1,\dots,\lambda_m)) and (\mu = (\mu_1,\dots,\mu_m)) with (\mu_1\ge\cdots\ge\mu_m\ge 0) and (\mu_i\le\lambda_i),
[ f^{\lambda/\mu} = |\lambda/\mu|! ;\det_{1\le i,j\le m}!\left( \frac{1}{(\lambda_i - \mu_j - i + j)!} \right), ] where we set (1/k! = 0) whenever (k<0).

In our problem (\lambda_i = n_i), (\mu_1 = 2), (\mu_j = 0) for (j\ge 2), and (|\lambda/\mu| = N-2). Substituting these values gives the required formula:

[ \boxed{A = (N-2)! ;\det_{1\le i,j\le m}!\left( \frac{1}{(n_i - \mu_j - i + j)!} \right)} ]

with the convention (1/k! = 0) for (k<0).
Explicitly, the (m\times m) matrix has entries [ M_{i,1} = \frac{1}{(n_i - i - 1)!}\quad (1\le i\le m),\qquad M_{i,j} = \frac{1}{(n_i - i + j)!}\quad (1\le i\le m,; 2\le j\le m). ]

Verification

We test the formula on several small shapes and compare with direct enumeration.

• Shape ((2,2)): (N=4). Matrix (\begin{pmatrix} 1/0! & 1/3! \ 0 & 1/2! \end{pmatrix} = \begin{pmatrix} 1 & 1/6 \ 0 & 1/2 \end{pmatrix}). Determinant (= 1/2). ((N-2)! = 2). (A = 2\cdot\frac12 = 1). The only SYT of shape ((2,2)) with (1,2) in the first row is (\begin{smallmatrix}1&2\3&4\end{smallmatrix}). ✓

• Shape ((3,2)): (N=5). Matrix (\begin{pmatrix} 1/1! & 1/4! \ 0 & 1/2! \end{pmatrix} = \begin{pmatrix} 1 & 1/24 \ 0 & 1/2 \end{pmatrix}). Determinant (= 1/2). ((N-2)! = 6). (A = 6\cdot\frac12 = 3). The three SYT of shape ((3,2)) with (1,2) in the first row are
  (\begin{smallmatrix}1&2&3\4&5\end{smallmatrix},; \begin{smallmatrix}1&2&4\3&5\end{smallmatrix},; \begin{smallmatrix}1&2&5\3&4\end{smallmatrix}). ✓

• Shape ((3,3)): (N=6). Matrix (\begin{pmatrix} 1/1! & 1/4! \ 1/0! & 1/3! \end{pmatrix} = \begin{pmatrix} 1 & 1/24 \ 1 & 1/6 \end{pmatrix}). Determinant (= \frac16-\frac1{24}=\frac18). ((N-2)! = 24). (A = 24\cdot\frac18 = 3). The three SYT of shape ((3,3)) with (1,2) in the first row are
  (\begin{smallmatrix}1&2&3\4&5&6\end{smallmatrix},; \begin{smallmatrix}1&2&4\3&5&6\end{smallmatrix},; \begin{smallmatrix}1&2&5\3&4&6\end{smallmatrix}). ✓

• Shape ((4,1)): (N=5). Matrix (\begin{pmatrix} 1/2! & 1/5! \ 0 & 1/1! \end{pmatrix} = \begin{pmatrix} 1/2 & 1/120 \ 0 & 1 \end{pmatrix}). Determinant (= 1/2). ((N-2)! = 6). (A = 6\cdot\frac12 = 3). The three SYT of shape ((4,1)) with (1,2) in the first row are
  (\begin{smallmatrix}1&2&3&4\5\end{smallmatrix},; \begin{smallmatrix}1&2&3&5\4\end{smallmatrix},; \begin{smallmatrix}1&2&4&5\3\end{smallmatrix}). ✓

All checks confirm the determinantal formula.

Notes

The same result can be obtained by evaluating the Schur function (s_{\lambda/\mu}) at (x_1=\cdots=x_N=1) using the Jacobi-Trudi identity, or by applying the identities of Exercises 17 and 18 to the Frobenius determinantal formula. The formula is valid for any (m\ge 1) and any (n_1\ge 2), (n_2,\dots,n_m\ge 0). ∎