Комбинаторика на пальцах

Прошлое занятие было про перебор вариантов. Это — про то, как узнать их количество, ни одного не перебрав.

Разница не косметическая. Подмножеств у тридцати элементов миллиард, и перебрать их нельзя. А сказать, что их ровно $2^{30}$, можно мгновенно.

Два правила, из которых растёт всё остальное

Правило произведения. Если выбор делается в несколько шагов и на каждом шаге вариантов известное количество независимо от предыдущих, общее число вариантов — произведение.

Слово из трёх букв в алфавите из 26: $26 \cdot 26 \cdot 26 = 17576$. На каждое место буква выбирается независимо.

Правило суммы. Если варианты разбиты на группы, которые не пересекаются, общее число — сумма.

В одной коробке 4 предмета, в другой 7. Взять один предмет: $4 + 7 = 11$ способов. Взять по одному из каждой: $4 \cdot 7 = 28$.

Ключевое слово в обоих правилах — «не пересекаются» и «независимо». Как только это перестаёт выполняться, правила ломаются, и получается двойной счёт. К этому вернёмся отдельно.

Про размер ответа

Комбинаторные числа растут стремительно: $500!$ — это 1135 цифр. В Python это не проблема, целые числа неограниченные. В C++ пришлось бы считать по модулю.

Три базовые величины. Различаются они ответами на два вопроса: берём ли все предметы и важен ли порядок.

Перестановки. Первый предмет ставим $n$ способами, второй — $n - 1$, и так далее. По правилу произведения получается $n!$. Договорённость: $0! = 1$, потому что пустой набор расставить можно ровно одним способом.

Размещения — то же самое, но останавливаемся после $k$ шагов: $n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$.

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

Это первый пример важнейшего приёма: посчитать с повторами, а потом поделить на кратность.

Как считать сочетания на практике

Через факториалы — громоздко. Удобнее накапливать:

result = 1
for i in range(k):
    result = result * (n - i) // (i + 1)

После $i$ шагов в result лежит ровно $C_n^i$, поэтому деление всегда без остатка. И числа не разрастаются зря — а если считать факториал в тысячу, он будет в две с половиной тысячи цифр.

В Python есть готовое: math.comb(n, k) и math.factorial(n).

Из пяти человек выбирают двоих: одного капитаном, другого его заместителем.

Сколько существует вариантов?

Это главная опасность темы. Перебор, если он неверен, обычно падает или зацикливается. Формула не падает — она молча выдаёт неправильное число.

Как выглядит ошибка

Задача: сколько слов длины $n$ в алфавите a, b, c содержат хотя бы одну букву a?

Рассуждение, которое приходит первым: выберем место для буквы a — $n$ способов, остальные места заполним чем угодно — $3^{n-1}$ способов. Итого $n \cdot 3^{n-1}$.

Проверим при $n = 2$: получается $2 \cdot 3 = 6$. Выпишем руками: aa, ab, ac, ba, ca. Пять, а не шесть.

Лишним оказалось слово aa: его посчитали дважды — один раз как «a на первом месте», другой раз как «a на втором». Правило произведения здесь неприменимо: по готовому слову нельзя однозначно восстановить, какое место мы «выбирали».

Как не попасться

Проверка на маленьком случае. Возьмите $n = 2$ или $n = 3$ и выпишите варианты руками. Двадцать секунд, а ловит почти всё.

Считайте дополнение. «Хотя бы один» почти всегда удобнее считать как «все минус ни одного». Здесь: $3^n - 2^n$. При $n = 2$: $9 - 4 = 5$. Сходится.

Спросите себя: восстанавливается ли выбор однозначно? Если по итоговому объекту нельзя понять, каким путём его получили, значит какие-то объекты посчитаны не по одному разу.

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

Приём, который превращает «хотя бы один» в точную формулу, когда простое дополнение не помогает.

Задача: сколько чисел от 1 до 100 делятся на 2 или на 3?

Кратных двойке — 50, кратных тройке — 33. Но сложить нельзя: числа вроде 6 и 12 попали в оба списка. Их надо вычесть один раз — а это кратные шестёрке, их 16.

Для трёх условий формула продолжается: прибавляем поодиночке, вычитаем попарные пересечения, возвращаем тройное. Общее правило: наборы нечётного размера прибавляем, чётного — вычитаем.

for mask in range(1, 1 << k):        # все непустые наборы условий
    ...                              # пересечение условий из набора
    total += part if bits % 2 == 1 else -part

Обратите внимание: здесь снова перебор подмножеств из прошлого занятия, но перебираем мы не варианты ответа, а условия. Их обычно мало — десяток, — поэтому $2^k$ невелико.

Тем же приёмом считаются перестановки без неподвижных точек, раскладки без пустых ящиков и многое другое, где сказано «ни одного».

Двойной счёт. Разобран выше. Проверяйте формулу на $n = 2$ и $n = 3$ руками.

Перепутаны сочетания и размещения. Спросите: «если поменять выбранные предметы местами, это другой вариант?» Разные роли, разные места, разный порядок — значит размещения.

Забыто деление на кратность. Считали с повторами и не поделили. Признак: ответ ровно в $k!$ раз больше правильного.

Крайние случаи. $C_n^0 = 1$, $0! = 1$, $C_n^k = 0$ при $k > n$. Формула должна давать это сама, иначе нужны отдельные проверки.

Нулевая степень. $0^0$ в Python равно единице, и это как раз то, что нужно в комбинаторных формулах. А вот $0^n$ при $n > 0$ равно нулю — проверьте, что ваша формула это переживает.

Как проверять себя

• самое маленькое $n$: 0, 1, 2 — и выписать варианты руками;
• $k = 0$ и $k = n$ — ответ обычно должен быть единицей;
• $n$ на верхней границе — не разрослись ли промежуточные числа сверх нужного;
• сравнение с перебором для $n = 5$: напишите оба решения и сверьте.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Перед тем как писать формулу, проговорите вслух, как устроен выбор: что выбирается первым, что вторым и восстанавливается ли всё однозначно. Это защищает от двойного счёта лучше всего.

А если сомневаетесь — напишите перебор для $n = 5$ и сверьте. Приём из прошлого занятия здесь работает как проверка.

Задача: «дано $n$ до $10^{18}$; сколько существует слов длины $n$ в алфавите из трёх букв a, b, c, содержащих хотя бы одну букву a? Ответ вывести как есть, он огромный».

Ученик рассуждает: «Выберем место для буквы a — это $n$ способов. Остальные $n - 1$ мест заполним любыми буквами — это $3^{n-1}$ способов». И пишет:

n = int(input())
print(n * 3 ** (n - 1))

Проверьте это рассуждение на маленьком $n$, объясните, что с ним не так, и приведите верную формулу.