Комбинаторика за час: сочетания, размещения, перестановки — все формулы с примерами

Комбинаторика — это искусство считать количество способов. Фундамент теории вероятностей: прежде чем считать $P(A) = m/n$, нужно уметь находить $m$ и $n$.

Три главных вопроса

Любая комбинаторная задача сводится к трём вопросам:

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

Перестановка — упорядочивание всех $n$ элементов.

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

Пример: книги на полке

Сколькими способами можно расставить 5 книг на полке?

$$P_5 = 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$

Перестановки с повторениями

Если среди $n$ элементов есть одинаковые: $n_1$ элементов первого типа, $n_2$ — второго, ...:

$$P_n(n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$$

Пример: сколько анаграмм у слова «МАМА»?

$n = 4$, $n_М = 2$, $n_А = 2$

$$P_4(2, 2) = \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6$$

Действительно: МАМА, МААМ, АММА, АМАМ, ААММ, ММАА.

2. Размещения

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

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

Пример: призёры

В забеге 8 участников. Сколькими способами могут распределиться золото, серебро и бронза?

$$A_8^3 = 8 \cdot 7 \cdot 6 = 336$$

Первого выбираем из 8, второго — из оставшихся 7, третьего — из 6.

Размещения с повторениями

Если элементы можно использовать многократно (как цифры в числе):

$$\bar{A}_n^k = n^k$$

Пример: сколько трёхзначных чисел можно составить из цифр 1–9 (цифры могут повторяться)?

$$\bar{A}_9^3 = 9^3 = 729$$

3. Сочетания

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

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

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

Пример: команда

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

$$C_{10}^3 = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120$$

Порядок не важен — Иванов-Петров-Сидоров и Сидоров-Петров-Иванов это одна команда.

Сочетания с повторениями

В кондитерской 5 видов пирожных. Сколькими способами можно купить 3 пирожных (виды могут повторяться, порядок не важен)?

$$\bar{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{k! \cdot (n-1)!}$$

$$\bar{C}_5^3 = C_7^3 = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$$

Сравнительная таблица

Свойства сочетаний

Симметрия

$$C_n^k = C_n^{n-k}$$

Выбрать $k$ элементов — то же самое, что выбрать $n - k$ элементов, которые НЕ войдут.

Пример: выбрать 2 человек из 5 на дежурство — то же, что выбрать 3, которые НЕ дежурят. $C_5^2 = C_5^3 = 10$.

Рекуррентное соотношение (правило Паскаля)

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$$

Основа треугольника Паскаля: каждый элемент — сумма двух над ним.

Бином Ньютона

$$(a + b)^n = \sum_{k=0}^{n} C_n^k \cdot a^{n-k} \cdot b^k$$

Коэффициенты разложения — это в точности числа из строки $n$ треугольника Паскаля.

Пример: $(x + 2)^4 = 1 \cdot x^4 + 4 \cdot x^3 \cdot 2 + 6 \cdot x^2 \cdot 4 + 4 \cdot x \cdot 8 + 1 \cdot 16 = x^4 + 8x^3 + 24x^2 + 32x + 16$

Полезные следствия

• $\sum_{k=0}^n C_n^k = 2^n$ — сумма всех сочетаний (число всех подмножеств)
• $\sum_{k=0}^n (-1)^k C_n^k = 0$ — знакопеременная сумма

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

n=0:            1
n=1:          1   1
n=2:        1   2   1
n=3:      1   3   3   1
n=4:    1   4   6   4   1
n=5:  1   5  10  10   5   1
n=6: 1  6  15  20  15   6   1

Строка $n = 6$: $C_6^0 = 1$, $C_6^1 = 6$, $C_6^2 = 15$, $C_6^3 = 20$, $C_6^4 = 15$, $C_6^5 = 6$, $C_6^6 = 1$.

Задачи для закрепления

1. Пароли

Пароль состоит из 4 различных букв латинского алфавита (26 букв). Сколько вариантов?

Решение: $A_{26}^4 = 26 \cdot 25 \cdot 24 \cdot 23 = 358\,800$

2. Шахматная доска

Сколькими способами можно выбрать 2 белые и 2 чёрные клетки на шахматной доске?

Решение: $C_{32}^2 \cdot C_{32}^2 = 496 \cdot 496 = 246\,016$

3. Флаги

Флаг состоит из 3 горизонтальных полос разных цветов. Доступно 7 цветов. Сколько разных флагов?

Решение: $A_7^3 = 7 \cdot 6 \cdot 5 = 210$

4. Карты

Из колоды в 36 карт сдают 6. Сколькими способами можно получить ровно 2 туза?

Решение: $C_4^2 \cdot C_{32}^4 = 6 \cdot 35\,960 = 215\,760$

5. Комиссия

Из 8 мужчин и 5 женщин выбирают комиссию из 4 человек. Сколько вариантов, где женщин больше мужчин?

Решение: 3 женщины + 1 мужчина ИЛИ 4 женщины.

$C_5^3 \cdot C_8^1 + C_5^4 \cdot C_8^0 = 10 \cdot 8 + 5 \cdot 1 = 80 + 5 = 85$

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

Итого

Ключевой навык комбинаторики — определить, что перед вами:

1. Порядок важен? Да → размещения (или перестановки). Нет → сочетания.
2. Элементы могут повторяться? Да → с повторениями. Нет → без повторений.
3. Один выбор ИЛИ несколько случаев? Несколько → сложить. Последовательные выборы → умножить.

Всё остальное — подстановка в формулы и аккуратный счёт.

Связанные статьи: Теория вероятностей и матстатистика — полная шпаргалка