2
$\begingroup$

Recent news piqued my interest in integer partitions again. I'm working my way back through an old text and I'm completely hung up on this problem:


Recall that $p_k(n)$ is the number of partitions of $n$ into exactly $k$ parts. Prove that for all positive integers $k\leq n$, the inequality $p_k(n) \leq (n-k+1)^{k-1}$ holds.

$\endgroup$
  • $\begingroup$ There is a lower bound of $\binom{n-1}{k-1} / k!$ which is quite good for large $n$ and small $k$. It comes from unordering compositions. $\endgroup$ – Henry Feb 25 '11 at 0:46
3
$\begingroup$

Each of the $k$ parts must have a minimum of 1 item, leaving $n-k$ to distribute into the $k$ bins. When you choose how many to put in the first $k-1$ bins, the number going into the last bin is fixed. So you have $k-1$ choices, each of which is within the range $[0,n-k]$, so there are $n-k+1$ of them. This is a generous upper bound.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy