1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That is a very elegant answer. I was trying to list partitions of $n$ by hand and see if I could recognize any recurrence pattern. I did not think at all of using the inclusion exclusion and the three sets you created (probably due to lack of experience). Do you mind elaborating more on how you determined the sizes of $E_1,E_2,E_3$? I assume for example you mean $6 = 3 + 2 + 1$ becomes $5=3+2$ so the partitions of $6$ by removing a $1$ is the same as partitions of $5$? I kind of see what you mean but its not really clicking with me at the moment. Its similiar to $P(n,k)=P(n-1,k-1)+P(n-k,k)$. $\endgroup$ – Hushus46 Apr 9 at 18:25
  • 1
    $\begingroup$ There is nothing more to it then that. To prove $|E_1|=a_{n-1}$, you give a bijection between partitions of $n$ with a part of size one to partitions of $n-1$. The bijection is simply removing one of the parts of size one. This is a bijection since it is reversible; the reverse map takes a partition of $n-1$ and adds a part of size $1$. $\endgroup$ – Mike Earnest Apr 9 at 18:28
  • $\begingroup$ I got it now, thanks! $\endgroup$ – Hushus46 Apr 9 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.