Recurrence relation of partioning $n$ into exactly 3 parts:

Question

I wanted to find a recurrence relation for partitioning an integer $n$ into exactly $3$ parts

To be clear, I know the formula $P(n,k)=P(n-1,k-1)+P(n-k,k)$, but I want to derive a relation involving ONLY partitions into 3 parts.

I tried to do this combinatorially, but I could not see any direct patterns to derive the recurrence relation from.

Using this answer, I was able to understand why there is a bijection between the number of partitions of $n$ into $3$ parts and the number of partitions of $n$ such that the largest part is exactly $3$.

And so the only option that I have learned in my combinatorics class is to use generating functions. However I only have converted from recurrence relations TO generating functions.

I attempted to go in the reverse direction in the following manner.

The generating function as seen in that post is:

$$G(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}$$

Taking $G(x)$ as a arbitrary sum of the recurrence relation coefficients

$$(1-x-x^2+x^4+x^5-x^6) \sum_{n\ge 0} a_nx^n = x^3$$

Multiplying and equating coefficients it must be

$$a_3-a_2-a_1=1\implies a_3=a_2+a_1+1$$

Well obviously $1$ and $2$ can not be summed into using the number $3$ so $a_1 =0, a_2 = 0$.

$3 = 3$ is the only way, so $a_3=1$, which works with the recurrence relation

$4 = 3+1$ (or $4=1+1+2$ in the other side of the bijection) so $a_4=1$.

but then $a_4 \ne a_3 + a_2 +1$, so the relation I derived literally only works for $a_3$ (I naively thought I could extend it to all $n$).

So I attempted to find the $a_n$ terms for some $n$ when multiplied out

$$(1-x-x^2+x^4+x^5-x^6)(a_0 + \dots+a_{n-6}x^{n-6}+a_{n-5}x^{n-5}+a_{n-4}x^{n-4}+a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}+a_{n}x^{n} + \dots)$$

So collecting terms $x^n$ and equating to $0$ since there is no $x^n$ on the RHS

$$a_n-a_{n-1}-a_{n-2}+a_{n-4}+a_{n-5}-a_{n-6}= 0$$

Hence $$\boxed{a_n=a_{n-1}+a_{n-2}-a_{n-4}-a_{n-5}+a_{n-6} \quad \forall n\ge 6 }$$

And by evaluating manually $a_0=0,a_1=0,a_2=0,a_4=1,a_5=2,a_6=3$. Then the Recurrence relation does work when I want to find $a_6$ ( and I assume it works for the rest).

Is this the only way I can find the recurrence relation? How would someone find this sum of $5$ terms (which skips $a_{n-3}$) combinatorially or intuitively? I worry that I have complicated the situation more than needed.

Answer 1

You can find it combinatorially!

We will count partitions whose largest part has size $3$. Let $\def\P{\mathcal P}\P(n,3)$ be the set of partitions of $n$ whose largest part has size $3$. Furthermore, let

• $E_1=\{\lambda \in \P(n,3)\mid \text{$\lambda$ has a part of size 1}\}$
• $E_2=\{\lambda \in \P(n,3)\mid \text{$\lambda$ has a part of size 2}\}$
• $E_3=\{\lambda \in \P(n,3)\mid \text{$\lambda$ has at least two parts of size 3}\}$

Note that whenever $n\ge 4$, $\mathcal P(n,3)=E_1\cup E_2\cup E_3$. Let us count the number of elements of $\P(n,3)$ using the principle of inclusion exclusion. \begin{align} |\P(n,3)|&=|E_1|+|E_2|+|E_3|\\&\quad-|E_1\cap E_2|-|E_1\cap E_3|-|E_2\cap E_3|\\&\quad+|E_1\cap E_2\cap E_3|. \end{align} Note that $|E_1|=a_{n-1}$, since removing one of the parts of size $1$ leaves a partition of $n-1$ whose largest part haze size $3$. Similarly for $E_2,E_3$. Also, $|E_1\cap E_2|=a_{n-3}$, since removing a part of size $1$ and a part of size $2$ leaves a partition of $n-3$. And so on. Making all these replacements, $$ a_n=a_{n-1}+a_{n-2}+a_{n-3}-a_{n-3}-a_{n-4}-a_{n-5}+a_{n-6}. $$