Introduction
Counting by listing works for two dice, but not for a lottery with 14 million tickets or a card hand from 2.6 million possibilities. Combinatorics, the mathematics of counting, gives formulas for these sample spaces. With them, a probability is still favourable over all, but neither number has to be listed.
How it works
The multiplication rule: if one choice can be made in a ways and the next in b ways, the pair can be made in a × b ways. Three shirts and four trousers make 12 outfits; two dice make 6 × 6 = 36 outcomes.
Applied to ordering n different things, the rule gives n choices for the first place, n − 1 for the second and so on: n! = n × (n − 1) × … × 1, read "n factorial". Four letters can be ordered in 4! = 24 ways.
Picking k of n items in order (gold, silver, bronze) is a permutation: n × (n − 1) × … for k places, which is P(n, k) = n! ÷ (n − k)!. Picking k items without order (a hand of cards, a committee) is a combination: every set of k was counted k! times by the permutation, so C(n, k) = n! ÷ (k! (n − k)!), read "n choose k". Python's math module has all three: factorial, perm and comb.
When some items repeat, swapping identical items gives the same arrangement. BANANA has 6! orders of its letters, but the three As can be swapped 3! ways and the two Ns 2! ways without any visible change, so there are 6! ÷ (3! × 2!) = 60 different words.
To decide which formula fits, ask two questions: does the order matter, and can an item be picked twice? A lottery ticket is unordered and without repeats: combinations. A PIN code is ordered with repeats: the multiplication rule, 10⁴.
Example
from math import comb, factorial, perm
print("orders of 4 letters:", factorial(4))
print("ordered picks of 2 from 4:", perm(4, 2))
print("unordered picks of 2 from 4:", comb(4, 2))
tickets = comb(49, 6) # choose 6 numbers from 49
print("lottery tickets:", tickets)
print("P(jackpot) = 1 in", tickets)
# BANANA: 6 letters, but the 3 As and the 2 Ns can swap among themselves
print("arrangements of BANANA:", factorial(6) // (factorial(3) * factorial(2)))Line by line
factorial(4)counts the orders of four different letters.perm(4, 2)counts ordered pairs,comb(4, 2)unordered ones: each pair appears twice among the ordered ones.comb(49, 6)counts lottery tickets; one ticket wins the jackpot.- BANANA's count divides 6! by 3! for the As and 2! for the Ns.
Expected result
orders of 4 letters: 24
ordered picks of 2 from 4: 12
unordered picks of 2 from 4: 6
lottery tickets: 13983816
P(jackpot) = 1 in 13983816
arrangements of BANANA: 60
In the real world
Lotteries publish their odds from combinations, and security experts estimate password strength by counting the possible passwords. Card games, tournament schedules, experiments that test every combination of settings, and DNA sequence analysis all rely on counting. When a count is too large even for formulas, the simulations of a later lesson estimate it instead.
Common mistakes
- Using permutations when order does not matter, counting every hand of cards k! times.
- Forgetting that items repeat, so BANANA seems to have 720 arrangements.
- Multiplying choices that depend on each other without adjusting the later counts.
Best practices
- Ask whether order matters and whether repeats are allowed before choosing a formula.
- Check a formula on a case small enough to list by hand.
- Use
math.combandmath.perminstead of dividing factorials yourself, which is slower and error-prone.
Summary
The multiplication rule counts sequences of choices, and n! counts the orders of n items. Ordered selections are permutations, P(n, k) = n! ÷ (n − k)!; unordered ones are combinations, C(n, k) = n! ÷ (k! (n − k)!). Repeated items divide the count by the factorial of each repeat's count.
Quick check
Key takeaways
- Multiply the choices at each step to count a sequence of choices.
- Order matters: permutations. Order does not matter: combinations, which divide by k!.
- With repeated items, divide by the factorial of each item's count.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.