Counting: the four cases, and how to tell them apart

Almost every counting question in an interview is one of four standard cases, and almost every wrong answer comes from picking the wrong one. Decide two things — does order matter, and can items repeat — and the formula follows.

Repetition	Order matters	Order does not
No repetition	$\dfrac{n!}{(n-k)!}$	$\dbinom{n}{k}$
Repetition allowed	$n^k$	$\dbinom{n+k-1}{k}$

Table 1.1 · The four cases. The bottom-right entry is stars and bars, and it is the one candidates forget exists. It counts multisets: how many ways to choose

k

items from

n

types when you may take several of a type.

Equation 1.2

The binomial coefficient

The number of ways to choose $k$ items from $n$ when order does not matter.

\binom{n}{k} = \frac{n!}{k!\,(n-k)!}

$\binom{n}{k} = \binom{n}{n-k}$: Choosing what to take is the same as choosing what to leave.
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$: Pascal: condition on whether the first item is taken.

Proposition 1.3

The identities worth knowing

Three come up repeatedly. The hockey-stick identity sums a column of Pascal’s triangle. Vandermonde’s identity splits a choice across two groups. And the committee-and-chair argument, $k\binom{n}{k} = n\binom{n-1}{k-1}$ , is the cleanest example of the double-counting technique: count the same thing two ways and equate.

Holds when

Hockey stick: $\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}$ .
Vandermonde: $\sum_{i}\binom{m}{i}\binom{n}{k-i} = \binom{m+n}{k}$ .
Double counting is usually a cleaner proof than algebra, and it is what an interviewer wants to see.

Derivation 1.4

Stars and bars

How many ways can $k$ identical items be distributed among $n$ distinct boxes?

$\underbrace{\star\star}_{\text{box 1}} \mid \underbrace{\ }_{\text{box 2}} \mid \underbrace{\star}_{\text{box 3}}$
Write the items as stars and the dividers between boxes as bars.
$k \text{ stars and } n-1 \text{ bars, in a row}$
Every arrangement corresponds to exactly one distribution.
$\text{choose which } k \text{ of the } n+k-1 \text{ positions are stars}$

\binom{n+k-1}{k}

Example 1.5

You buy 10 identical lots and must allocate them across 4 accounts, with empty accounts allowed. How many allocations are there?

Show the worked solutionHide the worked solution

Worked solution

Formula $\binom{n+k-1}{k}$
Substitute $n = 4 \text{ accounts},\ k = 10 \text{ lots}$
Solve $= \binom{13}{10} = \binom{13}{3}$
$= \frac{13 \times 12 \times 11}{6}$
Answer $286$

Sanity check. If empty accounts were forbidden, put one lot in each first and distribute the remaining 6, giving $\binom{9}{6} = 84$ — a useful check that the constraint changes the count in the right direction.

Counting: the four cases, and how to tell them apart

After this lesson you should be able to

The binomial coefficient

The identities worth knowing

Stars and bars

The rest of this lesson is in Premium