# Upper bound on integer partitions of n into k parts

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.

-
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. –  Henry Feb 25 '11 at 0:46

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.