Counting by Bijection

How many ways are there to place 5 identical balls into 3 distinct boxes?

Try it directly first — you'll likely start listing cases (5-0-0, 4-1-0, 3-2-0, ...) and it gets tedious fast, with lots of room to miss a case or double-count one. There's a cleaner way that sidesteps the listing entirely.

The idea: count something else instead

A bijection is a pairing between two collections where every item in the first matches exactly one item in the second, and vice versa — nothing left over on either side. If you can build such a pairing between your hard-to-count objects and some easy-to-count objects, the counts must be identical, because the pairing itself proves it item by item. You never touch the original messy pile again; you just count the tidy one.

The stars-and-bars bijection

For balls-in-boxes, the standard bijection is stars and bars. Represent 5 identical balls as 5 stars: $\star\star\star\star\star$. To split them among 3 boxes, insert 2 dividers ("bars") among the stars — 2 bars because 3 boxes need 2 walls to separate them. For instance:

$\star\star \, | \, \star \, | \, \star\star \quad \longleftrightarrow \quad \text{box 1: 2, box 2: 1, box 3: 2}$

Every arrangement of 5 stars and 2 bars in a row corresponds to exactly one way of splitting the balls, and every split corresponds to exactly one star-bar arrangement — that's the bijection, and it's obviously reversible in both directions. So the question "how many ways to split 5 balls into 3 boxes" becomes "how many ways to arrange a row of 5 stars and 2 bars," which is just: choose which 2 of the 7 total symbols are bars (the rest are automatically stars).

$\binom{7}{2} = \frac{7 \times 6}{2} = 21$

Answer: 21 ways. Compare that to listing every case (5-0-0 and its 3 orderings, 4-1-0 and its 6 orderings, 3-2-0 and its 6 orderings, 3-1-1 and its 3 orderings, 2-2-1 and its 3 orderings — $3+6+6+3+3 = 21$): it checks out, but the bijection got there without any of that bookkeeping.

A second example: handshakes at a party

20 people are at a party. Everyone shakes hands with everyone else exactly once. How many handshakes happen?

A handshake is fully described by which two people are involved — order doesn't matter, "Alice shakes Bob" is the same handshake as "Bob shakes Alice." So handshakes are in exact bijection with unordered pairs of the 20 people. Counting unordered pairs: pick a first person (20 ways) and a second (19 remaining ways), giving 380 ordered picks, but each unordered pair got counted twice (once as A-then-B, once as B-then-A), so divide by 2:

$\binom{20}{2} = \frac{20 \times 19}{2} = \textbf{190 handshakes}$

The bijection here is simple but easy to skip past: recognizing that "count the handshakes" is identical to "count the 2-element subsets of a 20-element set" is what turns a story problem into a formula you already have memorized.

Where this generalizes

The stars-and-bars bijection extends immediately to counting non-negative integer solutions of $x_1 + x_2 + \cdots + x_k = n$ (it's the identical picture: $n$ stars, $k-1$ bars), which is the combinatorial engine behind counting lattice paths, distributing indistinguishable trades across distinguishable accounts, or splitting a fixed budget across categories. The broader habit — find a bijection to something countable — is the same instinct that turns hard geometry counts into binary-string counts, turns balanced-parenthesis counts into Catalan-number counts, and turns "how many ways" into "how many subsets," which is usually a formula you already know.