Newton’s binomial
The number of ways to choose k out of n elements without regard to order is called the number of combinations: C(n, k) = n!/(k!(n − k)!). It arises by dividing n(n − 1)…(n − k + 1) by k!, since each subset is counted k! times. Properties: C(n, 0) = C(n, n) = 1, C(n, k) = C(n, n − k) (choosing k is the same as leaving out n − k) and C(n, k) = C(n − 1, k − 1) + C(n − 1, k); the last gives Pascal’s triangle: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1. Newton’s binomial: (a + b)ⁿ = C(n, 0)aⁿ + C(n, 1)aⁿ⁻¹b + … + C(n, n)bⁿ; the (k + 1)-th term is Tₖ₊₁ = C(n, k)aⁿ⁻ᵏbᵏ. For a = b = 1, C(n, 0) + … + C(n, n) = 2ⁿ; for a = 1, b = −1 the sum at odd places equals the sum at even places.
| 1 | ||||
| 1 | 1 | |||
| 1 | 2 | 1 | ||
| 1 | 3 | 3 | 1 | |
| 1 | 4 | 6 | 4 | 1 |
In a tournament with 8 teams where every two teams play each other once, the number of matches equals the number of pairs: C(8, 2) = 8 · 7 / 2 = 28. Order does not matter, because “A–B” and “B–A” are the same match. That is why we divide by 2! when counting combinations.
Sports organisers make tournament schedules, quality inspectors count the ways of picking a few items from a batch, and network engineers count the possible links between computers.
Write the letters A, B, C, D on paper, one for each of four friends, and list every possible pair. Check that the number of pairs matches C(4, 2) = 6.
“Pascal’s triangle”: on squared paper write 8 rows of Pascal’s triangle (each number is the sum of the two above it). Check that each row sums to 2ⁿ and read off the coefficients of (a + b)⁶.