How to partition n into 3 parts, repetitions are not allowed Can someone please give me a really dumbed down explanation on how I can partition n into 3 parts where repetition is not allowed. I know it has to do with generating functions but I'm not really sure. Also is there a formula for this, with examples?
Thanks
 A: The first few values from $n=1$ are $0,0,0,0,0,1,1,2,3,5,6,9,11,\dots$.
We therefore want to find a closed form for the infinite polynomial:
$$P_3(x)=x^{6}+x^{7}+2x^{8}+3x^{9}+5x^{10}+6x^{11}+9x^{12}+11x^{13}+\dots$$
Other than removing a factor of $x^{6}$, there aren't any obvious algebraic manipulations to make, so we use a more visual approach.
Consider three buckets. We require that each bucket has at least one ball, and that each bucket is different.
Therefore we add $1$ ball to bucket $1$, $2$ balls to bucket $2$ and $3$ balls to bucket $3$.This gives the $x^{6}$.
In order to keep each bucket distinct, we now employ three operations:

*

*Add a ball to buckets $1,2,3$

*Add a ball to buckets $2,3$

*Add a ball to bucket $3$
As we can do each operation as many times as we want, mathematically these become:

*

*$1+x^3+x^6+\dots$

*$1+x^2+x^4+\dots$

*$1+x+x^2+\dots$
These are geometric series, and in turn equal:

*

*$\frac1{1-x^3}$

*$\frac1{1-x^2}$

*$\frac1{1-x}$
We multiply everything together to give:
$$P_3(x)=\frac{x^6}{(1-x)(1-x^2)(1-x^3)}$$
A: Incomplete answer, followed by complete answer: (you can skip to the fifth paragraph)
Let's first do partitions of $n$ into two distinct parts, $n=a+b$, $a>b>0$. If $n$ is odd, then $b$ can be anything from $1$ to $(n/2)-(1/2)$, and for each such $b$ there is a unique $a$, so the answer is $(n-1)/2$. If $n$ is even, then $b$ ranges from $1$ to $(n/2)-1$, so the answer is $(n-2)/2$. Let's just call this answer, $f(n)$.
Now, let's go to three distinct parts, $n=a+b+c$, $a>b>c>0$. If $a\ge n/2$, then the problem reduces to partitioning $n-a$ into two distinct parts, which we know has the answer $f(n-a)$. So we get, as a partial answer, $$\sum_{n/2\le a\le n-2}f(n-a)$$
Now, what if $n/3<a<n/2$? Then $b+c=n-a$, $b>c>0$. It remains to work out the bounds on $b$ (or $c$), and to calculate a couple of sums. I'll try to get back to this.
Actually, I've decided on a different approach.
First, let's consider the easier problem of finding the number of solutions of $a+b+c=n$ with $a,b,c$ each integers at least zero. This is the standard "stars and bars" problem, for which the answer is $\displaystyle{n+2\choose2}$.
Now, we want each of $a,b,c$ to be positive. The number of solutions of $a+b+c=n$ with $a,b,c$ positive is the number of solutions of $a+b+c=n-3$ with $a,b,c$ nonnegative, which again falls to stars and bars, yielding $\displaystyle{n-1\choose2}$.
Now, we have to throw out solutions where $a,b,c$ are not distinct. Let's say $a=b$. How many solutions to $a+b+c=n$ are there with $a,b,c$ positive and $a=b$? We have $a=b\ge1$, and $a=b\le(n-1)/2$, so the number of solutions is $\displaystyle\left[{n-1\over2}\right]$ (where $[x]$ means the greatest integer not exceeding $x$). Now we have an equal number of solutions with $a=c$, and an equal number with $b=c$, so we are down to $${n-1\choose2}-3\left[{n-1\over2}\right]$$ solutions to $a+b+c=n$ in distinct positive integers $a,b,c$.
But that's not quite right. If $n$ is a multiple of three, then there's one solution of $a+b+c=n$ with $a=b=c$. But we've thrown out that solution three times, as $a=b$, as $a=c$, and as $b=c$. So, we have to put it back in twice, and so the correct formula is $${n-1\choose2}-3\left[{n-1\over2}\right]+2\delta(3,n)$$ where $\delta(3,n)$ is one if $n$ is a multiple of three, and zero otherwise.
But the question is about partitions, which means we don't distinguish between, say, $6=1+2+3$ and $6=2+3+1$. So, we have overcounted by a factor of six. So, the final answer to the question is $${1\over6}\left({n-1\choose2}-3\left[{n-1\over2}\right]+2\delta(3,n)\right)$$
Example
The formula is easy to use. For example, to compute the number of suitable partitions of $100$, we calculate $\displaystyle{99\choose2}={99\times98\over2}=4851$, and $\displaystyle\left[{99\over2}\right]=49$, and $\delta(100,3)=0$, so the answer is $$(4851-3\times49+2\times0)/6=(4851-147)/6=4704/6=784$$
A: User JMP found the generating function
$$
P_3(x)={x^6\over(1-x)(1-x^2)(1-x^3)}
$$
We want a formula for the coefficients $a_n$ that you get when you expand $P_3(x)$ into a power series,
$$
P_3(x)=a_0+a_1x+a_2x^2+\cdots
$$
This is done very nicely in Andrews & Eriksson, Integer Partitions, pages 57-58:
The idea is to use a version of partial fractions. The usual setup taught in Calculus classes goes
$$
{1\over(1-x)(1-x^2)(1-x^3)}={A\over(1-x)^3}+{B\over(1-x)^2}+{C\over1-x}+{D\over1+x}+{Ex+F\over1+x+x^2}
$$
but the calculations to find $A$ through $F$ are no fun (and lead to $C=17/72$, for example) and the expansion of the last summand as a power series is also tedious. The version we use instead goes
$$
{1\over(1-x)(1-x^2)(1-x^3)}={A\over(1-x)^3}+{B\over(1-x)^2}+{C\over1-x^2}+{D\over1-x^3}
$$
It's not too hard to get $(A,B,C,D)=(1/6,1/4,1/4,1/3)$. Then we have
$$
{1/6\over(1-x)^3}+{1/4\over(1-x)^2}+{1/4\over1-x^2}+{1/3\over1-x^3}
={1\over6}\sum{n+2\choose2}x^n+{1\over4}\sum(n+1)x^n+{1\over4}\sum x^{2n}+{1\over3}\sum x^{3n}
$$
where all the sums go from $n=0$ to $\infty$. This works out to
$$
\sum\left({(n+3)^2\over12}x^n-{1\over3}x^n+{1\over4}x^{2n}+{1\over3}x^{3n}\right)=\sum\left({(n+3)^2\over12}+g(n)\right)x^n
$$
where $g(n)$ only takes on the values $-1/3$, $-1/12$, $0$, and $1/4$. So, the coefficient of $x^n$ is
$$
{(n+3)^2\over12}+g(n)
$$
But the coefficient must be an integer, and $|g(n)|<1/2$, so the coefficient is the nearest integer to $(1/12)(n+3)^2$.
Now we actually wanted the coefficient of $x^n$ in ${x^6\over(1-x)(1-x^2)(1-x^3)}$, so we have to shift by six; the final answer is then the nearest integer to $(1/12)(n-3)^2$.
For example, if $n=100$, then $(1/12)(97)^2=9409/12=784.08\dots$, so the answer is 784, just as we got in the earlier answer (but with somewhat less calculation).
