Basic, lesson 1 of 3
Counting without double counting
Most wrong probability answers are wrong counts. Four tools cover almost every interview: ordered or not, repeated letters, stars and bars, and inclusion and exclusion.
10 min, 3 checks
1Ordered or unordered
Before counting anything, decide whether order matters. Picking a president, a treasurer, and a secretary from 10 people is ordered: 10 x 9 x 8 = 720. Picking a committee of three is not: divide by the 3! = 6 orders of the same three people, so 120.
Ordered: n! / (n - k)! Unordered: n! / (k! x (n - k)!)
The unordered count is the ordered count divided by the k! ways to arrange the chosen items.
Repeated items work the same way. Arrange the letters of MISSISSIPPI: 11 letters, but swapping the four S's among themselves changes nothing, nor do the four I's or the two P's.
Worked example
Distinct arrangements of MISSISSIPPI
- 111 letters: one M, four I, four S, two P.
- 2All orders: 11! = 39,916,800.
- 3Divide by the swaps that change nothing: 4! x 4! x 2! = 24 x 24 x 2 = 1,152.
39,916,800 / 1,152 = 34,650 distinct words.
Check 1
How many distinct arrangements are there of the letters in LETTER?
2Stars and bars
How many ways can 10 identical chips go into 3 labeled boxes? Line up the 10 chips and drop 2 dividers among them. Every arrangement of 10 chips and 2 dividers is one split, so the count is the number of ways to place 2 dividers in 12 slots: 12 choose 2 = 66.
Non negative integer solutions of x1 + ... + xk = n: (n + k - 1) choose (k - 1)
If every box needs at least one, give each box one first and count the rest: (n - 1) choose (k - 1).
Check 2
How many solutions does x1 + x2 + x3 = 10 have in positive integers (each at least 1)?
3Inclusion and exclusion
When you count things with property A or B, the overlap gets counted twice. Add the singles, subtract the pairs, add back the triples.
Worked example
Integers from 1 to 100 divisible by 2, 3, or 5
- 1Singles: 50 (by 2) + 33 (by 3) + 20 (by 5) = 103.
- 2Pairs: 16 (by 6) + 10 (by 10) + 6 (by 15) = 32.
- 3Triple: 3 (by 30).
- 4103 - 32 + 3 = 74.
74 of the first 100 integers, so 26 are divisible by none of 2, 3, and 5.
Check 3
How many integers from 1 to 60 are divisible by 3 or by 4?
3 checks in this lesson. Sign in to keep your progress.