Permutations and combinations
Different orders of placing n elements into n places, one per place, are called permutations. Their number is Pₙ = n · (n - 1) · ... · 2 · 1 = n! (n factorial). For example, 4 books can be placed on a shelf in P₄ = 4! = 24 different orders. In combinations of n elements taken k at a time the order does not matter, only the content does; their number is denoted Cₙᵏ and is found by Cₙᵏ = n!/(k! (n - k)!) = n(n - 1)...(n - k + 1)/k!. For example C₅² = 5 · 4/(1 · 2) = 10. The equality Cₙᵏ = Cₙⁿ⁻ᵏ holds: choosing k elements is the same as leaving out the other n - k. If order matters we use permutations; if not, combinations.
| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| n! | 1 | 2 | 6 | 24 | 120 |
A coach picks 3 of 7 pupils for a relay. If order does not matter, C₇³ = 7 · 6 · 5 / (1 · 2 · 3) = 35 ways. If the 3 places are different (first, second, third), there are 7 · 6 · 5 = 210 ways.
A coach selects a team, a teacher assigns duty pupils, and a statistician counts possible sample groups.
Write all the orders in which the letters A, B, C can be placed in a row and check that 3! = 6.
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| C₆ᵏ | 1 | 6 | 15 | 20 | 15 | 6 | 1 |
“Choosing a team”: 5 pupils come to the front. First the ways of lining them up (permutations) are counted, then the ways of choosing 2 of them (combinations), and the difference is discussed.