0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Unless I misunderstood the question, $P(4,3)=0$ which is not $\lfloor\frac{4^2}{12}\rfloor$. $\endgroup$ – David Feb 18 at 6:02
  • $\begingroup$ You did misunerstand the question sir. $\endgroup$ – Solvable Potato Feb 18 at 6:05
  • $\begingroup$ So how do you write $4$ as a partition of $3$ positive integers? $\endgroup$ – David Feb 18 at 6:13
  • $\begingroup$ @David $$4=2+1+1$$ $\endgroup$ – bof Feb 18 at 6:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Solvable Potato Feb 18 at 7:18
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.