Combinatorics problems
The main question of combinatorics is “in how many ways?”. When counting options we list them in order, so none is missed or repeated. Addition rule: if A can be chosen in m ways or B in another n ways, then “A or B” can be chosen in m + n ways. Multiplication rule: if A can be chosen in m ways and then B in n ways, “A and B” can be done in mn ways; for consecutive steps the numbers of ways are multiplied. The number of arrangements of k out of n elements without repetition is Aₙᵏ = n(n − 1)…(n − k + 1); with repetition it is n^k. The number of ways to order all n elements (permutations) is n! = 1 · 2 · … · n, with 0! = 1. An n-element set has 2ⁿ subsets, since each element is either in the subset or not.
| Selection | Formula |
|---|---|
| permutations | Pₙ = n! |
| arrangements | Aₙᵏ = n!/(n − k)! |
| combinations | Cₙᵏ = n!/(k!(n − k)!) |
A school concert programme has 5 acts. They can be put in order in 5! = 120 ways. If the opening act is already fixed, the other 4 can be arranged in 4! = 24 ways. The multiplication rule lets us count the possibilities without listing them all.
Event organisers plan the order of a programme, security specialists judge how many possible passwords and codes there are, and logistics staff count delivery route options.
Write the digits 1, 2, 3, 4 on four slips of paper. Without listing them all, work out how many different four-digit numbers can be made using each slip once (4 · 3 · 2 · 1). Then write out only those starting with 1: they should be one quarter of the total.
“Letters of a word”: take a word with all different letters (for example KITOB). List all orders of 3 of its letters by hand and check that there are 3! = 6. Then compute 5! for all five letters with the formula.