Counting and symmetry

A quant phone screen often opens with a short setup about picking people, flipping coins or assigning jobs, followed by "what's the probability that...". Most of these are counting problems. The interviewer is listening for two things: whether the top and bottom of your fraction count the same kind of outcome, and whether you spot the shortcut that removes most of the counting. By the end of this lesson you will be able to set up a count in one line, turn "at least one" into "none", correct for overlapping cases, and use symmetry to get an answer without counting at all.

Decide what one outcome is

When every outcome is equally likely, a probability is the number of favorable outcomes divided by the number of all outcomes. Before counting anything, decide what one outcome is, and use that same definition for the top and the bottom of the fraction.

A few tools do most of the work:

• Product rule. If a choice happens in stages, with a ways to make the first and b ways to make the second whatever the first was, there are a × b ways to make both.

• Permutation: an ordering. n distinct items can be lined up in n! = n × (n - 1) × ... × 1 ways.

• Combination: a group with no order. C(n, k), read "n choose k", counts the groups of k items you can take from n. It equals the number of ordered picks divided by k!, since each group can be picked in k! orders.

The bottom-right cell is a trap. Flip two fair coins and list the unordered results: two heads, two tails, one of each. "One of each" has probability 1/2, not 1/3, because it covers two ordered outcomes, HT and TH.

Worked example. A team of 12 analysts includes 5 women. Three are picked at random for an on-call rotation. What is the probability that all three are women?

• In order: 5 × 4 × 3 = 60 ordered picks of three women, out of 12 × 11 × 10 = 1,320 ordered picks in total. 60/1,320 = 1/22.

• As groups: C(5, 3) = 10 all-women groups, out of C(12, 3) = 220 groups. 10/220 = 1/22.

The two routes agree because each one counts a single kind of outcome, top and bottom.

"I'll count unordered groups of three. There are C(12, 3) = 220 equally likely groups, and C(5, 3) = 10 of them are all women, so it's 10/220, which is 1/22, about 4.5%."

The mistake the interviewer is watching for is a numerator counted as groups over a denominator counted as sequences: C(5, 3)/(12 × 11 × 10) = 10/1,320 = 1/132. That is too small by exactly 3! = 6, the number of orders of each group. When an answer is off by a factorial, look for this first.

Which one should you count? Count in order when the story happens in steps, such as draws one after another, and you may need to condition on an early step. Count groups when only the final set matters. Ordered outcomes are the safer default, because a process that picks uniformly at each step makes every ordered outcome equally likely.

Replacement changes the answer. Suppose instead a random analyst covers each of three weeks, and the same person can be picked again. Each week is a woman with probability 5/12 whatever happened before, so the probability is (5/12)^3 = 125/1,728, about 7.2%. Counting gives the same thing: there are 12^3 = 1,728 equally likely ordered picks, and 5^3 = 125 of them are all women. That beats 4.5% because picking a woman does not use her up.

Turn "at least one" into "none"

"At least one" covers many cases: one woman on the rotation, two, or three. Its opposite, the complement, covers a single case: none. An event and its complement have probabilities that add to 1, so

P(at least one) = 1 - P(none).

For the rotation, "no women" means all three come from the 7 men: C(7, 3) = 35 groups. So P(at least one woman) = 1 - 35/220 = 185/220, about 84.1%.

The direct count most people try first goes wrong. "Pick a woman to guarantee one (5 ways), then any two of the other 11 (C(11, 2) = 55 ways)" gives 5 × 55 = 275 groups, but only 220 groups exist. A group with two women was counted twice, once for each woman who could be "the guaranteed one", and a group with three women was counted three times. Any time your count of favorable outcomes beats the count of all outcomes, something was counted more than once. A count below the total can still be an overcount, so the complement is the safer route.

The complement works with independent trials too, where probabilities multiply. A nightly pipeline runs 6 jobs, and each fails with probability 5%, independently of the others. Then P(no failures) = 0.95^6 ≈ 0.735, so P(at least one failure) ≈ 26.5%. Sanity check: six chances to fail should land well above 5%, and below 6 × 5% = 30%, since simply adding counts the nights with two or more failures more than once.

Words that should send you to the complement: "at least", "at most", "some", "not all". "At most two women" on the rotation, for instance, is everything except the all-women case: 1 - 1/22 = 21/22, about 95.5%.

Correct for overlaps with inclusion and exclusion

To count outcomes in A or B (or both), add the two and subtract the overlap, which you counted twice:

P(A or B) = P(A) + P(B) - P(A and B).

If 40% of weekly users used search, 30% used filters and 15% used both, then 40 + 30 - 15 = 55% used at least one, and 45% used neither.

With three events, add the singles, subtract the pairs, then add back the triple, which the pairs took away once too often:

P(A or B or C) = (sum of singles) - (sum of pairs) + (triple).

Worked example. Six jobs are each sent to one of 3 servers, chosen uniformly at random and independently. What is the probability that every server gets at least one job? This is another "at least" question, so take the complement: some server sits idle. Then apply inclusion and exclusion to the three events "server 1 idle", "server 2 idle" and "server 3 idle":

1. One named server idle: every job goes to the other two, (2/3)^6 = 64/729. There are three such terms.

2. Two named servers idle: every job goes to the third, (1/3)^6 = 1/729. There are three such pairs.

3. All three idle: impossible, so 0.

4. P(some server idle) = 3 × 64/729 - 3 × 1/729 + 0 = 189/729 = 7/27.

5. P(every server busy) = 1 - 7/27 = 20/27, about 74.1%.

Stopping after line 1 gives 192/729 for "some server idle", which counts every run with two idle servers twice.

A short simulation confirms it. On a shared screen or a take-home, it is the quickest check you can show:

import numpy as np

rng = np.random.default_rng(7)
jobs = rng.integers(0, 3, size=(200_000, 6))  # each row: the server for each of 6 jobs
every_server_busy = np.ones(len(jobs), dtype=bool)
for server in range(3):
    every_server_busy &= (jobs == server).any(axis=1)
print(every_server_busy.mean())  # close to 20/27, about 0.741

Let symmetry replace the count

A symmetry argument works like this: if swapping two labels leaves the setup unchanged, then outcomes that differ only by that swap are equally likely. Often that gives the answer with no counting.

Ten people, including Ana and Ben, line up in random order. What is the probability that Ana is somewhere ahead of Ben? Counting means wading through 10! = 3,628,800 lineups. Instead, pair each lineup with the one where Ana and Ben trade places and everyone else stays put. Each pair holds exactly one lineup with Ana ahead, and the two lineups in a pair are equally likely, so the answer is 1/2. The other eight people never enter the argument.

Symmetry handles ties if you set them aside first. Flip a fair coin 10 times. What is the probability of more heads than tails? Swapping the words "heads" and "tails" turns each sequence with more heads into one with more tails, at the same probability, so those two events are equally likely. Together they miss one case, the 5 to 5 tie, which has probability C(10, 5)/2^10 = 252/1,024. So

P(more heads) = (1 - 252/1,024)/2 = 386/1,024, about 37.7%.

Check by counting: the sequences with 6 or more heads number 210 + 120 + 45 + 10 + 1 = 386. With 9 flips a tie is impossible, and the answer is exactly 1/2.

Symmetry needs a reason. A biased coin breaks the swap between heads and tails, and if Ana always arrives early, the lineup is not random. Say what makes the labels interchangeable before you rely on it; that sentence is the first thing to defend if the interviewer pushes back.

Practicing with the questions on this page

The wording of a question usually points to the tool:

Work each question on paper, out loud, against a 10-minute timer. Before any arithmetic, say what one outcome is and whether order matters. When you have a number, test it: it must sit between 0 and 1, it should move the right way when you change an input, and a short simulation should agree with it. Then look for a second route, a complement or a symmetry, and see whether it lands on the same answer. Two routes that agree are the strongest thing you can put on a whiteboard.

The next lesson, conditional probability and Bayes' rule, uses these counts when something is revealed partway through an experiment.