Suppose $p_k(n)$ is the number of partitions of the integer $n$ into $k$ parts. For example, the partition of 5 into 2 parts is; $p_2(5) = 2$, since the partitions are (4,1) and (3,2).

What is a good combinatorial proof that $p_k(n) \leq (n-k+1)^{k-1}$ for $k \leq n$? Or must this be done algebraically?

  • $\begingroup$ what's $p_k(n)$? $\endgroup$ – Phicar Sep 21 '17 at 4:16
  • $\begingroup$ Updated the question to include the definition. $\endgroup$ – bashmike Sep 21 '17 at 4:20
  • $\begingroup$ $p_k(n)$ is the Stirling number of second kind. $\endgroup$ – GAVD Sep 21 '17 at 4:35
  • 1
    $\begingroup$ @GAVD No, it isn't. The Stirling number of the second kind counts partitions of sets, $p_k(n)$ counts partitions of numbers. $\endgroup$ – bof Sep 21 '17 at 5:43

Here is an extremely straightforward way to see this:

A $k$-partition of $n$ is uniquely determined by the first $k-1$ values. Each element of a $k$-partition must be at most $n-k+1$, since the other elements are positive integers and sum to $\ge k-1$. Therefore the number of partitions of $n$ into $k$ parts is no larger than the number of $(k-1)$-tuples of integers between $1$ and $n-k+1$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.