Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

Your Answer

 
discard

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