Counting: does order matter?
Most probability questions are counting questions in disguise. The one decision that matters is whether swapping two of the chosen things gives a different outcome.
- Count committees with n choose k and ordered picks with n × (n − 1) × …
- Find the chance a named person is chosen without counting anything
- Count every pair: round-robin matches, handshakes, and the number of teams from the number of matches
- Seat people at a round table by fixing one of them first
The intuition
Pick three of ten traders for a dinner. If you pick them one at a time there are 10 × 9 × 8 = 720 ways, but the dinner does not care who was named first: every group of three was counted 3! = 6 times, once for each order. Divide it back out and there are 120 groups. That division is the whole difference between permutations (order counts) and combinations (it does not).
Once the outcomes are counted, probabilities are ratios of counts, and often you do not even need the counts. A random group of three from ten contains any particular person with probability 3 ÷ 10, by symmetry: three seats, ten equally likely people per seat. Two particular people are both in it with probability (3 × 2) ÷ (10 × 9). Fix one person and count the rest, or count the complement, and most 'hard' counting questions become one line.
C(n, k) = n! ÷ (k! (n − k)!) counts unordered groups; multiply by k! when order matters. P(a named person is chosen) = k ÷ n. P(two named people are both chosen) = k(k − 1) ÷ (n(n − 1)). Every pair among n: C(n, 2) = n(n − 1) ÷ 2. Two named people are neighbors at a round table of n with probability 2 ÷ (n − 1).
Why it works
- The conventions here: a group of k is drawn uniformly from n distinct people without replacement. Round-table seatings treat rotations as the same seating. A round-robin league of n teams plays every pair once.
- Ordered first, then divide. Picking k people in order gives n × (n − 1) × … (k factors) outcomes. Each unordered group appears k! times in that list, so C(n, k) = ordered ÷ k!.
- Symmetry beats counting. No person is more likely than any other to be chosen, and the chances add up to k (the number chosen), so each person's chance is k ÷ n. For two named people, multiply k ÷ n by (k − 1) ÷ (n − 1): the second seat is drawn from one fewer person.
- Selections without replacement are negatively correlated. Knowing one named person is in the group makes the other slightly less likely: (k − 1) ÷ (n − 1) is below k ÷ n.
- Every pair is C(n, 2). Matches in a league, handshakes at a meeting, correlations in a covariance matrix. It is quadratic: doubling n roughly quadruples the pairs. Run backwards, n = (1 + √(1 + 8 × pairs)) ÷ 2.
- Round tables: fix one person. Rotations are the same seating, so seat one of the two anywhere; the other has n − 1 equally likely seats and two of them are adjacent.
| Ordered picks: 10 × 9 × 8 | 720 |
| Groups: 720 ÷ 3! | 120 |
| P(the newest hire goes): 3 ÷ 10 | 30% |
| P(two named traders both go): (3 × 2) ÷ (10 × 9) | 6.67% |
| P(neither goes): C(8, 3) ÷ 120 = 56 ÷ 120 | 46.67% |
| Round-robin matches among 10 teams: C(10, 2) | 45 |
At a round table of 10, two named people sit together with probability 2 ÷ 9 = 22.22%. In a straight row it is 2 ÷ 10 = 20%, because the two end seats have only one neighbor.
The formulas
Unordered groups; multiply by k! when order matters.
By symmetry: k seats, every person equally likely in each.
The second seat is drawn from one fewer person.
Matches, handshakes; and how to get n back from the count.
Fix one person; two of the other n − 1 seats are adjacent.
Worked example
Count the ordered picks first, then divide by the number of orders each group was counted in. The follow-up shows why choosing who goes is the same as choosing who stays.
See it move
Same desk. Change how many traders there are and how many are chosen.
- Add traders to the desk. The number of groups rises, the chances that a named person or both of two named people are chosen fall, and the number of pairs rises as a square.
- Choose more of them. The chance a named person goes rises with k ÷ n, the chance that both of two named people go rises faster, and the chance that neither goes falls.
- Watch the ordered picks against the groups. The gap between them is k!, and it grows with every extra seat.
Run it backwards
A league played a known number of matches, every pair once. How many teams were there?
Matches = n(n − 1) ÷ 2 is a quadratic in n. Solve it, or try small n: the positive root is (1 + √(1 + 8 × matches)) ÷ 2, and it must come out as a whole number.
The follow-up is the same structure in another costume: handshakes at a meeting.
Traps
Say it in the interview
“Ten of us, three go to the dinner. How many groups, and what is the chance I go?”
Check yourself
5 fresh questions, with new numbers. Answer each one correctly to finish the chapter. Get one wrong and you will see the full working, then you can try it again with new numbers.
Answers within 1% are marked right. Type the number; $, %, x and M are fine. First tries count toward Learned: the topic is Learned once every chapter is done and 75% of first tries were right.
- C(n, k) = ordered picks ÷ k!; multiply back by k! when order matters.
- A named person is chosen with probability k ÷ n; two named people with k(k − 1) ÷ (n(n − 1)).
- Every pair among n is n(n − 1) ÷ 2, and it runs backwards through a quadratic.
- Round table: fix one person, then 2 ÷ (n − 1).