Counting: the four cases, and how to tell them apart
COMB · Chapter 112 min readAsked at Jane Street, Optiver, SIG, IMC
The lesson in a minute
The key idea, drawn and talked through, before you read. Captions are on, so it works with the sound off.
Read the transcript
You buy ten identical lots. You split them across four accounts, and an account can stay empty. How many ways can you do it? Pause and try it. Most people say four to the tenth. That's over a million. The real answer is two hundred and eighty-six. Four to the tenth picks an account for every lot, as if each lot had a name. But the lots are identical. All that matters is how many land in each account. So draw the lots as ten stars. Add three bars to cut them into four accounts. Here that's three, two, four and one. Two bars side by side? That's just an empty account. Now it's thirteen symbols in a row, and a split is just a choice of which three spots hold the bars. Thirteen choose three is two hundred and eighty-six. Every counting question sits in one of four boxes. Ask two things. Does order matter? Can things repeat? Identical lots into accounts is this corner: no order, repeats allowed. It's the one people forget. Before you count anything, ask: does order matter, and can things repeat? The full lesson is right below.
After this lesson you should be able to
- Classify a counting problem by order and replacement.
- Use stars and bars for identical objects.
- Spot when a "count" question is really a probability question.
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 | ||
| Repetition allowed |
Equation 1.2
The binomial coefficient
The number of ways to choose items from when order does not matter.
- Choosing what to take is the same as choosing what to leave.
- 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, , is the cleanest example of the double-counting technique: count the same thing two ways and equate.
Holds when
- Hockey stick: .
- Vandermonde: .
- 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 identical items be distributed among distinct boxes?
Write the items as stars and the dividers between boxes as bars.
Every arrangement corresponds to exactly one distribution.
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
- Substitute
- Solve
- Answer
Sanity check. If empty accounts were forbidden, put one lot in each first and distribute the remaining 6, giving – a useful check that the constraint changes the count in the right direction.
The rest of this lesson is in Premium
You have read the opening. 13 more sections follow, including 5 worked examples and 3 quick checks.
Nothing is charged for 7 days, and you can cancel before then. Not ready for a trial? A free account, with no card, saves your progress and opens the free questions, the drills and a mock paper. Or read Arithmetic that survives a clock in full, free.