2
$\begingroup$

Two Integer Partition Problems

Let $P(n,k,m)$ be the number of partitions of $n$ into $k$ parts with all parts $\leq m$.

So $P(10,3,4) = 2$, i.e., (4,4,2); (4,3,3).

I need help proving the following:

$P(2n,3,n-1) = P(2n-3,3, n-2)$
$P(4n+3, 3, 2n+1) = P(4n,3,2n-1) + n + 1$.

$\endgroup$
1
$\begingroup$

For the first one: For any partition $2n=a+b+c$ where $a,b,c \leq n-1$, we have a partition $2n-3=(a-1)+(b-1)+(c-1)$ where $a-1,b-1,c-1 \leq n-2$ and vice versa.

$\endgroup$
  • 1
    $\begingroup$ To do this you also have to show that $c$ (the smallest part of $2n$) is at least $2$, so that $c-1$ is positive. This is not difficult as $c= n- (a+b) \ge n-((n-1)+(n-1))=2$. $\endgroup$ – Henry Jan 18 '12 at 17:40

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.