Элементы комбинаторики — Ranimus, Ветвь разума

Зачем это нужно

Сколькими способами можно рассадить 5 гостей за столом? Сколько существует четырёхзначных PIN-кодов? Сколько разных команд по 3 человека можно выбрать из класса? Такие вопросы о числе вариантов решает комбинаторика. Она нужна для вычисления вероятностей (сколько исходов благоприятствует событию), в программировании и криптографии (сколько паролей нужно перебрать злоумышленнику), в генетике, логистике, планировании турниров.

Правило умножения

Если первый элемент можно выбрать $m$ способами, а после этого второй — $n$ способами, то пару можно выбрать $m \cdot n$ способами. Правило распространяется на любое число шагов.

Разобранный пример 1

Сколько существует четырёхзначных PIN-кодов (цифры могут повторяться)?

На каждой из 4 позиций — любая из 10 цифр: $10 \cdot 10 \cdot 10 \cdot 10 = 10\,000$ .

Перестановки. Факториал

Перестановка — способ расположить $n$ различных элементов в ряд. На первое место — $n$ вариантов, на второе — $n - 1$ , …, на последнее — 1:

$P_n = n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n.$

Запись $n!$ читается «эн факториал». По определению $0! = 1$ .

$n$	1	2	3	4	5	6	7	10
$n!$	1	2	6	24	120	720	5040	3 628 800

Факториал растёт очень быстро — быстрее любой степени: колоду из 36 карт можно перемешать более чем $3 \cdot 10^{41}$ способами.

Разобранный пример 2

Сколькими способами 5 гостей могут сесть на 5 стульев в ряд?

$5! = 120$ .

Размещения

Размещение из $n$ по $k$ — упорядоченный набор из $k$ различных элементов, выбранных из $n$ . Порядок важен.

$A_n^k = n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1) = \frac{n!}{(n - k)!}.$

Разобранный пример 3

Из 10 участников нужно выбрать призёров: 1-е, 2-е и 3-е места. Сколько вариантов?

$A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$ .

Сочетания

Сочетание из $n$ по $k$ — набор из $k$ различных элементов, выбранных из $n$ , без учёта порядка.

$C_n^k = \frac{n!}{k!\,(n - k)!} = \frac{A_n^k}{k!}.$

Каждое сочетание из $k$ элементов можно упорядочить $k!$ способами — поэтому размещений в $k!$ раз больше, чем сочетаний.

Разобранный пример 4

Сколькими способами можно выбрать команду из 3 человек в классе из 10 человек?

$C_{10}^3 = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$ . Сравните с примером 3: там порядок важен (места), и вариантов в $3! = 6$ раз больше.

Главный вопрос в задаче: важен ли порядок? Если да — размещения (или перестановки), если нет — сочетания.

Задача	Порядок	Формула
расставить все $n$ элементов	важен	$n!$
выбрать $k$ на разные роли	важен	$A_n^k$
выбрать $k$ в группу	не важен	$C_n^k$

Треугольник Паскаля

Числа $C_n^k$ удобно записывать в треугольник Паскаля (его знали ещё китайские и персидские математики за несколько веков до Блеза Паскаля): по краям единицы, а каждое внутреннее число равно сумме двух чисел над ним.

Треугольник Паскаля: строки от n = 0 до n = 6; каждое число — сумма двух чисел над ним; в строке n = 4 стоят числа 1, 4, 6, 4, 1

Свойства: $C_n^k = C_n^{n-k}$ (выбрать $k$ — то же, что выбрать $n - k$ , которых не берём); $C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}$ ; сумма чисел в строке $n$ равна $2^n$ (число всех подмножеств).

Комбинаторика и вероятность

Комбинаторика — главный инструмент для подсчёта исходов в классической вероятности. Например, в лотерее «5 из 36» число всех возможных комбинаций $C_{36}^5 = 376\,992$ . Поэтому вероятность угадать все пять чисел одним билетом равна $\frac{1}{376\,992}$ — примерно 0,0003 %.

Разобранный пример 5

В классе 10 мальчиков и 15 девочек. Наугад выбирают двух дежурных. Какова вероятность, что оба — мальчики?

Всего способов выбрать двоих: $C_{25}^2 = 300$ .
Благоприятных (оба мальчики): $C_{10}^2 = 45$ .
$P = \frac{45}{300} = 0{,}15$ .

Как решать комбинаторные задачи

Определите, что выбирают и из чего: какие элементы, сколько их всего и сколько нужно.
Решите, важен ли порядок (есть ли у выбранных элементов разные роли или места).
Решите, могут ли элементы повторяться (цифры в коде — могут, люди в команде — нет).
Выберите формулу или примените правило умножения по шагам.
Для маленьких задач проверьте перебором — выпишите все варианты.

Типичные ошибки

Путать размещения и сочетания: команда (без ролей) — сочетания, призовые места — размещения.
Применять правило умножения, когда варианты не зависят от порядка выбора, и получать «лишние» повторы.
Считать $0! = 0$ : на самом деле $0! = 1$ .
Забывать, что в PIN-коде цифры могут повторяться, а в перестановке элементы различны.
Вычислять большие факториалы целиком вместо сокращения дроби.

Что дальше

Операции над событиями. Формула сложения вероятностей — операции над событиями и сложение вероятностей.
Биномиальная формула и комбинаторные коэффициенты — бином Ньютона: коэффициенты — числа из треугольника Паскаля.
Комбинаторика — углублённая комбинаторика.