Комбинаторика (Kombinatorik)

15 мин · 2 упражнения

Комбинаторика изучает способы подсчёта объектов. Хорошая новость: все задачи сводятся к нескольким базовым формулам, которые мы разберём ниже.

---

Часть 1. Принципы подсчёта

Два фундаментальных правила лежат в основе всей комбинаторики:

Правило сложения (ИЛИ)

Если выбор можно сделать $m$ способами ИЛИ $n$ способами, и эти способы не пересекаются, то всего способов:

$$\boxed{m+n}$$

Пример: В меню 5 видов супа и 8 видов салата. Сколько вариантов для лёгкого обеда (одно блюдо)?

$$5++8==13\text{вариантов}$$

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

Если первый выбор можно сделать $m$ способами, И для каждого из них второй выбор делается $n$ способами, то всего способов:

$$\boxed{m\cdot n}$$

Пример: В кафе 3 вида первого, 4 вида второго и 2 вида напитка. Сколько вариантов комплексного обеда?

$$3\cdot \cdot 4\cdot \cdot 2==24\text{варианта}$$

Как отличить «ИЛИ» от «И»

Комбинация правил

В сложных задачах правила используются вместе.

Пример: В группе 8 мальчиков и 5 девочек. Нужно выбрать капитана и помощника разного пола. Либо капитан-мальчик и помощник-девочка, либо наоборот.

• Случай 1: $8\cdot 5=40$
• Случай 2: $5\cdot 8=40$

$$40++40==80\text{способов}$$

Подсчёт с ограничениями

Если есть ограничение, сначала заполняем ограниченную позицию!

Пример: Сколько чётных трёхзначных чисел из цифр 1–5 без повторений?

• Последняя цифра (должна быть чётной): 2 варианта (2 или 4)
• Первая цифра: 4 варианта (любая из оставшихся)
• Средняя цифра: 3 варианта

$$2\cdot \cdot 4\cdot \cdot 3==24\text{числа}$$

---

Часть 2. Факториал

Факториал числа $n$: произведение всех натуральных чисел от 1 до $n$.

$$\boxed{n!=1\cdot 2\cdot 3\cdot \dots \cdot n}$$

Ключевое свойство: $n!=n\cdot (n-1)!$

Например: $5!=5\cdot 4!=5\cdot 24=120$

---

Часть 3. Перестановки

Перестановки без повторений

Перестановка: упорядоченная расстановка всех $n$ элементов. Порядок важен: ABC ≠ BAC.

$$\boxed{P_n=n!}$$

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

$$P_5==5!==120\text{способов}$$

Размещения (частичные перестановки)

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

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

$$n\cdot \cdot (n--1)\cdot \cdot \dots \cdot \cdot (n--k++1)$$

Пример: Сколькими способами выбрать президента, вице-президента и секретаря из 10 человек?

$$A_{10}^3==10\cdot \cdot 9\cdot \cdot 8==720\text{способов}$$

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

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

$$P_n^{n_1,n_2,\dots ,n_k}==\frac{n!}{n_1!\cdot n_2!\cdot \dots \cdot n_k!}$$

Интуиция: Мы делим на факториалы повторяющихся элементов, потому что перестановки одинаковых элементов между собой дают дубликаты.

Пример: Сколько различных «слов» из букв слова МАТЕМАТИКА?

Всего 10 букв: М(2), А(3), Т(2), Е(1), И(1), К(1)

$$P_{10}^{2,3,2,1,1,1}==\frac{10!}{2!\cdot 3!\cdot 2!}==\frac{3628800}{24}==151200$$

Круговые перестановки

Расстановка $n$ элементов по кругу (начало не фиксировано). Каждую линейную расстановку можно «повернуть» $n$ способами, поэтому делим на $n$:

$$\boxed{P_{\text{круг}}=(n-1)!}$$

Пример: 6 человек за круглым столом: $(6-1)!=5!=120$ способов.

---

Часть 4. Сочетания

Что такое сочетание?

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

Сравните:

Откуда берётся формула?

Шаг 1. С учётом порядка: выбрать 3 из 5 = $5\cdot 4\cdot 3=60$ (это $A_5^3$)

Шаг 2. Каждую тройку мы посчитали $3!=6$ раз (все перестановки внутри неё)

Шаг 3. Делим: $C_5^3=\frac{60}{6}=10$

Формула

$$\boxed{C_n^k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}}$$

На экзамене EPM чаще используют обозначение $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ (читается «n по k» или по-немецки «n uber k»).

Быстрый способ вычисления

Вместо вычисления полных факториалов сокращаем сразу:

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

В числителе стоят $k$ множителей подряд, начиная с $n$; а в знаменателе стоит $k!$.

Примеры:

$$C_5^2==\frac{5\cdot 4}{2\cdot 1}==10$$ $$C_8^3==\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}==56$$ $$C_7^3==\frac{7\cdot 6\cdot 5}{3!}==\frac{210}{6}==35$$

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

Симметрия:

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

Выбрать 3 из 10 равносильно выбору 7, которых мы оставим. Это помогает при вычислениях: $C_{100}^{98}=C_{100}^2=\frac{100\cdot 99}{2}=4950$.

Крайние случаи:

• $C_n^0=1$ (один способ не выбрать ничего)
• $C_n^n=1$ (один способ выбрать всё)
• $C_n^1=n$

Формула Паскаля:

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

Последний элемент либо входит в выборку ($C_{n-1}^{k-1}$), либо нет ($C_{n-1}^k$).

Связь с размещениями:

$$A_n^k==C_n^k\cdot \cdot k!$$

Размещения = сочетания × перестановки выбранных.

---

Сочетания $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ также используются в биномиальном распределении (формула Бернулли) для подсчёта вероятностей повторных независимых испытаний. Подробнее об этом в отдельном топике.

---

Примеры задач EPM

Задача 1: Шары из урны

В урне 5 красных и 4 синих шара. Достают 3 шара. Сколько способов достать ровно 2 красных?

• Выбрать 2 красных из 5: $C_5^2=10$
• Выбрать 1 синий из 4: $C_4^1=4$
• По правилу умножения: $10\cdot 4=40$ способов

Задача 2: Вероятность

Из той же урны достают 3 шара. Какова вероятность, что все три одного цвета?

Общее число исходов: $C_9^3=84$

Благоприятные: все красные $C_5^3=10$ + все синие $C_4^3=4$ = 14

$$P==\frac{14}{84}==\frac{1}{6}$$

Задача 3: Комитет с условием

Из 6 мужчин и 4 женщин выбирают комитет из 5 человек. Нужно минимум 2 женщины. Сколько способов?

Итого: $120+60+6=186$

Задача 4: Книжная полка с группировкой

На полке 4 учебника математики и 3 учебника физики. Сколькими способами их расставить, если учебники одного предмета должны стоять рядом?

1. Группы: $2!=2$ способа расположить (М и Ф)
2. Внутри М: $4!=24$
3. Внутри Ф: $3!=6$

$$2!\cdot \cdot 4!\cdot \cdot 3!==2\cdot \cdot 24\cdot \cdot 6==288\text{способов}$$

Задача 5: Перестановки с повторениями

Сколько различных 5-значных чисел из цифр 1, 1, 2, 2, 3?

$$P_5^{2,2,1}==\frac{5!}{2!\cdot 2!\cdot 1!}==\frac{120}{4}==30$$

---

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

Ошибка 1: Путать «или» и «и»

Выбрать суп или салат: сложение. Выбрать суп и салат: умножение.

Ошибка 2: Путать сочетания и размещения

Спросите себя: важен ли порядок?

• «Выбрать команду»: порядок НЕ важен → сочетания
• «Распределить места»: порядок важен → размещения

Ошибка 3: Не начать с ограничения

Если есть условие (чётное число, начинается с определённой цифры), сначала заполняйте ограниченную позицию.

Ошибка 4: Сложить вместо умножения при выборе из разных групп

При одновременном выборе из разных групп мы умножаем, а не складываем:

$C_5^2\cdot C_4^1=40$ (правильно)

$10+4=14$ (неправильно)

Ошибка 5: Забыть про повторяющиеся элементы

Слово МАМА: не $4!=24$, а $\frac{4!}{2!\cdot 2!}=6$

---

Как выбрать формулу

• Порядок важен?
  • ДА: Все элементы?
    • ДА: Перестановки, $P=n!$
    • НЕТ: Размещения, $A=\frac{n!}{(n-k)!}$
  • НЕТ: Сочетания, $C=\frac{n!}{k!(n-k)!}$

---

Проверьте себя

Ваша очередь1 из 2

Код доступа состоит либо из двух разных букв из A, B, C, D, E, либо из трёх разных цифр из 1, 2, 3, 4. Сколько существует разных кодов?

A$14$B$44$C$480$D$40$

Проверить

Ваша очередь2 из 2

Пять человек садятся за круглый стол, и двое из них, Анна и Бен, хотят сидеть рядом. Рассадки, которые переходят друг в друга поворотом, считаются одинаковыми. Сколько существует рассадок?

A$24$B$12$C$48$D$6$

Проверить

---

Все формулы

Правило сложения (ИЛИ): $m+n$

Правило умножения (И): $m\cdot n$

Факториал: $n!=1\cdot 2\cdot 3\cdot \dots \cdot n$, причём $0!=1$

Перестановки: $P_n=n!$

Размещения: $A_n^k=\frac{n!}{(n-k)!}$

Перестановки с повторениями: $P_n^{n_1,\dots ,n_k}=\frac{n!}{n_1!\cdot \dots \cdot n_k!}$

Круговые перестановки: $P_{\text{круг}}=(n-1)!$

Сочетания: $C_n^k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$

Быстрый расчёт: $C_n^k=\frac{n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{k!}$

Симметрия: $C_n^k=C_n^{n-k}$

Формула Паскаля: $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$

Связь: $A_n^k=C_n^k\cdot k!$