Combinatorics: Find a recursive formula for partitions of integers into three partitions.

Question

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

Answer 1

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

Answer 2

You would better think of the problem as a star&bar setting, then you just need to divide by number of permutations that varie between $3!$,$3!/2$,$1$, but since this is more of complicated and overkill for this task, and not requirements-fit, I could sentence the recursive function of all available partitions $A+B+C$ conditioned with a pre-defined symbolic ordering, i choose it to be descendent: $A>=B>=C$

$S_A(a,n)$ is considered to be the number of descendent partitions $x_1x_2...x_n$ where $x_1<=A+1$ and $x_1+x_2+...+x_n=n+a$

In your case the partitions of 6 is calculated following $s_{3}(3,3)$

We can remove the units $1$'s to simplify calculations, which take $x_1$ decremented to be $<=A$ and $x_1+x_2+...+x_n=a$

The recursive function for this matter is reduced to:

$S_{3}(3,3)=\sum_i S_{3-i}(i,2) = S_{3}(0,2)+S_{2}(1,2)+S_{1}(2,2)$ where:

$S_{A}(a,n)=\begin{cases} 0\ \text{if } \frac{a}{n}>A \\ 1\ \text{if } n=1 \\ \sum_{i=0\rightarrow a-1} S_{Min(A,a-i)}(i,n-1)\ \text{otherwise} \\ \end{cases}$

I will make this formula practicable soon, I'm off my way to work now.