Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.