A partition of $n$ is a sequence of integers $(a_1, a_2, \dots, a_k)$ such that $a_i\geq 0$ for each $i$, and $\displaystyle\sum_{i=1}^k a_i = n$. The number $k$ is called the number of parts of the partition.
a) Let $S(n, k)$ denote the set of partitions of $n$ into $k$ parts. Calculate $|S(n, k)|$ for at least 4 different choices of $(n, k)$. Make sure to use both differing $n$ values and differing $k$ values.
b) Find a bijection between ${[n+k-1]\choose k-1}$ and $S(n, k)$. Conclude that $|S(n, k)|={n+k-1\choose k-1}$
For part a, I listed the following:
- $n = 0, k = 0$. Then $S(n,k) = \emptyset$ and $|S(n,k)| = 0$.
- $n = 1, k = 1$. Then $S(n,k) = \{ (1) \}$ and $|S(n,k)| = 1$.
- $n = 3, k = 2$. Then $S(n,k) = \{ (0,3), (1,2), (2,1), (3,0) \}$ and $|S(n,k)| = 4$.
- $n = 4, k = 3$. Then $S(n,k) = \{ (0,0,4), (0,4,0), (4,0,0), (0,1,3), (0,3,1), (1,0,3), (3,0,1), (1,3,0), (3,1,0), (0,2,2), (2,0,2), (2,2,0), (1,1,2), (1,2,1), (2,1,1) \}$ and $|S(n,k)| = 15$.
First, did I miss any tuples?
Second, for part b I'm not really sure how to proceed at all, but I suppose it should involve a bijection. I wrote down that ${n+k-1\choose k-1} = \frac{(n+k-1)!}{(k-1)!n!}$, but don't really know how to simplify it or relate it to the bijection.