# Number of partitions contained within Young shape $\lambda$

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$)?

-
–  Grigory M Oct 11 '13 at 7:38

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.)

-
This explains everything, indeed. Thank you! –  Grigory M Nov 26 '12 at 12:43

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$$

-
(Re: bounty) I'm interested in (a sketch of) a proof of the aforementioned formula -- or a (concise) reference, at least. –  Grigory M Nov 1 '12 at 22:05
The result I used comes at the end of 76 pages of MacMahon's treatment of "partitions in two dimensions," where he explains "Valuable information concerning line or one-dimenionsal partitions is furnished by putting $n = 1$ in the general formula." I too would like to see a more direct explanation of how this determinant "shews how many partitions of given content are contained in the given partition," but I will not have a chance to work it out during the bounty period. Anyone here well-versed in this section of Combinatory Analysis? –  Brian Hopkins Nov 4 '12 at 4:20