Problem on partioning

Question

On reading the book 'Aha! Solutions' by Martin Erickson I came to know that the number of partitions of $n$ ($n \in \mathbb{N}$) into three parts is $\left\{ {\frac{{{n^2}}}{{12}}} \right\}$ where $\left\{ {} \right\}$ denotes the nearest-integer function. But I cannot understand how this result comes. Please show me how this can be derived and how this can be generalized.

Answer 1

---

Let $P(n,k)$ be the number of partitions of $n$ into exactly $k$ parts. This function satisfies the recurrence

$$P(n,k)=P(n-1,k-1)+P(n-k,k)\;:$$

the first term on the right is the number of $k$-partitions of $n$ that have at least one part of size $1$, and the second is the number that have no parts of size $1$. (This is most easily seen by considering the Ferrers diagrams of the partitions.)

For $k=1$ we get

$$P(n,1)=P(n-1,0)+P(n-1,1)=P(n-1,1)\;,$$

so $P(n,1)=P(1,1)=1$ for all $n\ge 1$.

For $k=2$ we now get

$$\begin{align*} P(n,2)&=P(n-1,1)+P(n-2,2)\\ &=P(n-2,2)+1\;, \end{align*}$$

so $P(2m+1,2)=P(2m,2)=m$, since $P(3,2)=P(2,2)=1$. We can combine the cases as

$$P(n,2)=\left\lfloor\frac{n}2\right\rfloor\;.$$

Finally we can look at $k=3$:

$$\begin{align*} P(n,3)&=P(n-1,2)+P(n-3,3)\\ &=\left\lfloor\frac{n-1}2\right\rfloor+P(n-3,3)\\ &=\left\lfloor\frac{n-1}2\right\rfloor+\left\lfloor\frac{n-4}2\right\rfloor+P(n-6,3)\\ &\;\;\vdots\\ &=\sum_{k=0}^{\lfloor n/3\rfloor-1}\left\lfloor\frac{n-1-3k}2\right\rfloor+1\;. \end{align*}$$

If $n=6m$, this is

$$\begin{align*} \sum_{k=0}^{2m-1}\left\lfloor\frac{6m-1-3k}2\right\rfloor&=\sum_{k=1}^{2m}\left\lfloor\frac{3k-1}2\right\rfloor\\ &=\sum_{k=1}^m\left\lfloor\frac{6k-1}2\right\rfloor+\sum_{k=1}^m\left\lfloor\frac{6k-4}2\right\rfloor\\ &=\sum_{k=1}^m(3k-1)+\sum_{k=1}^m(3k-2)\\ &=3\sum_{k=1}^m(2k-1)\\ &=3m^2\\ &=\frac{n^2}{12}\;. \end{align*}$$

If $n=6m+1$, it’s

$$\begin{align*} \sum_{k=0}^{2m-1}\left\lfloor\frac{6m-3k}2\right\rfloor&=\sum_{k=1}^{2m}\left\lfloor\frac{3k}2\right\rfloor\\ &=\sum_{k=1}^m3k+\sum_{k=1}^m\left\lfloor\frac{6k-3}2\right\rfloor\\ &=\sum_{k=1}^m3k+\sum_{k=1}^m(3k-2)\\ &=2\sum_{k=1}^m(3k-1)\\ &=3m(m+1)-2m\\ &=3m^2+m\\ &=\frac{n^2-1}{12}\;. \end{align*}$$

If $n=6m+5$, it’s

$$\begin{align*} \sum_{k=0}^{2m}\left\lfloor\frac{6m+4-3k}2\right\rfloor&=\sum_{k=0}^{2m}(3m+2)+\sum_{k=0}^{2m}\left\lfloor-\frac{3k}2\right\rfloor\\ &=(2m+1)(3m+2)-\sum_{k=0}^{2m}\left\lceil\frac{3k}2\right\rceil\\ &=(2m+1)(3m+2)-\sum_{k=0}^m3k-\sum_{k=1}^m\left\lceil\frac{6k-3}2\right\rceil\\ &=6m^2+7m+2-\sum_{k=1}^m3k-\sum_{k=1}^m(3k-1)\\ &=6m^2+7m+2-\sum_{k=1}^m(6k-1)\\ &=6m^2+7m+2-\big(3m(m+1)-m\big)\\ &=3m^2+5m+2\\ &=\frac{n^2-1}{12}\;. \end{align*}$$

The other three cases are similar.