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

1 Answers 1

1

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.

  • 1
    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$.2012-01-18