Комбинаторика для алгоритмов и программирования с нуля

Правила сложения и умножения в дискретных подсчетах

Сколько времени потребуется серверу, чтобы методом полного перебора проверить все возможные пароли из восьми символов? Если пароль состоит только из строчных латинских букв, вариантов около двухсот миллиардов. Но если разрешить заглавные буквы, цифры и спецсимволы, пространство поиска мгновенно разрастается до сотен квадриллионов. Опытный разработчик не запускает перебор в цикле, чтобы узнать его объём: он вычисляет это число за несколько секунд с помощью двух базовых законов комбинаторики — правила сложения и правила умножения.

Вся алгоритмическая комбинаторика вырастает из ответов на два практических вопроса: «Сколько всего состояний может принять система?» и «Сколько итераций совершит алгоритм в худшем случае?». Чтобы находить точные ответы без перебора элементов в памяти, нужно научиться формализовать процесс выбора.

Дискретные множества и мощность

В дискретной математике объектом подсчёта выступает множество — набор различимых элементов. Множество может содержать типы HTTP-запросов, символы алфавита, узлы графа или состояния автомата.

Мощность множества — это количество элементов, входящих в данное множество. Если множество $A$ конечно, его мощность обозначается как $|A|$.

Например, если множество статусов сетевого соединения определено как $S = \{\text{INIT}, \text{LISTEN}, \text{ESTABLISHED}, \text{CLOSED}\}$, то мощность этого множества равна четырем: $|S| = 4$.

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

Правило сложения: логика взаимоисключающего выбора

Представьте, что микросервис может получить команду на перезагрузку из двух независимых очередей сообщений: через очередь брокера Kafka (где есть 3 типа сервисных событий) или через очередь RabbitMQ (где настроено 4 типа команд). Каждое сообщение обрабатывается одинаково — система берёт ровно одну команду за такт. Сколькими способами можно выбрать одну команду? Очевидно, $3 + 4 = 7$ способами.

Этот интуитивный принцип называется правилом сложения (или правилом суммы).

Правило сложения: Если объект $A$ можно выбрать $m$ способами, а объект $B$ можно выбрать $n$ способами, причём выбор объекта $A$ исключает одновременный выбор объекта $B$ (выборы несовместны), то выбор «либо $A$, либо $B$» можно осуществить $m + n$ способами.

На языке теории множеств правило описывает объединение непересекающихся множеств. Если множества $A$ и $B$ не имеют общих элементов (их пересечение пусто: $A \cap B = \emptyset$), то мощность их объединения равна сумме их мощностей:

$$|A \cup B| = |A| + |B|$$

Разберём формулу подробно:

• $A \cup B$ — объединение множеств $A$ и $B$, то есть совокупность всех элементов, принадлежащих хотя бы одному из них;
• $|A \cup B|$ — итоговое количество доступных вариантов;
• $|A|$ и $|B|$ — количества элементов в исходных непересекающихся группах.

Пример: в меню консольной утилиты пользователь может выбрать один инструмент анализа: доступно 5 тестов производительности CPU и 3 теста памяти RAM. Тесты не пересекаются. Выбрать ровно один тест для запуска можно $|A \cup B| = 5 + 3 = 8$ способами.

В коде правило сложения проявляется как конструкция ветвления if-elif-else: мы попадаем строго в одну из взаимоисключающих веток, и общее число сценариев выполнения складывается из возможностей каждой ветки.

Правило умножения: последовательные этапы и независимость

Что произойдет, если действия выполняются не вместо друг друга, а последовательно — одно за другим?

Допустим, веб-форма требует задать двухсимвольный идентификатор сессии: первый символ — заглавная латинская буква (из множества $\{A, B, C\}$ мощностью 3), а второй символ — десятичная цифра (из множества $\{0, 1, 2, 3, 4\}$ мощностью 5). Сколько различных идентификаторов может существовать?

Для буквы $A$ есть 5 продолжений: $A0, A1, A2, A3, A4$. Для буквы $B$ — те же 5 продолжений. Для буквы $C$ — снова 5 продолжений.

Каждый из 3 вариантов первого шага порождает ровно 5 вариантов второго шага. Общее число комбинаций равно $3 \times 5 = 15$.

Правило умножения: Если действие $A$ можно выполнить $m$ способами, и после каждого такого выбора действие $B$ можно выполнить $n$ способами, то составное действие «сначала $A$, затем $B$» можно выполнить $m \times n$ способами.

В теоретико-множественных терминах правило умножения соответствует декартову произведению двух множеств:

$$|A \times B| = |A| \cdot |B|$$

Разберём составляющие формулы:

• $A \times B$ — множество всех упорядоченных пар вида $(a, b)$, где $a \in A$, а $b \in B$;
• $|A \times B|$ — общее число таких пар (комбинаций);
• $|A|$ — число выборов на первом этапе;
• $|B|$ — число выборов на втором этапе.

Практический пример: генерация тестовой матрицы. Если алгоритм нужно протестировать на 4 типах входных данных (целые, дробные, строки, null) и на 3 различных конфигурациях памяти (128 MB, 512 MB, 2 GB), то общее число тестовых прогонов матрицы составит $4 \cdot 3 = 12$.

В архитектуре программ правило умножения эквивалентно вложенным циклам for: внешний цикл совершает $m$ итераций, а внутренний на каждой итерации внешнего выполняется $n$ раз. Общее число операций тела внутреннего цикла равно $m \cdot n$.

Обобщение на $k$ этапов

Правило умножения легко расширяется на произвольное число последовательных решений. Если составной объект формируется за $k$ последовательных шагов, причём на первом шаге есть $n_1$ вариантов, на втором — $n_2$, на третьем — $n_3$, и так далее до $k$-го шага с $n_k$ вариантами, то общее количество различных составных объектов вычисляется как произведение:

$$N = n_1 \cdot n_2 \cdot n_3 \dots n_k$$

• $N$ — совокупное количество комбинаций;
• $k$ — глубина последовательности (длина цепочки выбора);
• $n_i$ — число допустимых вариантов на $i$-м шаге.

Вернемся к вопросу из начала статьи. Если пароль состоит из 8 символов, и на каждой позиции может стоять любая из 26 строчных букв латинского алфавита, то число возможных паролей составляет:

$$26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 = 26^8 \approx 2{,}088 \times 10^{11}$$

Если же мы расширяем алфавит до 62 символов (26 строчных букв + 26 заглавных + 10 цифр), то при той же длине в 8 позиций получаем уже:

$$62^8 \approx 2{,}183 \times 10^{14}$$

Пространство поиска увеличилось более чем в 1000 раз просто за счёт изменения мощности базового алфавита на каждом шаге.

Дерево решений: как увидеть умножение

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

В дереве решений правило умножения работает только при одном ключевом условии: число ветвей, выходящих из любого узла уровня $i$, должно быть строго одинаковым, какие бы конкретные альтернативы мы ни выбирали на предыдущих шагах. Сами варианты могут зависеть от контекста, но их количество обязано оставаться константой.

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

Критерий	Правило сложения	Правило умножения
Логическая связка	«ИЛИ» (выбор альтернативы)	«И» (последовательность шагов)
Операция над множествами	Объединение $A \cup B$ при $A \cap B = \emptyset$	Декартово произведение $A \times B$
Аналог в алгоритмах	Ветвление if-else, выбор маршрута	Вложенные циклы, цепочка вызовов
Формула подсчёта	$N = |A| + |B|$	$N = |A| \cdot |B|$
Результат выбора	Ровно один неделимый элемент	Составной кортеж $(a, b)$ из нескольких частей

Главная ловушка: пересекающиеся множества

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

Рассмотрим задачу: в бэкенд-сервисе зарегистрировано 100 пользователей. Из них 40 имеют роль EDITOR, а 25 — роль MODERATOR. Сколькими способами можно выбрать одного привилегированного пользователя?

Соблазн сложить $40 + 25 = 65$ приводит к ошибке, если один и тот же аккаунт может одновременно обладать обеими ролями. Допустим, 10 пользователей имеют обе роли сразу. Если мы сложим 40 и 25, эти 10 человек будут посчитаны дважды.

В таком случае истинное количество вариантов вычисляется с вычитанием дубликатов:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Для нашего примера: $40 + 25 - 10 = 55$.

Правило сложения в чистом виде ($|A| + |B|$) строго требует, чтобы множества не пересекались ($|A \cap B| = 0$). Ситуации с пересекающимися множествами подчиняются формуле включений-исключений, которую мы детально изучим в одной из следующих глав курса.

Комбинирование правил: архитектура сложных структур

На практике реальные объекты редко описываются только одной операцией. Чаще всего сложные системы требуют многоуровневого анализа: задача разбивается на взаимоисключающие классы (правило сложения), а внутри каждого класса элементы строятся по цепочке шагов (правило умножения).

Задача о синтаксисе переменной

Разберём классический пример из компиляторостроения. Требуется определить, сколько различных допустимых идентификаторов длины от 1 до 3 символов можно составить в учебном языке программирования по следующим правилам:

1. Идентификатор состоит из латинских букв (алфавит из 26 строчных букв) и цифр (от 0 до 9).
2. Первым символом идентификатора обязана быть буква.
3. Начиная со второй позиции, допускаются как буквы, так и цифры.

Шаг 1. Декомпозиция по взаимоисключающим классам (правило сложения). Идентификатор не может иметь длину 1 и длину 2 одновременно. Длины 1, 2 и 3 — это непересекающиеся сценарии:

$$N_{\text{total}} = N_1 + N_2 + N_3$$

• $N_{\text{total}}$ — общее число допустимых идентификаторов;
• $N_1, N_2, N_3$ — количество идентификаторов длины 1, 2 и 3 соответственно.

Шаг 2. Подсчёт вариантов для каждого класса (правило умножения).

• Длина 1: состоит только из первого символа, который обязан быть буквой.

  $$N_1 = 26$$

• Длина 2: первый символ — буква (26 вариантов), второй — буква или цифра ($26 + 10 = 36$ вариантов). По правилу умножения:

  $$N_2 = 26 \cdot 36 = 936$$

• Длина 3: первый символ — буква (26 вариантов), второй — буква или цифра (36 вариантов), третий — буква или цифра (36 вариантов). По правилу умножения:

  $$N_3 = 26 \cdot 36 \cdot 36 = 26 \cdot 36^2 = 33\,696$$

Шаг 3. Финальный синтез. Складываем результаты всех сценариев:

$$N_{\text{total}} = 26 + 936 + 33\,696 = 34\,658$$

Если бы компилятор проверял уникальность имени полным перебором массива в оперативной памяти, ему пришлось бы хранить и сверять почти 35 тысяч вариантов. Зная формулу, мы мгновенно оцениваем границы памяти для хэш-таблицы идентификаторов.

Связь с программным кодом: комбинаторика вместо перебора

Чтобы закрепить фундаментальную связь между правилами подсчёта и кодом, посмотрим на реализацию проверки пространства состояний на Python.

Представьте задачу: сервис авторизации генерирует проверочные коды двух видов:

• Короткий код: 1 латинская буква и 2 цифры (например, A49).
• Длинный код: 2 латинские буквы и 1 цифра (например, AB7).

Мы можем сгенерировать все коды физически через itertools.product и посчитать длину списка. Но если диапазон параметров вырастет, этот код приведет к исчерпанию оперативной памяти (Memory Limit Exceeded). Формула же выполняется за $O(1)$ процессорного времени и не требует памяти вовсе:

import string

letters = string.ascii_uppercase  # 26 букв
digits = string.digits            # 10 цифр

# Аналитический подсчет за O(1) памяти и времени:
# Вариант 1 (Буква-Цифра-Цифра): 26 * 10 * 10
# Вариант 2 (Буква-Буква-Цифра): 26 * 26 * 10
count_variant_1 = len(letters) * len(digits) * len(digits)
count_variant_2 = len(letters) * len(letters) * len(digits)

total_combinations = count_variant_1 + count_variant_2
print(f"Аналитический подсчет: {total_combinations}")
# Вывод: 2600 + 6760 = 9360

Умение декомпозировать сложную структуру на независимые альтернативы (сложение) и упорядоченные цепочки шагов (умножение) — базовый навык для построения алгоритмов. Именно эти два правила станут фундаментом для следующих тем курса: упорядоченного выбора без возвращения (размещений и перестановок) и неупорядоченного отбора (сочетаний).

Перестановки и размещения: упорядоченный выбор

Если для генерации восьмизначного пароля из 26 латинских букв доступно $26^8 \approx 2{,}08 \times 10^{11}$ вариантов, то сколько уникальных последовательностей останется, если служба безопасности запретит повторять уже использованные символы? Число вариантов мгновенно сокращается более чем втрое — до $6{,}29 \times 10^{10}$. В этот момент независимость шагов исчезает: каждый сделанный шаг безвозвратно сужает пространство вариантов для всех последующих действий.

Любая система, распределяющая уникальные ресурсы — будь то планировщик задач операционной системы, распределяющий потоки по ядрам, или алгоритм балансировки трафика между серверами, — работает именно в условиях исчерпания пула кандидатов.

Исчерпание пула: от независимых шагов к выбору без возвращения

Когда символы или события могут повторяться, каждый шаг делается из одного и того же исходного множества мощности $n$. Если нужно составить цепочку длины $k$, по правилу умножения мы получаем декартову степень множества:

$$N = n^k$$

Здесь $n$ — мощность исходного алфавита или пула ресурсов, а $k$ — количество позиций (шагов) в создаваемой последовательности. Например, если в пуле 4 микросервиса ($n = 4$), и мы регистрируем лог из 3 любых обращений ($k = 3$), где один и тот же сервис может вызываться подряд, число сценариев равно $4^3 = 64$.

Но что происходит, если ресурс нельзя использовать дважды? Представим распределенный кластер: планировщик должен назначить 3 задачи ($k = 3$) на 5 свободных физических серверов ($n = 5$), причем на каждый сервер разрешено отправить не более одной задачи.

1. Для первой задачи доступен любой из 5 серверов (5 вариантов).
2. Сервер занят. Для второй задачи остаётся выбор лишь из оставшихся 4 серверов.
3. Для третьей задачи в пуле свободно только 3 сервера.

По правилу умножения общее число допустимых конфигураций равно:

$$5 \times 4 \times 3 = 60$$

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

Такая конструкция в комбинаторике называется размещением без повторений (или $k$-перестановкой множества из $n$ элементов).

Размещения: выбор части из целого с учетом порядка

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

Обозначается как $A_n^k$ (от французского arrangement) или $P(n, k)$ в англоязычной литературе. Произведение шагов записывается как:

$$A_n^k = n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)$$

Здесь $n$ — общее число доступных уникальных элементов, $k$ — длина формируемой последовательности (при этом $0 \leq k \leq n$), а всего в произведении участвует ровно $k$ сомножителей.

Если в пуле есть 10 воркеров ($n = 10$), и нужно назначить исполнителей на 3 строго ранжированные роли (Master, Primary Replica, Fallback Replica; $k = 3$), число способов составить такой триумвират:

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

Порядок здесь критичен: узел A в роли Master и узел B в роли Replica — это совершенно иная системная конфигурация, нежели B в роли Master и A в роли Replica.

Записывать длинные цепочки убывающих сомножителей вручную неудобно. Чтобы упростить вычисления и доказательства в алгоритмах, вводят специальную операцию — факториал.

Факториал и перестановки: когда исчерпан весь пул

Что будет, если длина формируемой последовательности $k$ совпадет с мощностью множества $n$? Это означает, что мы задействуем абсолютно все доступные элементы, меняя лишь их взаимный порядок.

$$A_n^n = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

Такая операция называется перестановкой, а само произведение всех натуральных чисел от 1 до $n$ обозначается как факториал ($n!$):

Перестановка множества из $n$ элементов — это любое упорядочивание всех $n$ элементов без пропусков и повторений. Число перестановок обозначается $P_n$ и равно:

$$P_n = n!$$

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

Теперь формулу размещений $A_n^k$ можно свернуть в компактную алгебраическую форму. Если домножить и разделить произведение на «хвост» из недостающих сомножителей от $(n - k)$ до 1, получим:

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

Разберем эту формулу на составляющих:

• $n!$ — число способов упорядочить вообще все $n$ элементов системы.
• $(n - k)!$ — число способов переставить между собой те элементы, которые не попали в итоговую выборку и остались невостребованными.
• Деление буквально «схлопывает» все несущественные перестановки оставшихся неиспользованными элементов.

В практических вычислениях и коде делить факториалы напрямую не стоит: $n!$ переполняет стандартный 64-битный целочисленный тип уже при $n = 21$. Для вычисления $A_n^k$ в программах используют цикл из $k$ умножений.

def arrangements_count(n: int, k: int) -> int:
    """Вычисляет A(n, k) без переполнения факториалами."""
    if not 0 <= k <= n:
        return 0
    result = 1
    for i in range(k):
        result *= (n - i)
    return result

При $n = 60$ и $k = 2$ факториал $60! \approx 8{,}32 \times 10^{81}$ превышает число атомов в обозримой Вселенной, однако цикл выполнит всего две итерации: $60 \times 59 = 3540$.

Факториальный взрыв в алгоритмах: цена порядка

В теории алгоритмов перестановки ассоциируются с одним из самых тяжелых классов вычислительной сложности — $O(n!)$.

Представим задачу коммивояжера (TSP, Travelling Salesperson Problem): курьерский сервис должен составить маршрут объезда $n$ серверов в дата-центрах, посетив каждый ровно один раз и минимизировав задержку сети. Если серверов всего 4 (A, B, C, D), то число замкнутых путей (при фиксированной стартовой точке A) равно перестановке остальных 3 вершин:

$$P_3 = 3! = 6$$

Полный перебор 6 вариантов в памяти занимает микросекунды. Но зависимость $n!$ растет быстрее экспоненты $2^n$ и даже быстрее $n^c$:

$n$	$n!$	Время перебора при $10^9$ операций/сек
5	120	0,00012 мс
10	3 628 800	3,63 мс
12	479 001 600	0,48 с
15	$1{,}31 \times 10^{12}$	~21,8 минут
20	$2{,}43 \times 10^{18}$	~77 лет
25	$1{,}55 \times 10^{25}$	~492 миллиона лет

Именно поэтому алгоритмы, генерирующие все перестановки полным перебором (brute-force), применимы только для крошечных входных массивов ($n \leq 10\dots12$). Для больших $n$ в Computer Science прибегают к динамическому программированию или приближенным эвристикам.

Перестановки с повторениями: учет тождественных элементов

До сих пор мы считали, что все элементы исходного множества уникальны. Однако в реальных данных объекты часто дублируются.

Классический пример из алгоритмических собеседований: сколько уникальных анаграмм (строк) можно составить из букв слова SUCCESS?

Длина слова $n = 7$. Если бы все буквы были помечены индексами и различимы (S₁, U₁, C₁, C₂, E₁, S₂, S₃), общее число перестановок равнялось бы $7! = 5040$.

Однако в слове есть дубликаты:

• Буква S встречается 3 раза.
• Буква C встречается 2 раза.
• Буквы U и E — по 1 разу.

Любая перестановка трех букв S между собой ($3! = 6$ вариантов) внутри слова визуально не меняет строку: S₁S₂S₃... и S₃S₂S₁... для строкового компаратора неотличимы. Точно так же перестановка двух букв C дает $2! = 2$ неразличимых состояния.

Поскольку эти перестановки независимы, для каждого уникального внешнего вида строки мы посчитали лишние варианты $3! \times 2! \times 1! \times 1!$ раз. Чтобы убрать избыточность, общее число перестановок нужно разделить на факториалы кратностей одинаковых элементов:

$$P(n; n_1, n_2, \dots, n_m) = \frac{n!}{n_1! \, n_2! \dots n_m!}$$

Элементы формулы:

• $n$ — суммарная длина последовательности ($n = n_1 + n_2 + \dots + n_m$).
• $n_1, n_2, \dots, n_m$ — количество повторений (кратность) каждого уникального типа элемента.
• $n_i!$ — факториал кратности $i$-го типа, компенсирующий внутренние перестановки тождественных объектов.

Для слова SUCCESS:

$$\frac{7!}{3! \times 2! \times 1! \times 1!} = \frac{5040}{6 \times 2 \times 1 \times 1} = \frac{5040}{12} = 420$$

Применение в алгоритмах: пути на сетке (Grid Travel)

Эта же формула решает классическую задачу динамического программирования: сколькими способами робот может пройти из левой верхней клетки $(0, 0)$ в правую нижнюю клетку $(W, H)$ прямоугольной сетки, если он может двигаться только вправо ($R$) и вниз ($D$)?

Чтобы дойти до цели, роботу необходимо сделать ровно $W$ шагов вправо и $H$ шагов вниз. Суммарное количество шагов фиксировано: $n = W + H$. Любой валидный маршрут — это просто уникальная строка длины $W + H$, состоящая из $W$ символов R и $H$ символов D.

Число путей равно перестановкам с повторениями:

$$\frac{(W + H)!}{W! \, H!}$$

Если сетка имеет размер $4 \times 3$, роботу нужно 4 шага вправо и 3 шага вниз:

$$\frac{(4 + 3)!}{4! \times 3!} = \frac{7!}{4! \times 3!} = \frac{5040}{24 \times 6} = 35$$

Выбор модели: сводная система ориентиров

Чтобы безошибочно определять инструмент при анализе алгоритмической задачи, достаточно ответить на два вопроса:

1. Важен ли порядок элементов? (В этой главе мы рассматривали только задачи, где порядок критичен).
2. Используются ли элементы повторно или пул исчерпывается?

Тип выборки	Элементы в пуле	Длина цепочки	Формула	Пример в разработке
С повторениями (степень)	Неограниченны	Любая $k$	$n^k$	Генерация PIN-кодов, подбор хэша
Размещения без повторений	Уникальны	$k \leq n$	$\frac{n!}{(n-k)!}$	Назначение $k$ уникальных ролей из $n$ серверов
Перестановки без повторений	Уникальны	Все $n$	$n!$	Очередь выполнения $n$ задач, маршрут TSP
Перестановки с повторениями	Сгруппированы по типам	Все $n$	$\frac{n!}{n_1! \dots n_m!}$	Маршруты в матрице, анаграммы токенов

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

Сочетания и биномиальные коэффициенты

Когда порядок элементов имеет значение, задача сводится к размещениям: если из 10 микросервисов нужно выбрать три для выполнения строго специализированных ролей Master, Worker и Logger, существует ровно $10 \times 9 \times 8 = 720$ вариантов. Но что происходит, если роли абсолютно одинаковы? Например, балансировщик выбирает 3 равноправных сервера из 10 для репликации базы данных. Теперь тройка (A, B, C) ничем не отличается от (B, A, C) или (C, B, A). Если посчитать их как 720 вариантов, мы многократно продублируем одну и ту же рабочую конфигурацию. Как математически строго избавиться от избыточного порядка и вычислить число уникальных неупорядоченных подмножеств?

Факторизация порядка: переход от размещений к сочетаниям

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

Сочетание из $n$ элементов по $k$ — это любое неупорядоченное подмножество мощности $k$, составленное из элементов исходного множества мощности $n$.

Обозначается число таких сочетаний символом $C_n^k$ или биномиальным коэффициентом $\binom{n}{k}$ (читается как «$C$ из $n$ по $k$» или «биномиальный коэффициент $n$ по $k$»).

Чтобы найти $\binom{n}{k}$, применим принцип факторизации (сжатия) пространства вариантов. Пусть мы уже умеем вычислять число размещений без повторений $A_n^k$. Каждое конкретное неупорядоченное подмножество из $k$ элементов порождает внутри себя ровно $k!$ перестановок. Поскольку все эти $k!$ перестановок соответствуют одной и той же группе узлов, общее число размещений $A_n^k$ склеивает сочетания в группы по $k!$ штук в каждой:

$$A_n^k = \binom{n}{k} \times k!$$

• $A_n^k$ — общее число упорядоченных выборок длины $k$ из $n$ элементов;
• $\binom{n}{k}$ — количество уникальных неупорядоченных подмножеств;
• $k!$ — число способов переставить элементы внутри одного фиксированного подмножества.

Практический пример: если выбраны серверы $\{S_1, S_2, S_3\}$, то для $k = 3$ существует $3! = 3 \times 2 \times 1 = 6$ упорядоченных кортежей: $(S_1, S_2, S_3)$, $(S_1, S_3, S_2)$, $(S_2, S_1, S_3)$, $(S_2, S_3, S_1)$, $(S_3, S_1, S_2)$, $(S_3, S_2, S_1)$. Для задачи кластеризации все 6 кортежей описывают одну и ту же группу.

Выражая $\binom{n}{k}$ через отношение упорядоченного выбора к числу внутренних перестановок, получаем базовую формулу:

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

• $n!$ — факториал мощности базового множества;
• $k!$ в знаменателе устраняет учет порядка между выбранными элементами;
• $(n - k)!$ в знаменателе отсекает невыбранные элементы (остаток пула).

Для выбора 3 реплик из 10 серверов расчет дает:

$$\binom{10}{3} = \frac{10!}{3! \times (10 - 3)!} = \frac{10 \times 9 \times 8 \times 7!}{6 \times 7!} = \frac{720}{6} = 120$$

Вместо 720 вариантов конфигураций кластера алгоритм должен оперировать лишь 120 уникальными состояниями.

Критерий	Размещения $A_n^k$	Сочетания $\binom{n}{k}$
Учет порядка	Порядок критичен: $(A, B) \neq (B, A)$	Порядок безразличен: $\{A, B\} = \{B, A\}$
Математический объект	Кортеж / упорядоченный список	Множество / подмножество
Связь величин	$A_n^k = \binom{n}{k} \times k!$	$\binom{n}{k} = \frac{A_n^k}{k!}$
Пример в коде	Назначение уникальных портов сервисам	Выбор кворума узлов для консенсуса

Рекуррентное свойство и треугольник Паскаля

Прямое вычисление через факториалы $\frac{n!}{k!(n - k)!}$ в коде быстро приводит к целочисленному переполнению: значение $21!$ уже превышает разрядность 64-битного целого числа uint64. Комбинаторная природа сочетаний позволяет обойти факториалы с помощью рекуррентного разложения.

Рассмотрим произвольный фиксированный элемент множества — назовем его «элемент $X$». Все возможные подмножества размера $k$ из $n$ кандидатов распадаются на два непересекающихся класса:

1. Подмножества, содержащие элемент $X$. Чтобы собрать такое подмножество, мы принудительно берем $X$, а оставшиеся $k - 1$ элементов добираем из оставшихся $n - 1$ кандидатов. Число способов: $\binom{n - 1}{k - 1}$.
2. Подмножества, не содержащие элемент $X$. Мы полностью исключаем $X$ из рассмотрения и набираем все $k$ элементов из оставшихся $n - 1$ кандидатов. Число способов: $\binom{n - 1}{k}$.

По правилу сложения для непересекающихся классов получаем тождество Паскаля:

$$\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$$

• $\binom{n}{k}$ — общее число искомых сочетаний;
• $\binom{n - 1}{k - 1}$ — ветвь, где текущий элемент включен в подвыборку;
• $\binom{n - 1}{k}$ — ветвь, где текущий элемент пропущен.

Это рекуррентное правило порождает треугольник Паскаля — геометрическую таблицу биномиальных коэффициентов, где каждое внутреннее число равно сумме двух чисел, стоящих прямо над ним.

В программировании тождество Паскаля лежит в основе табличного динамического программирования: матрица биномиальных коэффициентов заполняется за время $O(n \times k)$ с использованием исключительно операции сложения, исключая операции умножения и деления больших чисел.

Алгебраические свойства биномиальных коэффициентов

Биномиальные коэффициенты обладают фундаментальными симметриями, которые оптимизируют как комбинаторные оценки, так и производительность алгоритмов.

1. Свойство симметрии (комплементарность)

Выбрать подмножество из $k$ элементов — это в точности то же самое, что выбрать $n - k$ элементов, которые не войдут в это подмножество:

$$\binom{n}{k} = \binom{n}{n - k}$$

Практический пример: если из пула в 100 тестовых сценариев нужно выбрать 98 для ночного прогона, вычисление $\binom{100}{98}$ сводится к выбору $100 - 98 = 2$ тестов, которые будут пропущены:

$$\binom{100}{98} = \binom{100}{2} = \frac{100 \times 99}{2 \times 1} = 4950$$

Вместо перемножения десятков множителей алгоритм выполняет ровно две операции умножения и одно деление.

2. Сумма биномиальных коэффициентов и мощность булеана

Если сложить значения $\binom{n}{k}$ по всем возможным размерам подмножеств от $k = 0$ (пустое множество) до $k = n$ (само исходное множество), мы получим мощность булеана — множества всех подмножеств:

$$\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} = 2^n$$

• $n$ — число элементов в исходном множестве;
• $\binom{n}{k}$ — количество подмножеств фиксированного размера $k$;
• $2^n$ — общее число всех возможных конфигураций включения/исключения элементов.

Этот результат напрямую соотносится с правилом умножения: для каждого из $n$ независимых элементов у нас есть ровно 2 исхода — включить его в подмножество (бит 1) или проигнорировать (бит 0). Сложение сочетаний по всем размерам дает пространство состояний битовой маски длины $n$.

Формула бинома Ньютона

Свое название биномиальные коэффициенты получили благодаря роли в раскрытии степеней двучлена (бинома). При возведении суммы $(a + b)$ в натуральную степень $n$ мы перемножаем $n$ одинаковых скобок:

$$(a + b)^n = \underbrace{(a + b)(a + b)\dots(a + b)}_{n \text{ скобок}}$$

Каждое слагаемое в раскрытом выражении получается выбором либо слагаемого $a$, либо слагаемого $b$ из каждой скобки. Чтобы получить однородный моном вида $a^{n-k}b^k$, мы обязаны выбрать множитель $b$ ровно из $k$ скобок, а множитель $a$ — из оставшихся $n - k$ скобок.

Количество способов выбрать $k$ скобок из доступных $n$ в точности равно числу сочетаний $\binom{n}{k}$. Отсюда следует теорема о биноме Ньютона:

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

• $(a + b)^n$ — развертываемая степень бинома;
• $\binom{n}{k}$ — биномиальный коэффициент, определяющий кратность слагаемого с сомножителем $b^k$;
• $a^{n-k}b^k$ — моном, составленный из $n-k$ выборов переменной $a$ и $k$ выборов переменной $b$.

Практический пример: разложим выражение для трех параллельных узлов обработки $(x + y)^3$:

$$(x + y)^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3}y^3 = 1x^3 + 3x^2y + 3xy^2 + 1y^3$$

Коэффициенты $1, 3, 3, 1$ в точности совпадают с третьей строкой треугольника Паскаля. Если положить $a = 1$ и $b = 1$, бином Ньютона превращается в тождество суммы подмножеств: $(1 + 1)^n = 2^n$.

Практический синтез: комбинаторика транзакционных пулов

Продемонстрируем работу изученных структур на прикладной инженерной задаче. Пусть в пуле валидации находятся 8 транзакций: 5 стандартных пользовательских платежей и 3 системных смарт-контракта. Блокчейн-клиент формирует блок, состоящий ровно из 4 транзакций. Каково число способов сформировать блок так, чтобы в него вошел хотя бы один смарт-контракт?

Эту задачу можно решить двумя путями, объединяющими правила декомпозиции и биномиальные формулы.

Прямой подсчет через разбиение на классы

Блок из 4 транзакций может содержать 1, 2 или 3 смарт-контракта (больше трех взять невозможно, так как их всего 3). Эти сценарии не пересекаются, поэтому применим правило сложения:

1. Ровно 1 смарт-контракт: выбираем 1 из 3 контрактов и добираем $4 - 1 = 3$ обычных платежа из 5 доступных:

   $$\binom{3}{1} \times \binom{5}{3} = 3 \times \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 3 \times 10 = 30$$

2. Ровно 2 смарт-контракта: выбираем 2 из 3 контрактов и 2 обычных платежа из 5:

   $$\binom{3}{2} \times \binom{5}{2} = 3 \times 10 = 30$$

3. Ровно 3 смарт-контракта: выбираем все 3 доступных контракта и 1 обычный платеж из 5:

   $$\binom{3}{3} \times \binom{5}{1} = 1 \times 5 = 5$$

Суммируя взаимоисключающие классы: $30 + 30 + 5 = 65$ допустимых блоков.

Метод дополнения (инверсный подсчет)

Вместо сложения нескольких комбинаций вычислим общее число произвольных четверок и вычтем недопустимые (те, где нет ни одного смарт-контракта):

• Общее число способов выбрать любые 4 транзакции из 8 доступных:

  $$\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$$

• Число «пустых» блоков (все 4 транзакции выбраны только из 5 обычных платежей):

  $$\binom{5}{4} = \binom{5}{1} = 5$$

• Итоговое число валидных комбинаций:

  $$\binom{8}{4} - \binom{5}{4} = 70 - 5 = 65$$

Оба метода привели к идентичному результату. Метод дополнения потребовал существенно меньше вычислительных шагов за счет комбинаторного свойства симметрии $\binom{5}{4} = \binom{5}{1}$ и исключения промежуточных подклассов.

Комбинации с повторениями и метод перегородок

Если в корзине лежат красные, синие и зеленые шары с неограниченным запасом каждого цвета, сколькими способами можно достать ровно пять штук? Обычные формулы перестановок бессильны: порядок извлечения не имеет значения (три красных и два синих — это тот же набор, что и два синих и три красных). Формула классических сочетаний $\binom{n}{k}$ тоже не сработает: в ней элементы множества уникальны, каждый берется не более одного раза, а здесь цвет можно дублировать вплоть до всех пяти раз.

Кажется, что отсутствие уникальности усложняет подсчет, но в дискретной математике существует элегантный прием, превращающий неразличимые объекты в привычные биномиальные коэффициенты. Этот прием называется методом перегородок (Stars and Bars).

Идея перегородок: как закодировать выбор корзинами

Сформулируем задачу в терминах программирования. Пусть у нас есть $k$ одинаковых вычислительных задач (например, фоновых джобов), которые нужно распределить между $n$ воркерами в кластере. Задачи абсолютно одинаковы (нам важно только их количество у каждого воркера), а воркеры различимы — у каждого есть свой уникальный идентификатор. Некоторые воркеры могут остаться без задач вовсе.

Представим наши $k$ задач в виде неразличимых предметов — звездочек:

$$\star \quad \star \quad \star \quad \star \quad \star$$

Чтобы распределить их между $n$ воркерами, разделим этот ряд предметов вертикальными чертами (перегородками). Сколько перегородок понадобится, чтобы разбить одну полосу на $n$ отсеков? Ровно $n - 1$:

• 1 перегородка делит ряд на 2 отсека;
• 2 перегородки делят ряд на 3 отсека;
• $n - 1$ перегородок делят ряд на $n$ отсеков.

Посмотрим на пример: пусть $k = 5$ задач распределяются по $n = 3$ воркерам. Нам нужно $3 - 1 = 2$ перегородки. Запись вида:

$$\star \star \mid \star \mid \star \star$$

означает: первый воркер получил 2 задачи, второй — 1 задачу, третий — 2 задачи.

А что, если перегородки стоят подряд или с краю?

$$\mid \star \star \star \mid \star \star$$

В этом случае первый воркер получил 0 задач, второй — 3 задачи, третий — 2 задачи. Две перегородки подряд без звездочек между ними означают, что соответствующему отсеку досталось 0 предметов.

Любое возможное распределение взаимно однозначно кодируется цепочкой из символов двух типов: предметов ($\star$) и перегородок ($\mid$).

Вывод формулы сочетаний с повторениями

Посчитаем общую длину получившейся символьной строки:

• Всего предметов: $k$.
• Всего перегородок: $n - 1$.
• Общее число позиций в цепочке: $k + (n - 1) = n + k - 1$.

Чтобы однозначно задать конфигурацию, нам достаточно из всех $n + k - 1$ доступных позиций выбрать те, на которых будут стоять перегородки. Все оставшиеся места автоматически займут звездочки. Либо наоборот: выбрать места для $k$ звездочек среди всех доступных позиций. По свойству симметрии биномиальных коэффициентов оба варианта дают одно и то же число:

$$\binom{n + k - 1}{n - 1} = \binom{n + k - 1}{k}$$

Элементы формулы:

• $n$ — количество категорий (типов предметов, контейнеров или приемников);
• $k$ — количество неразличимых предметов, которые мы выбираем или распределяем;
• $n - 1$ — число разделителей между категориями;
• $\binom{n + k - 1}{k}$ — число способов расставить $k$ предметов по $n$ ячейкам.

Сочетание с повторениями из $n$ элементов по $k$ — это неупорядоченный набор длины $k$, составленный из элементов $n$ сортов, где каждый сорт может встречаться произвольное количество раз. Число таких наборов обозначается $\left(\binom{n}{k}\right)$ или $\bar{C}_n^k$ и вычисляется как $\binom{n + k - 1}{k}$.

Вернемся к нашему вводному вопросу: сколькими способами можно выбрать 5 шаров из корзины с 3 цветами (красный, синий, зеленый)? Здесь количество сортов $n = 3$, а объем выборки $k = 5$:

$$\binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2} = \frac{7 \times 6}{2 \times 1} = 21$$

Всего существует 21 уникальная мультимножественная комбинация цветов.

Диофантовы уравнения: неотрицательные целые решения

В анализе алгоритмов часто возникает задача подсчета числа конфигураций ресурсов, которая сводится к уравнению в целых числах.

Пусть распределенная база данных делит квоту на чтение из 10 параллельных соединений между 4 независимыми узлами-репликами $x_1, x_2, x_3, x_4$. Каждому узлу можно выделить любое неотрицательное число соединений (включая 0). Сколько существует способов распределить эту нагрузку?

Математически это записывается как поиск количества целых решений уравнения:

$$x_1 + x_2 + x_3 + x_4 = 10, \quad \text{где } x_i \geq 0$$

Каждая переменная $x_i$ — это количество предметов, попавших в $i$-й контейнер. Это в точности модель перегородок:

• Сумма предметов $k = 10$;
• Количество слагаемых (контейнеров) $n = 4$;
• Число разделителей: $n - 1 = 3$.

Применяем выведенную формулу:

$$\binom{4 + 10 - 1}{10} = \binom{13}{10} = \binom{13}{3} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 286$$

Существует ровно 286 способов распределить лимит соединений. Любое линейное уравнение с коэффициентами 1 при переменных и ограничением $x_i \geq 0$ решается именно этой комбинаторной конструкцией.

Задача с ограничениями: когда контейнеры не могут быть пустыми

Что изменится, если система требует обязательного присутствия каждого ресурса? Предположим, каждый узел обязан получить хотя бы одно соединение, то есть $x_i \geq 1$.

В терминах перегородок это означает запрет на пустые ячейки: перегородки не могут стоять на концах ряда и не могут стоять вплотную друг к другу.

Существует два равносильных способа справиться с этим ограничением.

Способ 1. Замена переменных (жадная предоплата)

Если каждому узлу положено минимум одно соединение, выделим им по 1 соединению заранее. Из общего бюджета в 10 соединений мы гарантированно отдаем 4:

$$10 - 4 = 6$$

Осталось распределить 6 свободных соединений между 4 узлами без каких-либо нижних ограничений (теперь каждый может получить еще 0 или больше).

Обозначим $y_i = x_i - 1$, где $y_i \geq 0$. Уравнение принимает вид:

$$y_1 + y_2 + y_3 + y_4 = 6$$

Теперь применяем стандартную формулу перегородок для $k = 6$ и $n = 4$:

$$\binom{4 + 6 - 1}{6} = \binom{9}{6} = \binom{9}{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$$

Способ 2. Выбор промежутков между предметами

Посмотрим на $k$ предметов, выстроенных в ряд. Между ними ровно $k - 1$ внутренних зазоров:

$$\star \ \sqcup \ \star \ \sqcup \ \star \ \dots \ \sqcup \ \star$$

Если нам нужно гарантировать, что каждый отсек получит хотя бы один предмет, мы обязаны поместить $n - 1$ перегородок строго в эти зазоры, причем не более одной перегородки в один зазор.

Это классический выбор $n - 1$ позиций из $k - 1$ доступных без повторений:

$$\binom{k - 1}{n - 1}$$

Для наших значений $k = 10$ и $n = 4$:

$$\binom{10 - 1}{4 - 1} = \binom{9}{3} = 84$$

Оба метода приводят к идентичному результату, но метод сдвига переменных универсальнее: он работает для любых нижних границ (например, если узлу $x_1$ требуется не менее 3 соединений, а узлу $x_2$ — не менее 2).

Систематизация: четыре базовые схемы выбора

Мы подошли к моменту, когда все основные типы подсчета независимых элементов складываются в единую систему. В комбинаторике ее часто называют «четырьмя путями» выбора $k$ объектов из $n$ сортов:

Схема выбора	Порядок важен (последовательности)	Порядок не важен (подмножества / мультимножества)
Без повторений (каждый объект берется максимум 1 раз)	Размещения: $A_n^k = \frac{n!}{(n-k)!}$	Сочетания: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
С повторениями (объекты каждого сорта доступны неограниченно)	Размещения с повторениями: $n^k$	Сочетания с повторениями: $\binom{n + k - 1}{k}$

Разница между строками — в механике возвращения элементов в пул. Разница между столбцами — в том, различаем ли мы перестановку элементов внутри результата.

Практический алгоритмический кейс: монотонные векторы и генерация состояний

В задачах динамического программирования часто требуется перебрать или оценить размер пространства монотонно неубывающих последовательностей.

Допустим, оптимизатор запросов строит план доступа для фильтра по индексам. Нам нужно сгенерировать все целочисленные кортежи длины $k = 3$, элементы которых удовлетворяют условию:

$$1 \leq a_1 \leq a_2 \leq a_3 \leq 5$$

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

Каждый такой кортеж однозначно задается мультимножеством из 3 чисел, выбранных из диапазона $\{1, 2, 3, 4, 5\}$. Действительно, если мы выбрали мультимножество $\{4, 1, 4\}$, то существует ровно один способ упорядочить его по неубыванию: $(1, 4, 4)$.

Следовательно, количество неубывающих последовательностей длины $k$ из алфавита мощности $n$ в точности равно числу сочетаний с повторениями из $n$ по $k$:

$$\binom{n + k - 1}{k} = \binom{5 + 3 - 1}{3} = \binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$$

Сравните это с общим числом всех последовательностей из 3 элементов от 1 до 5: по правилу произведения их $5^3 = 125$. Пространство монотонных состояний составляет меньше трети от полного декартова произведения, и метод перегородок позволяет сразу выделить этот объем памяти без предварительного отсеивающего перебора.

Принцип Дирихле и формула включений-исключений

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

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

Принцип Дирихле: неизбежность коллизий

Принцип Дирихле (в англоязычной литературе — pigeonhole principle, «принцип голубей и ящиков») формулируется обманчиво просто:

Если $n$ предметов разложить по $k$ ящикам и $n > k$, то хотя бы в одном ящике окажется не менее двух предметов.

Этот факт опирается на доказательство от противного. Предположим обратное: в каждом из $k$ ящиков находится не более одного предмета. Тогда суммарное число предметов не может превосходить $1 \times k = k$. Но по исходному условию предметов $n > k$. Полученное противоречие строго доказывает утверждение.

В программировании ящики — это дискретные классы эквивалентности (значения хеш-функции, остатки от деления, ячейки памяти), а предметы — обрабатываемые данные.

Классический пример неизбежности коллизий — хеширование. Пусть 32-битная хеш-функция генерирует $2^{32}$ возможных значений (около $4{,}29 \times 10^9$). Как только система обрабатывает $2^{32} + 1$ уникальную строку, совпадение хешей двух разных строк математически неизбежно. Никакой идеальный алгоритм хеширования не способен это предотвратить: мощность множества входных сообщений строго больше мощности пространства хеш-значений.

Обобщённая форма принципа

В практических задачах часто требуется оценить не просто факт наличия дубликата, а минимальную плотность скопления элементов.

Если $n$ предметов распределены по $k$ ящикам, то хотя бы в одном ящике содержится не менее $\lceil n / k \rceil$ предметов, а также хотя бы в одном ящике — не более $\lfloor n / k \rfloor$ предметов.

Здесь $\lceil x \rceil$ обозначает округление вверх до ближайшего целого (потолок), а $\lfloor x \rfloor$ — округление вниз (пол).

Рассмотрим распределение нагрузки в бэкенд-кластере. Пусть балансировщик распределил 105 входящих запросов по 10 вычислительным нодам. Сколько запросов гарантированно примет самый загруженный сервер?

$$m = \left\lceil \frac{105}{10} \right\rceil = \lceil 10{,}5 \rceil = 11$$

Формула гарантирует, что при любой работе балансировщика найдётся нода, обрабатывающая как минимум 11 запросов. Если бы все ноды получили не более 10 запросов, суммарный объем обработанных задач составил бы максимум $10 \times 10 = 100$, что противоречит общему числу в 105 запросов.

Принцип Дирихле отвечает на вопрос качественного характера: «Существует ли коллизия или превышение порога?». Однако он не дает ответа на вопрос количественный: «Сколько именно элементов принадлежит пересечению нескольких классов?». Для точного количественного учета перекрывающихся структур необходим аппарат включений-исключений.

Формула включений-исключений для двух и трех множеств

При сложении мощностей двух непересекающихся множеств выполняется правило суммы: $|A \cup B| = |A| + |B|$. Но если множества пересекаются, простая сумма учитывает общую зону $|A \cap B|$ дважды. Чтобы восстановить баланс, избыток необходимо вычесть:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Когда множеств становится три, ситуация усложняется. Сложив мощности $|A| + |B| + |C|$, мы дважды посчитали попарные пересечения и трижды — центральную область, где пересекаются все три множества. Вычитание попарных пересечений $- |A \cap B| - |A \cap C| - |B \cap C|$ компенсирует лишние дубли, однако центральная зона $|A \cap B \cap C|$, будучи добавленной 3 раза и затем вычтенной 3 раза, исчезает из подсчета целиком. Её требуется вернуть:

$$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$

Общая формула для $n$ множеств

Этот процесс чередования знаков обобщается на любое конечное число множеств $A_1, A_2, \dots, A_n$.

Принцип включений-исключений (Inclusion-Exclusion Principle):

Мощность объединения $n$ конечных множеств равна сумме мощностей отдельных множеств, минус суммы мощностей всех попарных пересечений, плюс суммы мощностей пересечений по три множества, и так далее, с чередованием знаков:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$$

В этой формуле:

• Первая сумма перебирает все $\binom{n}{1} = n$ отдельных множеств.
• Вторая сумма содержит $\binom{n}{2}$ слагаемых для всех уникальных пар.
• Каждая последующая группа суммирует пересечения троек, четверок и так далее, всего $2^n - 1$ слагаемых.
• Множитель $(-1)^{m-1}$ определяет знак слагаемого: нечетные размеры пересечений прибавляются ($+$), четные — вычитаются ($-$).

Чтобы строго понять, почему формула верна, проследим за вкладом произвольного элемента $x$, принадлежащего ровно $m$ множествам из $n$ (где $1 \leq m \leq n$). Сколько раз его учтет правая часть формулы?

Элемент $x$ входит в $m$ множеств первого уровня, в $\binom{m}{2}$ попарных пересечений, в $\binom{m}{3}$ тройных пересечений и так далее до $\binom{m}{m}$. Его суммарный вклад равен:

$$\text{Вклад } x = \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \dots + (-1)^{m-1}\binom{m}{m}$$

Из бинома Ньютона известно разложение для $(1 - 1)^m$:

$$(1 - 1)^m = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \binom{m}{3} + \dots + (-1)^m \binom{m}{m} = 0$$

Поскольку $\binom{m}{0} = 1$, перенесем оставшиеся члены в противоположную сторону равенства:

$$1 = \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \dots + (-1)^{m-1}\binom{m}{m}$$

Правая часть в точности совпадает с суммарным вкладом элемента $x$. Каждый элемент объединения учитывается ровно 1 раз, независимо от того, в скольких множествах он одновременно состоит.

Дополнение: подсчет элементов вне объединения

В алгоритмических задачах чаще требуется найти количество объектов универсума $U$, которые не обладают ни одним из $n$ запрещенных свойств (обозначим множества нарушителей как $A_1, A_2, \dots, A_n$).

По закону де Моргана, дополнение объединения множеств равно пересечению их дополнений:

$$\left| \bigcap_{i=1}^n \overline{A_i} \right| = |U| - \left| \bigcup_{i=1}^n A_i \right|$$

Подставляя развернутую формулу, получаем:

$$|U| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \dots$$

Практический расчет: фильтрация адресного пространства

Пусть распределенная сеть выделяет диапазон целочисленных идентификаторов $U = \{1, 2, \dots, 1000\}$. Идентификатор считается рабочим, если он не делится на 2, не делится на 3 и не делится на 5 (эти адреса зарезервированы системными шинами). Сколько рабочих ID доступно для клиентов?

Определим запрещенные множества:

• $A_2$ — числа, делящиеся на 2. Их количество: $\lfloor 1000 / 2 \rfloor = 500$.
• $A_3$ — числа, делящиеся на 3. Их количество: $\lfloor 1000 / 3 \rfloor = 333$.
• $A_5$ — числа, делящиеся на 5. Их количество: $\lfloor 1000 / 5 \rfloor = 200$.

Пересечения соответствуют делению на наименьшее общее кратное (для взаимно простых делителей — на их произведение):

• $|A_2 \cap A_3| = \lfloor 1000 / 6 \rfloor = 166$
• $|A_2 \cap A_5| = \lfloor 1000 / 10 \rfloor = 100$
• $|A_3 \cap A_5| = \lfloor 1000 / 15 \rfloor = 66$
• $|A_2 \cap A_3 \cap A_5| = \lfloor 1000 / 30 \rfloor = 33$

Считаем размер запрещенного пула по формуле включений-исключений:

$$|A_2 \cup A_3 \cup A_5| = (500 + 333 + 200) - (166 + 100 + 66) + 33 = 1033 - 332 + 33 = 734$$

Следовательно, количество свободных рабочих адресов составляет:

$$|U \setminus (A_2 \cup A_3 \cup A_5)| = 1000 - 734 = 266$$

Задача о беспорядках (Derangements)

Ярким применением формулы включений-исключений является классическая комбинаторная задача о беспорядках.

Беспорядок порядка $n$ ($D_n$ или $!n$) — это перестановка элементов множества $\{1, 2, \dots, n\}$, в которой ни один элемент не остается на своей исходной позиции (то есть для всех $i$ выполняется $\pi(i) \neq i$).

В системном программировании эта задача возникает при анализе случайных перестановок: какова вероятность, что после перетасовки пула потоков ни один поток не вернется на прежнее ядро процессора? Или при проверке тестов: сколькими способами можно распределить $n$ секретных ключей между $n$ сервисами так, чтобы ни один сервис не получил собственный ключ?

Пусть универсум $U$ — это множество всех возможных перестановок из $n$ элементов. Его мощность равна $|U| = n!$.

Определим свойство $A_i$ как множество перестановок, где элемент $i$ остался на своем месте: $\pi(i) = i$.

• Зафиксировав позицию одного элемента $i$, остальные $n - 1$ элементов мы вольны переставлять как угодно. Значит, $|A_i| = (n - 1)!$. Всего таких одиночных условий $\binom{n}{1} = n$.
• Для двух зафиксированных элементов $\pi(i) = i$ и $\pi(j) = j$ число способов переставить остальные элементы равно $(n - 2)!$. Всего таких пар существует $\binom{n}{2}$.
• Для $k$ зафиксированных элементов мощность пересечения равна $(n - k)!$, а число таких сочетаний — $\binom{n}{k}$.

Применим формулу дополнения для подсчета перестановок, не обладающих ни одним из свойств $A_i$:

$$D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \dots + (-1)^n \binom{n}{n}(n-n)!$$

Распишем биномиальный коэффициент $\binom{n}{k} = \frac{n!}{k!(n-k)!}$:

$$\binom{n}{k}(n-k)! = \frac{n!}{k!(n-k)!} \times (n-k)! = \frac{n!}{k!}$$

Подставляя это упрощение в каждый член ряда, получаем:

$$D_n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \dots + (-1)^n \frac{n!}{n!}$$

Вынесем общий множитель $n!$ за скобки:

$$D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$

Посчитаем число беспорядков для небольших значений $n$:

$n$	Общее число перестановок ($n!$)	Выражение для $D_n$	Число беспорядков ($D_n$)	Доля беспорядков ($D_n / n!$)
1	1	$1 \times (1 - 1)$	0	0{,}0000
2	2	$2 \times (1 - 1 + 1/2)$	1	0{,}5000
3	6	$6 \times (1 - 1 + 1/2 - 1/6)$	2	0{,}3333
4	24	$24 \times (1/2 - 1/6 + 1/24)$	9	0{,}3750
5	120	$120 \times (9/24 - 1/120)$	44	0{,}3667

Заметим, что сумма в скобках представляет собой частичную сумму ряда Тейлора для функции $e^x$ в точке $x = -1$:

$$e^{-1} = \frac{1}{e} = \sum_{k=0}^\infty \frac{(-1)^k}{k!} \approx 0{,}367879\dots$$

Это приводит к фундаментальному выводу: с ростом $n$ вероятность того, что случайно выбранная перестановка окажется беспорядком, стремительно сходится к константе:

$$\lim_{n \to \infty} \frac{D_n}{n!} = \frac{1}{e} \approx 36{,}8\%$$

Даже если в пуле находится миллион серверов, вероятность того, что при случайном перемешивании абсолютно каждый сервер сменит свой порядковый номер, составляет приблизительно $36{,}8\%$.

Связь с диофантовыми уравнениями и верхними ограничениями

Ранее метод перегородок позволил нам находить число целочисленных решений уравнений вида $x_1 + x_2 + \dots + x_k = S$ при условии $x_i \geq 0$ или с нижними границами $x_i \geq c_i$. Однако метод перегородок принципиально бессилен, если на переменные наложены верхние границы вида $x_i \leq M_i$.

В таких ситуациях на помощь приходит формула включений-исключений.

Пусть требуется распределить 12 однотипных вычислительных пакетов между 3 контейнерами: $x_1 + x_2 + x_3 = 12$, где $x_i \geq 0$. Но каждый контейнер аппаратно вмещает максимум 5 пакетов ($x_i \leq 5$).

Определим универсум $U$ как все решения без верхних ограничений. По формуле сочетаний с повторениями:

$$|U| = \binom{12 + 3 - 1}{3 - 1} = \binom{14}{2} = \frac{14 \times 13}{2} = 91$$

Определим нарушение свойства для каждого контейнера: $A_i$ — событие, при котором $x_i \geq 6$. Чтобы подсчитать мощность $|A_1|$, выделим контейнеру 1 шесть пакетов заранее (сдвиг переменной: $x_1' = x_1 - 6 \geq 0$). Уравнение принимает вид:

$$x_1' + x_2 + x_3 = 12 - 6 = 6$$

Число таких решений:

$$|A_1| = |A_2| = |A_3| = \binom{6 + 3 - 1}{2} = \binom{8}{2} = 28$$

Теперь рассмотрим пересечения. Может ли нарушиться сразу два ограничения ($x_1 \geq 6$ и $x_2 \geq 6$)? Сумма пакетов уже составит $6 + 6 = 12$. Для оставшегося остатка получаем уравнение:

$$x_1' + x_2' + x_3 = 12 - 12 = 0$$

Число решений:

$$|A_1 \cap A_2| = |A_1 \cap A_3| = |A_2 \cap A_3| = \binom{0 + 3 - 1}{2} = \binom{2}{2} = 1$$

Может ли нарушиться три ограничения ($x_1 \geq 6, x_2 \geq 6, x_3 \geq 6$)? Сумма потребовала бы минимум $6 \times 3 = 18$ пакетов, что больше доступных 12. Поэтому $|A_1 \cap A_2 \cap A_3| = 0$.

Применяем формулу дополнения для вычисления числа допустимых конфигураций:

$$N = |U| - \sum |A_i| + \sum |A_i \cap A_j| - |A_1 \cap A_2 \cap A_3|$$

$$N = 91 - (3 \times 28) + (3 \times 1) - 0 = 91 - 84 + 3 = 10$$

Всего существует 10 способов загрузить кластер без переполнения контейнеров. Без формулы включений-исключений программисту пришлось бы осуществлять полный перебор состояний вложенными циклами.

Формула включений-исключений превращает сложную систему пересекающихся условий в точный аналитический расчет. Однако с ростом числа условий $n$ количество слагаемых растет экспоненциально как $2^n$. Когда аналитический подсчет становится вычислительно слишком дорогим или когда требуется не просто узнать число вариантов, а последовательно перебрать и обработать каждый из них в коде, комбинаторика переходит от формул к алгоритмам генерации — теме следующей главы.