Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

4 nonintersecting paths

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

share|improve this answer
    
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$$

share|improve this answer
    
(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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.