Бином Ньютона
Число способов выбрать k из n элементов без учёта порядка называется числом сочетаний: C(n, k) = n!/(k!(n − k)!). Оно получается делением n(n − 1)…(n − k + 1) на k!, так как каждое подмножество считается k! раз. Свойства: C(n, 0) = C(n, n) = 1, C(n, k) = C(n, n − k) (выбрать k — то же, что оставить n − k) и C(n, k) = C(n − 1, k − 1) + C(n − 1, k); последнее даёт треугольник Паскаля: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1. Бином Ньютона: (a + b)ⁿ = C(n, 0)aⁿ + C(n, 1)aⁿ⁻¹b + … + C(n, n)bⁿ; (k + 1)-й член равен Tₖ₊₁ = C(n, k)aⁿ⁻ᵏbᵏ. При a = b = 1 C(n, 0) + … + C(n, n) = 2ⁿ; при a = 1, b = −1 сумма членов на нечётных местах равна сумме членов на чётных местах.
| 1 | ||||
| 1 | 1 | |||
| 1 | 2 | 1 | ||
| 1 | 3 | 3 | 1 | |
| 1 | 4 | 6 | 4 | 1 |
В турнире с 8 командами, где каждые две команды играют друг с другом один раз, число матчей равно числу пар: C(8, 2) = 8 · 7 / 2 = 28. Порядок не важен, потому что «A–B» и «B–A» — один и тот же матч. Поэтому при подсчёте сочетаний мы делим на 2!.
Организаторы спортивных соревнований составляют расписание турниров, контролёры качества подсчитывают способы выбрать несколько изделий из партии, а сетевые инженеры подсчитывают возможные связи между компьютерами.
Запишите на бумаге буквы A, B, C, D, по одной для каждого из четырёх друзей, и выпишите все возможные пары. Проверьте, что число пар совпадает с C(4, 2) = 6.
«Треугольник Паскаля»: на клетчатой бумаге запишите 8 строк треугольника Паскаля (каждое число — сумма двух чисел над ним). Проверьте, что сумма каждой строки равна 2ⁿ, и считайте коэффициенты (a + b)⁶.