Combinatorics: Find a recursive formula for partitions of integers into three partitions. I need to find a recursive formula for $p_n$ the number of ways to partition $n$ into three partitions.  For example if we look for the partitions of $6$ then they are $1+1+4$, $1+2+3$, and $2+2+2$.  Intuitively I look for the number of ways of partitioning $5$, which are $1+1+3$ and $1+2+2$, and try to relate this to the number of partitions of $6$.  Of course, for every partition of $n-1$ there is a corresponding partition of $n$ in which the (or a) maximal element is increased by $1$.  However, I'm having trouble finding a good characterization for the remaining partitions which are not formed in this way.  I could think about also increasing a minimal element, but then I would have to find a way to count the number of double-countings, which would mean counting the number of ways of partitioning $n=a+b+c$ such that $a\leq b\leq c$ and $a+1=b$ or $a+1=c+1$.  And I'm not even fully confidence that this description captures all of the ways that elements could get double-counted.
In the case of partitioning $5$ and $6$, increasing the maximal element takes the partitions $1+1+3$ and $1+2+2$ and yields $1+1+4$ and $1+2+3$.  Increasing the minimal element yields $1+2+3$ and $2+2+2$, so the double-counted element is $1+2+3$.    

I think it would be easiest to start with the generating function for partitions into $3$ parts. 
The generating function will be used to build the partition in layers.
e.g. A partition of $15$ in to $3$ parts is formed in layers: $3$ layers of width $3$, $2$ layers of width $2$ and $2$ layers of width $1$. 
$$\begin{array}{c|ccc}
\text{layer $7$}&\Large{*} & &\\
\text{layer $6$}&\Large{*} & &\\
\text{layer $5$}&\Large{*} &\Large{*} &\\
\text{layer $4$}&\Large{*} &\Large{*} &\\
\text{layer $3$}&\Large{*} &\Large{*} &\Large{*}\\
\text{layer $2$}&\Large{*} &\Large{*} &\Large{*}\\
\text{layer $1$}&\Large{*} &\Large{*} &\Large{*}\\\hline
\textbf{part no.}& 1 & 2 & 3
\end{array}$$
This is the partition $(7,5,3)$.
If we build partitions in layers, then we can have an arbitrary number ($\ge 1$) of layers of width $3$. These possibilities can be represented by:
$$x^{1\cdot 3}+x^{2\cdot 3}+x^{3\cdot 3}+\cdots=\frac{x^3}{1-x^3}\tag{1}$$
then an arbitrary number ($\ge 0$) of layers of width $2$. These possibilities can be represented by:
$$x^{0\cdot 2}+x^{1\cdot 2}+x^{2\cdot 2}+\cdots=\frac{1}{1-x^2}\tag{2}$$
then an arbitrary number ($\ge 0$) of of width $1$. These possibilities can be represented by:
$$x^{0\cdot 1}+x^{1\cdot 1}+x^{2\cdot 1}+\cdots=\frac{1}{1-x}\tag{3}$$
The generating function for partitions into exactly $3$ parts is 
$$P(x)=\sum_{k\ge 0}p_kx^k\, , \tag{4}$$
where $p_k$ is the number of partitions of $k$ into exactly $3$ parts. $P(x)$ is therefore given by the product of the factors $(1)$, $(2)$ and $(3)$:
$$P(x)=\frac{x^3}{(1-x)(1-x^2)(1-x^3)}=\frac{x^3}{1-x-x^2+x^4+x^5-x^6}\tag{5}$$
So, our example partition of $15$ above is represented by the term receiving contributing factors $x^{3\cdot 3}x^{2\cdot 2}x^{2\cdot 1}$ in this expansion of $(5)$.
Rearranging $(5)$:
$$P(x)(1-x-x^2+x^4+x^5-x^6)=x^3$$
$$\implies P(x)=x^3+(x+x^2-x^4-x^5+x^6)P(x)\, .\tag{6}$$
Using $(4)$ in $(6)$ and equating $x^k$ coefficients:

$$p_k=p_{k-1}+p_{k-2}-p_{k-4}-p_{k-5}+p_{k-6}\tag{Answer}$$

with $p_3=1$ is our starting value as shown by $(6)$.
