1
$\begingroup$

Quoting from Wolfram MathWorld, "$P(n,k)$ denotes the number of ways of writing $n$ as a sum of exactly $k$ terms or, equivalently, the number of partitions into parts of which the largest is exactly $k$."

Why are these two definitions equivalent? What is the mapping?

The page also states a recurrence,

$P(n,k)=P(n-1,k-1)+P(n-k,k)$

Why is this true?

1 Answers 1

2

For the first see Ferrers diagram in Wikipedia's article on partition function. For the second, the first term on the right is the number of ways to write $n$ as a sum of $k$ plus terms smaller than $k$, as if you reduce the $k$ term by 1 you have a way to write $n-1$ as terms with largest term $k-1$. The second term is the number of ways to write $n$ as a sum of terms with at least two terms $k$ and nothing larger.