Partitions of $n$ with exactly 3 parts

Question

I'm learning about generating functions, and came across this question: find the generating function for the number of partitions of a number $n$, into exactly 3 parts. I just solved a problem where the condition was that each part is no greater than 3, but I'm kind of stuck on this one. Any ideas? Thanks!

Answer 1

Hint: The following can be found somewhat more detailed in this answer.

A generating function for the number of partitions with exactly three parts is \begin{align*} &\frac{1}{(1-x)(1-x^2)(1-x^3)}-\frac{1}{(1-x)(1-x^2)}\\ &\qquad=\frac{1}{(1-x)(1-x^2)}\left(\frac{1}{1-x^3}-1\right)\\ &\qquad=\frac{x^3}{(1-x)(1-x^2)(1-x^3)}\\ &\qquad=x^3+x^4+2x^5+3x^6+4x^7+\color{blue}{5}x^8+7x^9\cdots \end{align*}

Example: There are $\color{blue}{5}$ partitions of $8$ with three summands \begin{align*} 8&=1+1+6\\ &=1+2+5\\ &=1+3+4\\ &=2+2+4\\ &=2+3+3 \end{align*}

Answer 2

The two numbers are related to each other in a neat sort of way. Let's suppose, for example, that we want to partition $n = 10$ into three parts. One such partition is $10 = 5 + 3 + 2.$ We can represent this partition as follows:

X X X X X    5
X X X        3
X X          2

Now take this pattern of X's and "transpose" it, by reflecting it about a line starting at the upper left corner and running down & to the right (like you'd transpose a matrix):

X X X     3
X X X     3
X X       2
X         1
X         1

This is a different partition of $n = 10$: $10 = 3 + 3 + 2 + 1 + 1$. Note that because the original pattern had three rows, the new pattern has three columns; which means that no part of the new partition is greater than three. In fact, we can do this for any such partition of 10 into three parts; and given a partition of 10 such that the largest part is 3, we can find a corresponding partition of 10 into three parts. We conclude that the number of each type of partitions must be the same. This idea can then be generalized:

The number of partitions of $n$ into exactly $m$ parts is equal to the number of partitions of $n$ such that the largest part is exactly $m$.

So, if you can find the number of partitions of $n$ such that the largest part is exactly 3, then you can find the number of partitions of $n$ into exactly 3 parts.

FYI, the patterns that I used above are called Young diagrams (or sometimes Ferrers diagrams), and they pop up all the time in upper-level combinatorics.

Answer 3

$p(6n+0,3)=3n^2$

$p(6n+1,3)=3n^2+n$

$p(6n+2,3)=3n^2+2n$

$p(6n+3,3)=3n^2+3n+1$

$p(6n+4,3)=3n^2+4n+1$

$p(6n+5,3)=3n^2+5n+2$

     I think that is the complete answer in easy to understand way.

Answer 4

Other way at looking the problem.p(n,3) can be very useful.Idea behind is to put the answer as an arithmatic progression.p(n,3)=sum of all positive terms of (n-3-6t) and adding 1 if any term is zero,where t=0,1,2,3,4,5••• Ex p(11,3)=(11-3-6*0)+(11-3-6*1)=8+2=10;
p(12,3)=(12-3-6*0)+(12-3-6*1)=9+3=12;
p(15,3)=(15-3-6*0)+(15-3-6*1)+(15-3-6*2);
In the last example we encounter the third term being zero.We have to add 1 for it. Hence, p(15,3)=12+6+0+1=19

Answer 5

The easiest way is to replace $n$ by $n-3$ in your equation and you are done! Since the number of partitions on $n$ with at most $k$ elements is exactly equal to the number of partitions of $n+k$ with $k$ elements. So the number of partition of $n$ with no more that $3$ elements is the partition of $n+3$ with exactly $3$ elements. To rephrase, the number of partition of $n$ with exactly $3$ elements is the number of partitions of $n-3$ with no more than $3$ elements.

As an example, the formula you have is $(n+3)^2/12$, just replace $n$ by $n-3$ so you will get $(n-3+3)^2/12$, which is $n^2/12$.