Probability, lesson 1
Counting outcomes
Permutations and combinations: how many ways something can happen.
Every probability question starts with a count: how many ways can this happen, out of how many in all? This lesson is about the count. If you can multiply and divide, you have all the maths it needs.
By the end, you can:
Part 1. Choices made in stages
Count choices made in stages, such as filling seats in order.
Many counting questions are choices made one after another: a first pick, then a second, then a third. Start with the simplest one.
Example 1.1
Eight tiles, three slots
You have eight tiles, lettered A to H, and three slots in a row. You fill the slots left to right, and a tile you've used can't be used again. In how many different ways can the three slots end up?
- Fill the first slot8
Any of the 8 tiles can go first.
- Fill the second slot8 × 7 = 56
Whichever tile went first, 7 are left. Starting with A alone gives AB, AC, AD, AE, AF, AG and AH.
- Fill the third slot56 × 6 = 336
Each of the 56 pairs leaves 6 tiles for the last slot.
Answer336 ways.
Why multiply? Picture the choices as a tree. The first choice splits into 8 branches, each of those into 7, and each of those into 6. Every path from the root to a leaf is one way to fill the slots. So the count is the number of leaves, 8 × 7 × 6, and nobody has to list them.
The multiplication rule
When a choice happens in stages, and each stage has the same number of options whatever came before, the number of outcomes is the product of the options at each stage.
8 × 7 × 6 = 336
The rule asks for the same number of options at each stage. The options themselves can change, as the next example shows.
Example 1.2
Three-digit numbers with no repeated digit
How many three-digit numbers have no repeated digit? 507 and 981 count. 550 doesn't.
- First digit9
Anything but 0, so 9 options.
- Second digit9 × 9 = 81
0 is allowed now, but the first digit isn't. That's 9 options again, a different 9 each time.
- Third digit81 × 8 = 648
It avoids both digits already used.
Answer648 numbers.
If the number of options did change from branch to branch, multiplying would break. Then you count each branch on its own and add them up.
Before you multiply, also settle whether a choice can repeat. Tiles can't: a tile in the first slot isn't there for the second. Digits on a lock can, so every stage keeps all its options.
Your turn
A lock code is 4 digits from 0 to 9, and digits may repeat. How many codes are there?
Part 2. When order doesn't matter
Tell when order matters, and divide it out when it doesn't.
The 336 from part 1 counts ABC and CAB as different, because the slots are filled in a different order. Often you don't care about that. If the three tiles are a hand you hold, ABC and CAB are the same hand.
Example 2.1
Groups of three tiles
How many different groups of three can you take from the eight tiles, if order doesn't matter?
- Count the arrangements8 × 7 × 6 = 336
The answer from part 1, where order counted.
- Count the orders of one group3 × 2 × 1 = 6
A, B and C can sit as ABC, ACB, BAC, BCA, CAB or CBA.
- Divide out the repeats336 ÷ 6 = 56
Every group shows up in the 336 exactly 6 times.
Answer56 groups.
Permutation and combination
A permutation is an arrangement, where order matters. A combination is a group, where it doesn't. To count combinations, count the permutations, then divide by the number of orders of one group.
One test settles the order question. Swap two of your picks. If that gives a different outcome, order matters, and the product is your answer. If it gives the same outcome, divide by the number of orders.
Dividing works whenever every outcome was counted the same number of times. It works for letters too.
Example 2.2
The letters of LEVEL
How many different words can you make by rearranging the letters of LEVEL?
- Count the orders of five letters5 × 4 × 3 × 2 × 1 = 120
As if every letter were different.
- Count the repeats2 × 2 = 4
Swapping the two Ls gives the same word, and so does swapping the two Es.
- Divide120 ÷ 4 = 30
Each word was counted 4 times.
Answer30 words.
Your turn
From 10 people, how many ways can you pick a president, a secretary and a treasurer? And how many ways can you pick a committee of 3?
Part 3. The formula for groups
Count groups with the n choose k formula.
For the tiles you worked out (8 × 7 × 6) ÷ (3 × 2 × 1) = 56. Products that count down to 1, like 3 × 2 × 1, come up so often that they have a name. So does the whole calculation.
Factorial and n choose k
n!, read "n factorial", is n × (n − 1) × … × 1, so 3! = 6 and 5! = 120. The number of groups of k things from n is C(n, k), read "n choose k":
C(n, k) = n! / (k! × (n − k)!)
Read it for the tiles. 8 choose 3 is 8! / (3! × 5!). The 5! cancels most of the 8!, which leaves (8 × 7 × 6) / (3 × 2 × 1) = 56, the same answer. You never need 8! itself.
The formula also says C(8, 3) = C(8, 5). That makes sense: choosing the 3 tiles you take is the same as choosing the 5 you leave.
Example 3.1
Five cards from 52
How many different five-card hands can a 52-card deck deal?
- Deal the cards in order52 × 51 × 50 × 49 × 48 = 311,875,200
52 choices for the first card, 51 for the second, and so on.
- Count the orders of one hand5! = 120
A hand is the same hand whatever order it arrived in.
- Divide311,875,200 ÷ 120 = 2,598,960
This is C(52, 5).
Answer2,598,960 hands.
Your turn
How many different two-card hands can a 52-card deck deal?
Part 4. Counting poker hands
Count poker hands, a common first question in quant interviews.
Card questions are where many quant interviews start. After "how many hands?" comes "how many are a full house?": three cards of one rank and two of another, such as three kings and two sevens. Build the hand in stages and count each stage.
Example 4.1
Full houses
How many five-card hands are a full house?
- Rank of the three13
Any rank, ace to king.
- Suits of the threeC(4, 3) = 4
Choosing 3 suits of 4 is choosing the 1 to leave out.
- Rank of the pair12
Any rank but the one already used.
- Suits of the pairC(4, 2) = 6
Any 2 of the 4 suits.
- Multiply the stages13 × 4 × 12 × 6 = 3,744
Each stage has the same number of options whatever came before.
Answer3,744 full houses, about 1 hand in 694.
Notice the ranks came as 13 × 12, in order, and not as C(13, 2) = 78. Three kings and two sevens is a different hand from three sevens and two kings, because the two ranks do different jobs.
That's the trap in almost every card count: dividing when the roles differ, or not dividing when they're the same. Two pair is the opposite case.
Example 4.2
Two pair
How many hands are two pair, such as two kings, two sevens and one other card?
- Ranks of the pairs, as a groupC(13, 2) = 78
The two pairs do the same job, so swapping them gives the same hand.
- Suits of each pair6 × 6 = 36
C(4, 2) = 6 ways for each pair.
- The fifth card44
Any card from the other 11 ranks.
- Multiply the stages78 × 36 × 44 = 123,552
Using 13 × 12 for the ranks would count every hand twice and give 247,104.
Answer123,552 hands.
Your turn
A flush is five cards of one suit. How many five-card flushes are there, counting straight flushes too?
Where you'll meet it
Counting questions open many quant trading and research interviews: hands from a deck, seats at a table, paths across a grid. Before you multiply, answer two questions out loud. Does order matter? Can things repeat? A path that goes 3 steps right and 2 steps up is a choice of which 2 of its 5 moves go up: C(5, 2) = 10 paths.
A binomial tree, a standard model for pricing options, moves a price up or down one step at a time. After n steps, exactly C(n, k) paths end with k up moves. With 10 steps, 252 of the 1,024 paths end at 5 up and 5 down, and only 1 ends at 10 up. That's why the middle prices carry most of the weight.
from itertools import permutations
from math import comb, perm
print(perm(8, 3), comb(8, 3)) # 336 56
print(len(set(permutations("LEVEL")))) # 30
print(comb(52, 5)) # 2598960
full_house = 13 * comb(4, 3) * 12 * comb(4, 2)
two_pair = comb(13, 2) * comb(4, 2) ** 2 * 44
print(full_house, two_pair) # 3744 123552itertools lists every arrangement, which is a good way to check a formula on a small case. For 52 cards, trust the formula.
Check yourself
Three questions from across the lesson. Try each one before you look back.
1
Ten runners race. In how many ways can gold, silver and bronze be handed out?
2
A pizza place has 8 toppings. How many pizzas have exactly 3 different toppings?
3
A team needs 2 engineers out of 6 and 1 analyst out of 4. How many different teams are there?
What to remember
1Choices made in stages
When a choice happens in stages, and each stage has the same number of options, multiply the options: 8 × 7 × 6 = 336.
2When order doesn't matter
Swap two picks. If the outcome changes, order matters and the product is the answer. If it doesn't, divide by the orders of one group: 336 ÷ 6 = 56.
3The formula for groups
There are C(n, k) = n! / (k! × (n − k)!) groups of k things from n. A deck deals C(52, 5) = 2,598,960 five-card hands.
4Counting poker hands
Picks that do different jobs are counted in order, like the ranks of a full house (13 × 12). Picks that do the same job are chosen as a group, like the ranks of two pair (C(13, 2)).
Probability overviewSpotted a mistake? Tell us.