Counting: rules, choices and bijections

Two rules carry most of counting. The sum rule: if a choice can be made in one of several disjoint ways, the counts add. The product rule: if a choice is a sequence of steps, and step \( i \) can be done in \( n_i \) ways whatever happened before, the counts multiply. A licence plate of three letters then three digits can be filled in \( 26^3 \cdot 10^3 \) ways. The number of arrangements of \( k \) of \( n \) distinct objects in order is \( n(n-1)\cdots(n-k+1) = n!/(n-k)! \).

When order does not matter, each unordered selection has been counted once for every one of its \( k! \) orderings, so the number of combinations is \[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!}. \] The example chooses 3 from 10 in \( \binom{10}{3} = 120 \) ways. Dividing out an overcount like this is a basic technique: if every object of interest is counted exactly \( d \) times, divide the total by \( d \).

A bijective proof counts a set by pairing its elements perfectly with those of a set already counted. Choosing which 3 of 10 people are on a committee is the same as choosing which 7 are not, so \( \binom{10}{3} = \binom{10}{7} \). Subsets of an \( n \)-element set correspond to binary strings of length \( n \) (a 1 in position \( i \) means element \( i \) is in), so there are \( 2^n \) of them. And the number of ways to write \( n \) as an ordered sum of \( k \) non-negative integers, \( x_1 + \dots + x_k = n \), matches arrangements of \( n \) stars and \( k - 1 \) bars in a row, which gives stars and bars: \( \binom{n + k - 1}{k - 1} \) solutions.

Double counting is the sibling technique: count one set in two different ways and equate the answers. Counting pairs (a committee of \( k \) from \( n \) people, a chair within it) first by committee then by chair gives \( k\binom{n}{k} = n\binom{n-1}{k-1} \). Counting all subsets by size gives \( \sum_k \binom{n}{k} = 2^n \).

Picture it: lay out the objects to be counted in a grid, one row per first choice and one column per second choice: the product rule is the area of the rectangle. A bijection is a set of strings tying each object in one pile to exactly one object in another, with none left over on either side.

Think it: before multiplying, ask whether order matters and whether repetition is allowed; the four answers give \( n^k \), \( n!/(n-k)! \), \( \binom{n}{k} \) and \( \binom{n+k-1}{k} \). When a direct count is awkward, count the complement, or find a bijection to something easier.