How many different 4-digit PIN codes can a bank card have? Each position takes one of 10 digits: 10 · 10 · 10 · 10 = 10,000 options. In how many ways can a class of 25 choose 3 representatives? In 2300 ways! Listing every option one by one is impossible, and combinatorics teaches you to count them without a list. It is the foundation of probability, cryptography and programming.
The rules of product and sum
Where
- n₁, n₂, …, nₖ
- the number of options at each step
- N
- the total number of outcomes
Rule of product: if a choice is made in several successive steps (“this and then that”), multiply the numbers of options at each step.
Where
- n, m
- the numbers of options in two groups with nothing in common
Rule of sum: if you choose “either this or that” and the groups do not overlap, add the numbers of options.
Picture the rule of product as a tree. Murad has 3 shirts (white, blue, green) and 2 pairs of trousers (black, grey). From every shirt grow 2 branches, one for each pair of trousers, so there are 3 · 2 = 6 outfits: white–black, white–grey, blue–black, blue–grey, green–black, green–grey. If he must choose just one item — either one of 3 caps or one of 2 scarves — the options are added: 3 + 2 = 5. In short: “this and that” — multiply; “either this or that” — add.
Rules of product and sum
Problem
a) A café offers 3 soups, 4 main courses and 2 drinks. How many different lunches of one soup, one main course and one drink can you order?
b) How many three-digit numbers have all different digits?
c) Leyla picks one book: one of 5 novels or one of 7 poetry books on the shelf. How many choices does she have?
Show solutionHide solution
Solution
b) Hundreds digit: cannot be 0, so 9 options. Tens digit: any digit except the first one, including 0, so 9 options. Units digit: the remaining 8 digits. 9 · 9 · 8 = 648.
c) “Either a novel or a poetry book”, so use the rule of sum: 5 + 7 = 12.
Inclusion–exclusion. If two groups overlap, the rule of sum counts the common elements twice, so they are subtracted once. For three groups: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Here |A| is the number of elements of the set A.
Divisible by 2, 3 or 5
Problem
How many of the numbers 1, 2, …, 100 are divisible by 2, by 3 or by 5?
Show solutionHide solution
Solution
By 6: 16, by 10: 10, by 15: 6; by 30: 3.
50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
So 100 − 74 = 26 numbers are divisible by none of them — for example 1, 7, 11, 13 and every prime greater than 5.
Factorials and permutations
FactorialDefinition
n! = 1 · 2 · 3 · … · n, the product of all natural numbers from 1 to n. By definition 0! = 1. For example, 5! = 120 and 10! = 3,628,800: factorials grow very fast.
Where
- n
- the number of different objects being arranged
The number of permutations: the number of ways to put n different objects in a row. There are n choices for the first place, n − 1 for the second, and so on.
Write them all down
Problem
In how many orders can Aysel (A), Leyla (L) and Murad (M) stand in a line?
Show solutionHide solution
Solution
A first: ALM, AML
L first: LAM, LMA
M first: MAL, MLA
That is 6 orders. The counting rule says the same: 3 choices for the first place, 2 for the second, 1 for the last: 3 · 2 · 1 = 3! = 6.
Permutations
Problem
a) In how many ways can 5 different books be put on a shelf?
b) 6 pupils stand in a line. How many orders are possible if Aysel and Murad must stand next to each other?
Show solutionHide solution
Solution
b) “Glue” Aysel and Murad together and treat them as one object: then 5 objects are arranged, 5! = 120 ways. Inside the pair they can stand in 2! = 2 orders.
120 · 2 = 240. (Without the condition there would be 6! = 720.)
Repeated objects and a round table
Problem
1) How many different 7-digit numbers can be written with the digits 1, 1, 2, 2, 2, 3, 3, each used exactly once?
2) In how many ways can 6 people sit around a round table, if only the order around the table matters?
Show solutionHide solution
Solution
2) Moving everybody one seat round gives the same seating, and every seating has 6 such rotations: 6!/6 = 5! = 120. Put differently: fix one person’s seat and arrange the other 5.
Arrangements and combinations
Where
- n
- the total number of objects
- k
- the number of objects chosen and ordered (k ≤ n)
Arrangements (ordered selections): choose k of n objects and put them in order, so order matters. The right-hand side has k factors counting down from n.
Where
- n
- the total number of objects
- k
- the number of objects chosen; order ignored
Combinations: simply choose k of n objects, so order does not matter. Each group of k is counted k! times among the arrangements, so we divide by k!. C(n, k) is also written ⁿCₖ.
When does order matter? Take three pupils, A, B and C, and choose two of them. If the two get different jobs (captain and deputy), AB and BA are different choices. If they are simply a pair going to a competition, AB and BA are the same pair.
| Captain and deputy (order matters) | Just a pair (order does not matter) |
|---|---|
| AB, BA | {A, B} |
| AC, CA | {A, C} |
| BC, CB | {B, C} |
| 6 in total = P(3, 2) | 3 in total = C(3, 2) |
| What are we doing? | Does order matter? | Formula | Example |
|---|---|---|---|
| arrange all n objects | yes | n! | 5 books on a shelf: 120 |
| choose k of n and order them | yes | P(n, k) | president, deputy, secretary from 25: 13,800 |
| just choose k of n | no | C(n, k) | 3 representatives from 25: 2300 |
| each of k places gets one of n options (repeats allowed) | yes | nᵏ | 4-digit PIN: 10⁴ = 10,000 |
Does order matter or not?
Problem
In a class of 25 pupils:
a) in how many ways can they choose a class president, a deputy and a secretary?
b) in how many ways can they choose 3 representatives for a conference?
Show solutionHide solution
Solution
b) The three representatives are equal, so order does not matter: C(25, 3) = P(25, 3) / 3! = 13,800 / 6 = 2300.
Where
- n, k
- whole numbers with k ≤ n
First property: choosing k objects is the same as “leaving out” the other n − k. The second property is the rule that builds Pascal's triangle: C(5, 2) + C(5, 3) = 10 + 10 = 20 = C(6, 3).
Why does C(5, 2) + C(5, 3) = C(6, 3) hold? A story explains it. From 6 pupils, Aysel among them, we choose a team of 3: C(6, 3) = 20 teams. Every team either includes Aysel or not. Teams with Aysel: choose 2 more from the other 5 — C(5, 2) = 10. Teams without her: choose all 3 from the other 5 — C(5, 3) = 10. 10 + 10 = 20. And C(5, 2) = C(5, 3) is just as simple: choosing the 2 pupils who go is the same as choosing the 3 who stay.
- For C(10, 3), write on top 3 numbers counting down from 10: 10 · 9 · 8 = 720.
- Underneath write 3! = 1 · 2 · 3 = 6.
- Divide: 720 ÷ 6 = 120. It is easier to cancel first: 9 ÷ 3 = 3 and 8 ÷ 2 = 4, so 10 · 3 · 4 = 120.
- If k is large, turn it around: C(20, 18) = C(20, 2) = (20 · 19) / 2 = 190.
Exam-style problem: choosing a team
Problem
A club has 6 boys and 4 girls. A team of 5 is chosen.
a) How many teams have exactly 2 girls?
b) How many teams have at least one girl?
c) 2 members of the club are chosen at random. What is the probability that both are girls?
Show solutionHide solution
Solution
b) Use the complement: “at least one girl” = all teams − teams with no girls. C(10, 5) − C(6, 5) = 252 − 6 = 246.
c) All pairs: C(10, 2) = 45; pairs of two girls: C(4, 2) = 6. P = 6/45 = 2/15 ≈ 0.13.
A classic olympiad idea is stars and bars. Sharing n identical objects among m people is the same as arranging n stars and m − 1 bars in a row: the bars cut the row into m parts. For example, ★★|★★★★★|★★★ means 2, 5 and 3. We only choose the places of the bars among n + m − 1 places, so the number of ways is C(n + m − 1, m − 1).
Sharing sweets
Problem
1) In how many ways can 10 identical sweets be shared among 3 children?
2) And if every child must get at least one?
Show solutionHide solution
Solution
2) First give every child one sweet; the remaining 7 are shared freely: C(9, 2) = (9 · 8)/2 = 36.
The same numbers count the solutions of x + y + z = 10 in non-negative integers (66) and in positive integers (36).
The binomial theorem and Pascal's triangle
Where
- n
- a natural-number exponent
- C(n, k)
- the binomial coefficients
The binomial theorem. General term: Tₖ₊₁ = C(n, k) · aⁿ⁻ᵏ · bᵏ. The expansion has n + 1 terms and its coefficients add up to 2ⁿ. In (a − b)ⁿ the signs alternate: +, −, +, …
Start with what you know: (a + b)² = a² + 2ab + b² — the coefficients 1, 2, 1 are row 2 of Pascal’s triangle. Multiply by (a + b) once more and you get (a + b)³ = a³ + 3a²b + 3ab² + b³ — row 3: 1, 3, 3, 1. Two patterns help: from term to term the power of a goes down by one while the power of b goes up, and in every term the two powers add up to n. For n = 3: a³, a²b, ab², b³.
| n | Binomial coefficients | Sum |
|---|---|---|
| 0 | 1 | 1 = 2⁰ |
| 1 | 1 1 | 2 = 2¹ |
| 2 | 1 2 1 | 4 = 2² |
| 3 | 1 3 3 1 | 8 = 2³ |
| 4 | 1 4 6 4 1 | 16 = 2⁴ |
| 5 | 1 5 10 10 5 1 | 32 = 2⁵ |
| 6 | 1 6 15 20 15 6 1 | 64 = 2⁶ |
Why do the coefficients of row n add up to 2ⁿ? Put a = b = 1 in the binomial theorem: (1 + 1)ⁿ = C(n, 0) + C(n, 1) + … + C(n, n). There is a counting proof too: a set of n elements has 2ⁿ subsets (each element is either taken or not), and C(n, k) of them have exactly k elements. Putting a = 1, b = −1 instead gives C(n, 0) − C(n, 1) + C(n, 2) − … = 0: a set has as many subsets with an even number of elements as with an odd number.
Pizza toppings
Problem
A pizzeria offers 8 toppings. How many different pizzas can be ordered (any set of toppings, possibly none)? How many of them have an even number of toppings?
Show solutionHide solution
Solution
Even and odd numbers of toppings are equally common, so 128 pizzas have an even number of toppings. Check with row 8: C(8, 0) + C(8, 2) + C(8, 4) + C(8, 6) + C(8, 8) = 1 + 28 + 70 + 28 + 1 = 128 ✓.
Interactive
Expanding a binomial and finding a coefficient
Problem
a) Expand (x + 2)⁴.
b) Find the coefficient of x² in the expansion of (2x − 1)⁵.
Show solutionHide solution
Solution
(x + 2)⁴ = x⁴ + 4 · 2x³ + 6 · 4x² + 4 · 8x + 16 = x⁴ + 8x³ + 24x² + 32x + 16.
b) General term: C(5, k) · (2x)⁵⁻ᵏ · (−1)ᵏ. For x² we need 5 − k = 2 ⇒ k = 3.
C(5, 3) · 2² · (−1)³ = 10 · 4 · (−1) = −40.
The binomial theorem is also a tool for approximation and for probability. If x is small, the terms with x², x³, … quickly become tiny, so (1 + x)ⁿ ≈ 1 + nx + C(n, 2)x². And when a coin is tossed n times, every sequence of heads and tails has probability 1/2ⁿ, while exactly k heads appear in C(n, k) sequences — this is the binomial distribution, one of the main laws of university probability theory.
Approximation and coin tossing
Problem
1) Estimate 1.01¹⁰ without a calculator.
2) A coin is tossed 10 times. What is the probability of exactly 5 heads?
Show solutionHide solution
Solution
2) There are 2¹⁰ = 1024 equally likely sequences, and C(10, 5) = 252 of them have exactly 5 heads: P = 252/1024 = 63/256 ≈ 0.246. So even the most likely result happens in fewer than one series out of four.
Remember
- Rule of product: multiply the options of successive steps; rule of sum: add the options of “either/or” choices.
- n! counts all orderings of n objects.
- If order matters, P(n, k) = n!/(n − k)!; if not, C(n, k) = n!/(k!(n − k)!).
- For “at least one” problems it is easier to subtract the opposite case from the total.
- The coefficients of (a + b)ⁿ are row n of Pascal's triangle; the general term is C(n, k)aⁿ⁻ᵏbᵏ.