Number of partitions contained within Young shape $\lambda$

Question

It is well known that the number of partitions contained within an $m\times n$ rectangle is $\binom{m+n}{n}$.

Furthermore, it is not difficult to calculate the number of partitions contained within a Young shape $\lambda$, where $\lambda $ is also a partition, for "small" $\lambda$ by recursively counting lattice paths with steps up and to the right.

For example, the number of partitions contained within the shape $\lambda = (3,2,1,1)$ is 19.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Is there a simpler way to determine the number of partitions contained within the shape $\lambda=(\lambda_1,\dots,\lambda_n$)?

Answer 1

Ira Gessel has very kindly explained how this can be solved by counting nonintersecting lattice paths. Again, working through the example of $(3,2,1,1)$ will explain the general approach.

First, convert the problem to counting distinct part partitions contained in $(3+3,2+2,1+1,1+0) = (6,4,2,1)$. Now a collection of four nonintersecting paths from $(0,0), (1,0), (2,0), (3,0)$ to $(1,6), (2,4), (3,2), (4,1)$ gives a subpartition by looking at the height of each column of boxes. E.g.,

corresponds to $(5,3,2,0)$ in $(6,4,2,1)$ and the partition $(5-3,3-2,2-1,0-0) = (2,1,1)$ in $(3,2,1,1)$. Using the Gessel-Viennot Lemma, the number of such quartets of nonintersecting paths is given by

$$ \begin{vmatrix} \binom{7}{1} & \binom{6}{2} & \binom{5}{3} & \binom{5}{4} \\ \binom{6}{0} & \binom{5}{1} & \binom{4}{2} & \binom{4}{3} \\ \binom{7}{-1} & \binom{4}{0} & \binom{3}{1} & \binom{3}{2} \\ \binom{8}{-2} & \binom{5}{-1} & \binom{2}{0} & \binom{2}{1} \end{vmatrix} = \begin{vmatrix} 7 & 15 & 10 & 5 \\ 1 & 5 & 6 & 4 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 1 & 2 \end{vmatrix} = 19.$$

Note that moving to distinct part partitions is necessary for this approach since, for instance, the empty partition $(0,0,0,0)$ in $(3,2,1,1)$ would correspond to paths that intersect other dots along the bottom. In the equivalent distinct part subpartition problem, the empty partition corresponds to $(3,2,1,0)$.

Let me close with a historical note. In the context of Young diagrams, this determinant result is usually attributed to Kreweras 1965. In the context of partitions, MacMahon's solution is in his 1915 collection and may date to even earlier. (The MacMahon and Kreweras solutions are very similar, and Gessel and Viennot connect to Kreweras as an application of their results.)

Answer 2

Not sure how simple it is, but Percy MacMahon devised a general way to do this as an application of generating functions he worked out for plane partitions. See Combinatory Analysis v2, $\S$X, ch11, paragraphs 497-498. These are in the second pages 245-246 of the 1960 Chelsea reprint.

The answer for a general $n$ part partition is the determinant of an $n \times n$ matrix. He works out up to four parts in detail; here is the computation for your example (so $p_1 = 3$, $p_2 = 2$, $p_3 = p_4 = 1$).

$$ \frac{1}{4!} \begin{vmatrix} p_1 + 1 & p_2(p_2+1) & (p_3-1)p_3(p_3+1) & (p_4-2)(p_4-1)p_4(p_4+1) \\ 1 & 2(p_2+1) & 3p_3(p_3+1) & 4(p_4-1)p_4(p_4+1) \\ 0 & 1 & 3 (p_3+1) & 6p_4(p_4+1) \\ 0 & 0 & 1 & 4(p_4+1)\end{vmatrix} \\ = \frac{1}{24} \begin{vmatrix} 4 & 6 & 0 & 0 \\ 1 & 6 & 6 & 0 \\ 0 & 1 & 6 & 12 \\ 0 & 0 & 1 & 8 \end{vmatrix} = \frac{456}{24} = 19$$

Since a partition and its conjugate have the same number of included partitions, the work is easier considering your partition's conjugate, (4,2,1).

$$ \frac{1}{3!} \begin{vmatrix} p_1 + 1 & p_2(p_2+1) & (p_3-1)p_3(p_3+1) \\ 1 & 2(p_2+1) & 3p_3(p_3+1) \\ 0 & 1 & 3 (p_3+1) \end{vmatrix} = \frac{1}{6} \begin{vmatrix} 5 & 6 & 0 \\ 1 & 6 & 6 \\ 0 & 1 & 6 \end{vmatrix} = \frac{114}{6} = 19$$