- Count possibilities with the rules of product and sum
- Choose between arrangements and combinations by asking whether order matters
- Expand a binomial with Pascal's triangle and find any coefficient
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
- n₁, n₂, …, nₖthe number of options at each step
- Nthe 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.
- n, mthe 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.
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
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.
Factorials and permutations
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.
- nthe 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.
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
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.)
Arrangements and combinations
- nthe total number of objects
- kthe 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.
- nthe total number of objects
- kthe 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ₖ.
| 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 |
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
b) The three representatives are equal, so order does not matter: C(25, 3) = P(25, 3) / 3! = 13,800 / 6 = 2300.
- n, kwhole 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).
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
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.
The binomial theorem and Pascal's triangle
- na 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: +, −, +, …
| 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⁶ |
a) Expand (x + 2)⁴.
b) Find the coefficient of x² in the expansion of (2x − 1)⁵.
Show solutionHide 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.
Key points
- 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ᵏ.
Check yourself
10 questions. Every correct answer earns XP.