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

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?

• Unless I misunderstood the question, $P(4,3)=0$ which is not $\lfloor\frac{4^2}{12}\rfloor$. – David Feb 18 at 6:02
• You did misunerstand the question sir. – Solvable Potato Feb 18 at 6:05
• So how do you write $4$ as a partition of $3$ positive integers? – David Feb 18 at 6:13
• @David $$4=2+1+1$$ – bof Feb 18 at 6:51
• There i find my misleading definition. You should count distinct tuples not tuples of disinct positive integers. My appologies for wasting your time. I edited the wrong wording. – Solvable Potato Feb 18 at 7:18

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

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