# What is a combinatorial proof for $p_k(n) \leq (n-k+1)^{k-1}$

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?

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

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$.