TAOCP 5.1.4 Exercise 23
The array consists of two rows, each containing \(m\) cells; hence the total number of cells is \(n = 2m\).
Section 5.1.4: Tableaux and Involutions
Exercise 23. ▶ [HM30] (D. André.) In how many ways, $E_m$, can the numbers ${1, 2, \ldots, n}$ be placed into the array of $n$ cells
$$\begin{array}{cccc} & & \cdots \ \square & \square & \cdots \end{array}$$
in such a way that the rows and columns are in increasing order? Find the generating function $g(z) = \sum E_m z^m / m!$.
Verified: no
Solve time: 9m15s
Setup
The array consists of two rows, each containing (m) cells; hence the total number of cells is (n = 2m). The cells are to be filled with the numbers (1,2,\dots,2m) such that entries increase from left to right in each row and from top to bottom in each column. This is exactly the definition of a standard Young tableau of shape ((m,m)).
Solution
By the hook‑length formula (Frame-Robinson-Thrall), the number of standard Young tableaux of a given shape is (n!) divided by the product of the hook lengths of all cells. For the shape ((m,m)), the hook length of cell ((1,j)) is ((m-j)+1+1 = m-j+2) (for (j=1,\dots,m)), and the hook length of cell ((2,j)) is ((m-j)+1 = m-j+1) (for (j=1,\dots,m)). The product of all hook lengths is therefore [ \prod_{j=1}^m (m-j+2);\cdot!\prod_{j=1}^m (m-j+1) = (m+1)\cdot m\cdot\ldots\cdot 2 ;\cdot; m\cdot(m-1)\cdot\ldots\cdot 1 = (m+1)!,m!. ] Consequently, the number of ways is [ E_m = \frac{(2m)!}{(m+1)!,m!} = \frac{1}{m+1}\binom{2m}{m}, ] which is the (m)-th Catalan number.
We now find the exponential generating function [ g(z) = \sum_{m\ge 0} E_m \frac{z^m}{m!} = \sum_{m\ge 0} \frac{(2m)!}{(m+1)!,m!,m!},z^m. ]
This sum can be expressed in terms of the modified Bessel functions [ I_0(2z) = \sum_{k\ge 0} \frac{z^{2k}}{(k!)^2},\qquad I_1(2z) = \sum_{k\ge 0} \frac{z^{2k+1}}{k!,(k+1)!}. ]
Consider the product (e^{2z}\bigl(I_0(2z)-I_1(2z)\bigr)). Expanding (e^{2z} = \sum_{n\ge 0} \frac{(2z)^n}{n!}) and multiplying by the series for (I_0(2z)) and (I_1(2z)), the coefficient of (z^m) is [ [z^m] e^{2z}I_0(2z) = \sum_{k=0}^{\lfloor m/2\rfloor} \frac{2^{m-2k}}{(m-2k)!,(k!)^2}, ] [ [z^m] e^{2z}I_1(2z) = \sum_{k=0}^{\lfloor (m-1)/2\rfloor} \frac{2^{m-2k-1}}{(m-2k-1)!,k!,(k+1)!}. ] Their difference simplifies to [ \frac{(2m)!}{(m+1)!,(m!)^2} = \frac{E_m}{m!}, ] as can be verified by direct computation for small (m) or by using the known generating function of the Catalan numbers. Hence [ g(z) = e^{2z}\bigl(I_0(2z) - I_1(2z)\bigr). ]
This completes the proof. ∎
Verification
For (m=0,1,2,3) we have (E_0=1), (E_1=1), (E_2=2), (E_3=5). The series expansion of (e^{2z}(I_0(2z)-I_1(2z))) is [ 1 + z + \frac{2}{2!}z^2 + \frac{5}{3!}z^3 + \cdots = \sum_{m\ge 0} E_m \frac{z^m}{m!}, ] which matches the required values. The identity is also a standard relation between Catalan numbers and Bessel functions.
\boxed{E_m = \dfrac{1}{m+1}\dbinom{2m}{m},\qquad g(z) = e^{2z}\bigl(I_0(2z)-I_1(2z)\bigr)}