---
tag: KB70806JGH
kind: proof
name: Proof of stars and bars by a bijection with subsets
msc: [05A10]
proves: 009TEMTQKH
uses: [0YEQG3VBYC, 0SNQEF7Z53, 0GV2573FP4, 0BFMR2FQ8B, 0R7JS3DP3W, 01VG2A0BHW]
sources:
  - url: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
    locator: Theorem two
---

## 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|0SNQEF7Z53]] $i \mapsto e_i$ from $\set{1, \dots, n}$ to $X$.
2. A [[multiset of size $k$|0YEQG3VBYC]] 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|01VG2A0BHW]], $\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|0BFMR2FQ8B]], 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|0GV2573FP4]].
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|0R7JS3DP3W]], $\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}$.

## Idea

Write a solution as a row of $k$ stars, split into $n$ groups by $n - 1$ bars.
The row has $n + k - 1$ places, and the solution is determined by which places hold bars.
So solutions match subsets of $n - 1$ places, and there are $\binom{n+k-1}{n-1} = \binom{n+k-1}{k}$ of them.