Proof of stars and bars by a bijection with subsets

Proof

We match the multisets with the solutions, and the solutions with subsets of positions of the bars. Let $X$ be the $n$-element set and put $N = n + k - 1$.

1. Fix a bijection $i \mapsto e_i$ from $\set{1, \dots, n}$ to $X$.
2. A multiset of size $k$ on $X$ is a function $\mu : X \to \N$ with $\sum_{x \in X} \mu(x) = k$. Send it to the tuple $(\mu(e_1), \dots, \mu(e_n))$.
3. This tuple solves $x_1 + \dots + x_n = k$ in natural numbers, since the sum over $X$ is the sum over the $e_i$.
4. Conversely, a solution $(x_1, \dots, x_n)$ gives the multiset $e_i \mapsto x_i$. The two maps are mutually inverse. So multisets and solutions are equinumerous.
5. Let $S$ be the set of solutions. For $(x_1, \dots, x_n) \in S$, put $p_0 = 0$ and $p_j = x_1 + \dots + x_j + j$ for $1 \le j \le n$.
6. Then $p_j - p_{j-1} = x_j + 1 \ge 1$ for $1 \le j \le n$, so $p_0 < p_1 < \dots < p_n$. Also $p_n = k + n = N + 1$.
7. Hence $p_1, \dots, p_{n-1}$ are $n - 1$ distinct elements of $\set{1, \dots, N}$. Let $\beta(x_1, \dots, x_n)$ be the set $\set{p_1, \dots, p_{n-1}}$.
8. Conversely, let $T \subseteq \set{1, \dots, N}$ have $n - 1$ elements. List them in increasing order as $q_1 < \dots < q_{n-1}$, and put $q_0 = 0$ and $q_n = N + 1$.
9. Put $x_j = q_j - q_{j-1} - 1$ for $1 \le j \le n$. Each $x_j \ge 0$ because $q_{j-1} < q_j$.
10. The sum telescopes: $x_1 + \dots + x_n = q_n - q_0 - n = N + 1 - n = k$. So $\gamma(T) = (x_1, \dots, x_n)$ lies in $S$.
11. For this solution, $x_1 + \dots + x_j + j = q_j - q_0 = q_j$ for every $j$. So $\beta(\gamma(T)) = T$.
12. Starting from a solution, the list of step 6 is the increasing listing of $\beta(x_1, \dots, x_n)$. Step 9 then returns $x_j = p_j - p_{j-1} - 1$. So $\gamma(\beta(x_1, \dots, x_n)) = (x_1, \dots, x_n)$.
13. By the inverse criterion, $\beta$ is a bijection from $S$ to the set of $(n-1)$-element subsets of $\set{1, \dots, N}$.
14. By the number of $k$-element subsets, there are $\binom{N}{n-1}$ such subsets. Numbering them and composing with $\gamma$ gives $|S| = \binom{N}{n-1}$, as in the bijection principle.
15. Since $n \ge 1$ and $k \ge 0$, we have $n - 1 \le N$ and $N - (n - 1) = k$. By the symmetry of binomial coefficients, $\binom{N}{n-1} = \binom{N}{k}$.
16. By step 4, the number of multisets of size $k$ on $X$ is also $\binom{n + k - 1}{k}$.