§ 3. Число сочетаний и треугольник Паскаля

Перестановки отвечали на вопрос «в каком порядке»: в них участвовали все предметы набора сразу. Теперь задача другая. Из набора надо взять только часть, а порядок внутри взятой части никого не интересует. Кого включат в команду, какие три газеты выберут для объявления, какие шесть номеров зачеркнут в лотерейном билете — всюду важен состав, а не очерёдность. Правило умножения к таким задачам напрямую не подходит, и сейчас станет ясно почему.

Тренер выбирает из трёх теннисистов А, Б и В двоих для игры в паре. Если различать, кто назван первым, вариантов будет шесть: первого берём тремя способами, второго — двумя, 3 · 2 = 6. Но «А и Б» и «Б и А» — это одни и те же два человека на площадке. Каждая пара попала в список дважды, значит, разных пар вдвое меньше: 6 : 2 = 3.

С четырьмя игроками рассуждение то же (рис. 1). Упорядоченных пар выходит 4 · 3 = 12, и все они выписаны. Жёлтым отмечены шесть записей, которые повторяют уже встречавшуюся пару в обратном порядке. Разных пар остаётся 12 : 2 = 6: АБ, АВ, АГ, БВ, БГ, ВГ.

Число способов отобрать k предметов из n имеющихся, когда порядок отобранных предметов не различают, называют числом сочетаний из n по k. Пишут его Cₙᵏ и читают «цэ из эн по ка». Два таких числа мы уже сосчитали: C₃² = 3 и C₄² = 6.

Заодно виден общий приём, которым эти числа получают. Сначала считают упорядоченные наборы обычным правилом умножения: первый предмет берут n способами, второй — (n − 1) способами, и так k шагов. Потом замечают, что один и тот же набор из k предметов записан в этом списке столько раз, сколькими способами сами эти предметы можно переставить между собой, то есть k! раз. Значит, число упорядоченных наборов надо разделить на k!. Для пар мы делили на 2! = 2, а отбирая тройку, делили бы уже на 3! = 6.

Дальше выписывать наборы руками бесполезно: уже для десятка предметов список не поместится на страницу. Готовые ответы для небольших n собраны в треугольную таблицу — треугольник Паскаля (рис. 2). Число Cₙᵏ стоит на пересечении строки n и столбца k, и запомнить нужно две вещи. Первая: строки и столбцы нумеруются с нуля, верхняя строка — нулевая, а первое число в строке — нулевое. Вторая: столбцы наклонные, они спускаются вниз и вправо. На рисунке столбец 4 показан зелёным: в строке 6 он даёт клетку 15, поэтому C₆⁴ = 15. Если искать столбец прямо под верхушкой треугольника, снимешь чужое число — это самая частая ошибка при работе с таблицей.

Треугольник не заучивают наизусть, его строят, и уходит на это полминуты. Каждая строка начинается и кончается единицей, а любое другое число равно сумме двух ближайших чисел строкой выше (рис.