To prove identity $P(n,3)= \lfloor n^2/12 \rfloor$

Question

Suppose $P(n,k)$ is number of partitions of positive integer n by k positive integers with no duplicative tuples. And $\lfloor r\rfloor$ is largest of integers equal or less than real number $r$

If $n\not\equiv 3\pmod6$ Then $P(n,3)=\lfloor \frac{n^2}{12}\rfloor$.

My bruteforcing answer is that $P(n,3)$ $=(\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor} num.(a,b):a\leq b, a+b+i=n)$ $=(\sum_{i=1}^{\lfloor\frac{n}{3}\rfloor} \lfloor\frac{n-i}{2}\rfloor-i+1)$ And it is seen that the identity holds for each cases where $n\equiv 0,1,2,4,5\pmod6$ thus statement is true.

However i think there should be more general and less repetitive approach for this which i can't do.

Ideas?

Answer 1

$P(n,k)$ is the number of partitions of $n$ into exactly $k$ parts. (It is also the number of partitions of $n$ into any number of parts with greatest part equal to $k$; also, for $n\ge k$, the number of partitions of $n-k$ into parts of size at most $k$.)

$P(n,3)$ is OEIS sequence A069905.

You are probably familiar with the identity $$P(n,k)=P(n-1,k-1)+P(n-k,k)\quad\quad(n\ge k\ge1);\tag1$$ if not, observe that $P(n-1,k-1)$ is the number of partitions of $n$ into $k$ parts with least part equal to $1$, and $P(n-k,k)$ is the number of partitions of $n$ into $k$ parts with least part greater than $1$. We need this for $k=3$: $$P(n,3)=P(n-1,2)+P(n-3,3)\quad\quad(n\ge3)\tag2.$$ Since $P(n,2)=\left\lfloor\frac n2\right\rfloor$, we can rewrite $(2)$ as $$P(n,3)=\left\lfloor\frac{n-1}2\right\rfloor+P(n-3,3)\quad\quad(n\ge3).\tag3$$ Applying $(3)$ twice, we get $$P(n,3)=\left\lfloor\frac{n-1}2\right\rfloor+\left\lfloor\frac{n-4}2\right\rfloor+P(n-6,3)\quad\quad(n\ge6).\tag4$$ Since $$\left\lfloor\frac{n-1}2\right\rfloor+\left\lfloor\frac{n-4}2\right\rfloor=\begin{cases}\frac{n-2}2+\frac{n-4}2=n-3\quad\text{ if }n\text{ is even },\\ \frac{n-1}2+\frac{n-5}2=n-3\quad\text{ if }n\text{ is odd }, \end{cases}$$ we can rewrite $(4)$ as $$P(n,3)=P(n-6,3)+n-3\quad\quad(n\ge6).\tag5$$ Hence, if we suppose that $n\ge6$ and $$P(n-6,3)=\left\lfloor\frac{(n-6)^2}{12}\right\rfloor=\left\lfloor\frac{n^2-12n+36}{12}\right\rfloor=\left\lfloor\frac{n^2}{12}\right\rfloor-n+3,$$ it follows by $(5)$ that $$P(n,3)=P(n-6,3)+n-3=\left\lfloor\frac{n^2}{12}\right\rfloor.$$ Since the equality $P(n,3)=\left\lfloor\frac{n^2}{12}\right\rfloor$ holds for the base cases $n=0,1,2,4,5$, it follows by induction that it holds whenever $n\not\equiv3\pmod6$.

Remark. In the same way, we can show that the identity $$P(n,3)=\left\lfloor\frac{n^2+3}{12}\right\rfloor$$ holds for all $n$ without exception.

Answer 2

A slightly simpler method with three cases:

All three same: $x=1$ for $0 \pmod 6$ and $x=0$ for $1,2,4,5 \pmod 6$

Two same: $y=\lfloor {n-1\over 2} \rfloor$

All different: $z={{n-1 \choose 2} - x - 3y \over 6} = {n^2-3n+2-2x\over 12} - \lfloor {n-1\over 4} \rfloor$

Now count the total: $x+y+z = {n^2-3n+2+10x\over 12} + \lfloor {n-1\over 4} \rfloor= {n^2-3n+2+10x\over 12} + \lfloor {3n-3\over 12} \rfloor = \lfloor {n^2+10x-1\over 12} \rfloor$

For $0 \pmod 6$: $\lfloor {n^2+10x-1\over 12} \rfloor = \lfloor {n^2+9\over 12} \rfloor$, However since $12\mid n^2$ and $9<12$, this is same as $\lfloor {n^2\over 12} \rfloor$

For $1,2,4,5\pmod 6$ : $\lfloor {n^2+10x-1\over 12} \rfloor =\lfloor {n^2-1\over 12} \rfloor $. Since $12 \nmid n^2$ this is also equal to $\lfloor {n^2\over 12} \rfloor$.