Комбинаторика с нуля: фундамент для теории вероятностей и Data Science

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

Представьте, что вы проектируете систему авторизации. Четырехзначный PIN-код из цифр от 0 до 9 взламывается простым перебором за пару секунд: в нем ровно 10 000 вариантов. Но если потребовать добавить хотя бы одну букву латинского алфавита, число комбинаций взлетит до сотен тысяч. Почему добавление одного символа меняет безопасность системы в десятки раз? И как дата-сайентисту быстро оценить, сколько конфигураций придется перебрать алгоритму GridSearchCV при подборе гиперпараметров модели машинного обучения?

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

---

Правило сложения: выбор по принципу «ИЛИ»

Начнем с базовой ситуации: перед нами несколько групп вариантов, и нам нужно выбрать ровно один вариант из всех возможных.

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

Математически для любого количества непересекающихся групп вариантов $k$:

$$N = n_1 + n_2 + \dots + n_k$$

Здесь:

• $N$ — общее число способов сделать единственный выбор;
• $n_1, n_2, \dots, n_k$ — количество вариантов выбора в каждой отдельной независимой категории.

Практический пример: Аналитик данных решает задачу классификации текстов. У него есть выбор: использовать одну из 3 моделей на основе решающих деревьев (Random Forest, Gradient Boosting, Extra Trees) или одну из 2 линейных моделей (логистическая регрессия, линейный SVM). Аналитик намерен запустить в качестве базового решения ровно одну модель. Сколькими способами он может выбрать алгоритм?

Поскольку модель выбирается только одна, варианты не пересекаются: $3 + 2 = 5$ способов.

Критическое условие: несовместность

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

Если варианты могут совпасть, простое сложение приведет к дублированию. Например, если среди 10 сотрудников 6 владеют Python, а 5 — SQL, мы не можем сложить $6 + 5 = 11$, если кто-то знает оба инструмента. Подсчет объектов с пересечениями регулируется принципом включений-исключений, который подробно разобран в главе 6. В рамках правила сложения мы всегда следим за тем, чтобы категории были взаимоисключающими.

---

Правило умножения: цепочка выбора по принципу «И»

Теперь усложним задачу: вместо выбора одного объекта из альтернатив нам нужно сконструировать составной объект, совершив серию последовательных шагов: выбрать первый элемент И второй элемент И третий элемент.

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

В общем виде для цепочки из $k$ последовательных шагов:

$$N = n_1 \times n_2 \times \dots \times n_k$$

Здесь:

• $N$ — общее число итоговых комбинаций;
• $n_1$ — количество вариантов на первом шаге;
• $n_2$ — количество вариантов на втором шаге (при любом исходе первого шага);
• $n_k$ — количество вариантов на $k$-м шаге.

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

1. Функцию активации на скрытых слоях: ReLU, GELU или Swish (3 варианта).
2. Оптимизатор: AdamW или SGD (2 варианта).
3. Размер батча: 32, 64, 128 или 256 (4 варианта).

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

$$N = 3 \times 2 \times 4 = 24$$

Получаем 24 уникальные конфигурации.

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

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

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

Как видно на схеме, если на первом уровне образуется 3 ветки, и из каждой выходит по 2 новые ветки, общее количество листьев на конце дерева равно $3 \times 2 = 6$. Умножение — это компактная запись разветвления дерева.

Инвариантность количества, а не состава

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

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

Пример: В отделе из 5 аналитиков нужно назначить тимлида и код-ревьюера. Тимлидом может стать любой из 5 человек. После того как тимлид назначен, код-ревьюером можно назначить любого из оставшихся сотрудников. Сам состав кандидатов на втором шаге меняется (выбранный тимлид уже не доступен), но их количество всегда строго равно $5 - 1 = 4$. Значит, правило умножения законно:

$$N = 5 \times 4 = 20 \text{ способов}$$

---

Сравнение правил: ИЛИ против И

Чтобы не путать эти правила на практике, сведем их ключевые отличия в таблицу:

Критерий	Правило сложения	Правило умножения
Логическая связка	«ИЛИ» (выбор альтернативы)	«И» (последовательный выбор)
Характер действия	Выбирается один элемент из множества групп	Формируется кортеж/набор из элементов разных групп
Графическая модель	Объединение параллельных путей	Последовательное ветвление (дерево исходов)
Ключевое требование	Несовместность вариантов (нет общих исходов)	Независимость числа вариантов на каждом шаге
Формула	$N = n_1 + n_2 + \dots + n_k$	$N = n_1 \times n_2 \times \dots \times n_k$

---

Комбинирование правил в реальных задачах

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

Кейс: генерация идентификаторов для Data Pipeline

Инженер данных проектирует схему генерации временных токенов сессий для API. Токен формируется по следующему регламенту:

• Токен состоит из двух частей: буквенного префикса и числового суффикса.
• Префикс указывает на тип среды: либо односимвольный для тестов ('T'), либо двухсимвольный для продакшена (две заглавные буквы латинского алфавита от 'A' до 'Z', всего 26 букв).
• Суффикс — это последовательность из трех цифр (от 0 до 9), причем первая цифра суффикса не может быть нулем (доступны цифры от 1 до 9).

Сколько всего уникальных токенов можно сгенерировать по такой спецификации?

Разобьем решение на логические уровни:

1. Шаг 1. Анализ префикса (правило сложения + правило умножения): Префикс бывает либо тестовым, либо продакшен:

   • Тестовый префикс: ровно 1 вариант ('T').
   • Продакшен-префикс: первая буква (26 вариантов) И вторая буква (26 вариантов). По правилу умножения: $26 \times 26 = 676$ вариантов.
   • Поскольку среда может быть либо тестовой, либо продакшен (несовместные события), применяем правило сложения:

   $$N_{\text{prefix}} = 1 + 676 = 677 \text{ вариантов префикса}$$

2. Шаг 2. Анализ числового суффикса (правило умножения): Суффикс состоит из трех цифр:

   • Первая цифра (от 1 до 9): 9 вариантов.
   • Вторая цифра (от 0 до 9): 10 вариантов.
   • Третья цифра (от 0 до 9): 10 вариантов.

   По правилу умножения для трех позиций:

   $$N_{\text{suffix}} = 9 \times 10 \times 10 = 900 \text{ вариантов суффикса}$$

3. Шаг 3. Итоговая сборка токена: Токен состоит из префикса И суффикса. Связка «И» означает финальное применение правила умножения:

   $$N_{\text{total}} = N_{\text{prefix}} \times N_{\text{suffix}} = 677 \times 900 = 609\,300$$

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

---

Связь с теорией вероятностей и Data Science

Зачем эти формулы специалисту по анализу данных?

В классической теории вероятностей вероятность любого случайного события $A$ вычисляется по формуле:

$$P(A) = \frac{m}{N}$$

Где:

• $P(A)$ — вероятность наступления события $A$;
• $m$ — число благоприятных исходов;
• $N$ — общее число всех возможных элементарных исходов в пространстве событий.

Например, вероятность того, что сгенерированный в нашем примере токен случайно окажется тестовым, равна отношению числа тестовых токенов ($1 \times 900 = 900$) ко всем возможным токенам ($609\,300$):

$$P(\text{Test}) = \frac{900}{609\,300} \approx 0{,}00147 \text{ (около } 0{,}15\%)$$

Без умения строго подсчитать $N$ и $m$ с помощью правил суммы и произведения невозможно найти ни одну вероятность в дискретном пространстве.

Кроме того, правило умножения лежит в основе проблемы комбинаторного взрыва при подборе гиперпараметров (Grid Search). Если у вас есть 6 параметров, и для каждого вы проверяете всего по 5 значений, алгоритм должен обучить и протестировать модель:

$$5 \times 5 \times 5 \times 5 \times 5 \times 5 = 5^6 = 15\,625 \text{ раз}$$

Если одно обучение занимает хотя бы 10 секунд, полный перебор продлится более 43 часов. Понимание правил комбинаторики позволяет вовремя заметить взрывной рост вычислений и перейти к более эффективным методам — например, случайному поиску (Random Search) или байесовской оптимизации.

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

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

Если вы тщательно перетасуете стандартную колоду из 52 карт, то с вероятностью, практически неотличимой от единицы, полученная последовательность карт никогда раньше не возникала за всю историю человечества. Более того, она вряд ли повторится до тех пор, пока существует Вселенная. Число возможных порядков колоды равно $52!$ — это число из 68 знаков ($8{,}0658 \times 10^{67}$), которое лишь ненамного уступает оценочному количеству атомов во всей видимой части космоса.

Каким образом простая операция выстраивания объектов в цепочку порождает столь невообразимые пространства вариантов? Ответ вытекает непосредственно из логики последовательного выбора.

От цепочки независимых выборов к перестановкам

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

Представьте конвейер подготовки признаков (Data Preprocessing Pipeline), состоящий из $n$ изолированных шагов: например, стандартизация значений, заполнение пропусков, кодирование категорий и удаление выбросов. Мы хотим применить все $n$ шагов, но порядок их выполнения пока произволен. Сколькими способами можно организовать этот конвейер?

Разобьем процесс на $n$ последовательных позиций («слотов»):

1. Первый слот конвейера: у нас есть выбор из всех $n$ имеющихся операций.
2. Второй слот: одна операция уже задействована на первом шаге. Независимо от того, какая именно это была операция, неиспользованными остаются ровно $n - 1$ вариантов.
3. Третий слот: две операции уже заняты, на выбор остается $n - 2$ шага.
4. Последний ($n$-й) слот: все операции, кроме одной, уже распределены. Для финальной позиции остается единственный кандидат (1 вариант).

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

$$P_n = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

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

• $P_n$ — число перестановок множества из $n$ элементов (от латинского permutatio — перемещение, перестановка).
• $n$ — количество кандидатов на первую позицию.
• $(n - 1), (n - 2), \dots, 1$ — остаток кандидатов на каждом последующем шаге, уменьшающийся строго на единицу.

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

Для конвейера из 4 шагов число альтернативных порядков равно $P_4 = 4 \times 3 \times 2 \times 1 = 24$. Если конвейер расширится всего до 7 этапов, число маршрутов возрастет до $P_7 = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$.

Анатомия факториала и парадокс пустого множества

Произведение всех натуральных чисел от 1 до $n$ обозначается символом $n!$ (читается «эн факториал»). Это компактная запись длины пространства всех возможных упорядочиваний:

$$n! = \prod_{k=1}^{n} k = 1 \times 2 \times \dots \times n$$

Где $\prod$ — математический оператор произведения элементов от $k = 1$ до $k = n$.

Факториал обладает фундаментальным рекуррентным свойством: значение для следующего числа получается простым умножением предыдущего факториала на размер нового шага:

$$n! = n \times (n - 1)!$$

Например, зная, что $4! = 24$, мы мгновенно находим $5! = 5 \times 4! = 5 \times 24 = 120$.

Однако эта рекуррентная связь ставит вопрос: чему равен $0!$? С интуитивной точки зрения «произведение чисел от 1 до 0» звучит бессмысленно, а ответ «ноль» кажется очевидным. Но в математике и анализе данных $0! = 1$. К этому выводу ведут сразу три независимых обоснования:

• Алгебраическое. Развернем рекуррентную формулу в обратную сторону: $(n - 1)! = \frac{n!}{n}$. Если мы хотим, чтобы соотношение работало для $n = 1$, подставим единицу: $0! = \frac{1!}{1} = \frac{1}{1} = 1$. Если бы $0!$ равнялся нулю, деление на него разрушило бы формулы высшей комбинаторики и распределений вероятностей (например, распределение Пуассона).
• Комбинаторное. Сколькими способами можно упорядочить множество из 0 элементов (пустое множество $\emptyset$)? Ровно одним: «ничего не брать и оставить список пустым». Пустое действие — это тоже один конкретный исход.
• Концепция нейтрального элемента. При сложении нуля слагаемых результатом признается 0 (нейтральный элемент относительно сложения). При умножении нуля сомножителей (пустое произведение) результатом признается 1 — нейтральный элемент относительно умножения.

Масштаб роста: почему факториал останавливает суперкомпьютеры

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

Взглянем на скорость, с которой истощаются вычислительные мощности при попытке решить такую задачу полным перебором перестановок ($O(n!)$):

Число объектов ($n$)	Значение $n!$	Время перебора при $10^9$ операций/сек
$5$	$120$	$0{,}00000012$ секунды
$10$	$3\,628\,800$	$0{,}0036$ секунды
$15$	$1{,}31 \times 10^{12}$	$\approx 22$ минуты
$20$	$2{,}43 \times 10^{18}$	$\approx 77$ лет
$25$	$1{,}55 \times 10^{25}$	$\approx 492$ миллиона лет

Увеличение числа параметров всего на 5 позиций (с 15 до 20) превращает задачу, решаемую за чашку кофе, в процесс, превосходящий среднюю продолжительность человеческой жизни. Именно поэтому алгоритмы полного перебора перестановок в Data Science не применяются для задач размерности $n > 12$.

Когда $n$ велико, прямое вычисление $n!$ вызывает переполнение памяти (integer overflow). Для аналитической работы, вычисления логарифмических функций правдоподобия и энтропии используют формулу приближения Стирлинга:

$$n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$$

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

• $\pi \approx 3{,}14159$ и $e \approx 2{,}71828$ — фундаментальные математические константы.
• Множитель $\left(\frac{n}{e}\right)^n$ показывает доминирующую часть роста: факториал растет быстрее, чем любая фиксированная экспонента $a^n$, поскольку основание дроби растет вместе с $n$.
• Практический пример: для $n = 10$ точное значение $10! = 3\,628\,800$. По формуле Стирлинга: $\sqrt{20\pi} \times (10/e)^{10} \approx 7{,}9266 \times 453\,999{,}3 \approx 3\,598\,696$. Относительная погрешность составляет менее 1%, и она стремится к нулю с ростом $n$.

В прикладном анализе данных чаще всего работают с логарифмом факториала, заменяя произведение суммой: $\ln(n!) \approx n \ln n - n$. Это позволяет алгоритмам оценивать вероятностные пространства терабайтных выборок без риска переполнения разрядной сетки процессора.

Перестановки на практике: Permutation Importance и статистические тесты

Знание структуры перестановок необходимо не только для оценки сложности алгоритмов, но и для статистических инструментов в Data Science. Рассмотрим два прямых применения.

1. Перестановочная важность признаков (Permutation Feature Importance)

Обучив сложную модель (например, градиентный бустинг), мы хотим знать: насколько признак $X_j$ важен для итогового прогноза?

Вместо сложного переобучения модели дата-сайентисты применяют следующий алгоритм:

1. Фиксируют тестовую выборку и замеряют исходную метрику качества модели (например, ROC-AUC или $R^2$).
2. Берут столбец признака $X_j$ и случайно переставляют в нем значения между объектами (перемешивают строки местами).
3. Прогоняют модель на выборке с перемешанным столбцом и фиксируют падение качества.

В чем комбинаторный смысл этой процедуры? Перестановка разрушает взаимосвязь признака $X_j$ с целевой переменной, но сохраняет одномерное эмпирическое распределение самого признака (среднее, дисперсия и квантили остаются абсолютно прежними, ведь набор чисел не изменился, изменился лишь их порядок). Если признак был критически важен, качество прогноза рушится. Множество всех допустимых перемешиваний для выборки размера $N$ — это в точности пространство перестановок $P_N = N!$.

2. Точный перестановочный тест (Permutation Test)

Представьте, что при A/B-тестировании нового интерфейса группы оказались маленькими: 4 пользователя в группе A и 4 пользователя в группе B. Мы хотим проверить гипотезу о том, различается ли среднее время сессии между группами, не полагаясь на предположения о нормальности данных (t-тест Стьюдента здесь не надежен).

Нулевая гипотеза ($H_0$) утверждает: разделение на группы не влияет на метрику, эффект равен нулю, а все 8 наблюдений принадлежат одной генеральной совокупности.

Если гипотеза $H_0$ верна, то метки «A» и «B» можно произвольным образом перетасовать между 8 измерениями. Любая перестановка объединенного массива из 8 значений дает один из равновероятных сценариев распределения данных при отсутствии эффекта.

Сравнивая наблюдаемую разницу средних со значениями, полученными на всех возможных перестановках, аналитик вычисляет точное значение p-value как долю перестановок, давших столь же сильное или более экстремальное расхождение:

$$p = \frac{m}{N!}$$

где $N!$ — общее количество способов упорядочить наблюдения (в нашем случае $8! = 40\,320$), а $m$ — число порядков, приводящих к экстремальной разнице средних. Это прямой мост между комбинаторикой перестановок и проверкой статистических гипотез.

Мы изучили ситуацию, когда упорядочиваются все $n$ имеющихся объектов. Однако в большинстве практических задач машинного обучения нам не требуется выстраивать абсолютно все элементы. Например, из 100 доступных признаков для компактной модели нужно отобрать только 5 наиболее информативных и расставить их по позициям приоритета. В этом случае слотов оказывается меньше, чем претендентов. К подсчету таких упорядоченных подмножеств мы перейдем в следующей главе.

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

Представьте, что рекомендательная система музыкального сервиса формирует персональный плейлист дня: на витрине пользователя отображаются ровно 3 трека на позициях № 1, № 2 и № 3. Алгоритм отобрал 50 наиболее подходящих композиций-кандидатов. Если бы сервис просто перемешивал все 50 треков между собой, мы получили бы $50! \approx 3{,}04 \times 10^{64}$ вариантов — число, превосходящее количество песчинок на Земле. Однако экрану не нужны все 50 треков: требуется заполнить всего 3 позиции, причем порядок строго важен, ведь трек на первой строчке слушают вчетверо чаще, чем на третьей.

Сколько существует способов расставить 3 трека из 50 доступных? Эта прикладная задача подводит нас к фундаментальной операции комбинаторики — частичной перестановке, или размещению.

---

От полного порядка к выборочному: логика слотов

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

• Рекомендательная лента показывает пользователю Top-$k$ товаров из каталога в $n$ позиций.
• Алгоритм пошагового отбора признаков (Forward Feature Selection) выбирает $k$ наиболее информативных предикторов из базы в $n$ колонок.
• На пьедестале соревнований по анализу данных Kaggle есть только 3 призовых места (золото, серебро, бронза), на которые претендуют $n$ команд.

Поставим строгую комбинаторную задачу: сколькими способами можно выбрать $k$ различных элементов из генеральной совокупности объемом $n$ и расставить их по $k$ пронумерованным позициям ($k \leq n$)?

Используем базовое правило умножения и метод последовательного заполнения позиций. Создадим $k$ упорядоченных ячеек:

1. Первая позиция (слот 1): мы можем поместить любой из $n$ доступных объектов. Вариантов выбора: $n$.
2. Вторая позиция (слот 2): один объект уже зафиксирован на первом месте. Повторно использовать его нельзя, поэтому доступно $n - 1$ кандидатов.
3. Третья позиция (слот 3): заняты уже две позиции, остается выбор из $n - 2$ объектов.
4. Позиция с номером $k$ (слот $k$): перед заполнением последнего слота мы уже отобрали и распределили $k - 1$ объектов. Следовательно, из исходных $n$ элементов свободными остаются:

$$n - (k - 1) = n - k + 1$$

По правилу умножения общее число упорядоченных последовательностей длины $k$ из $n$ различных элементов равно произведению вариантов на каждом шаге:

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

Такую конструкцию в математике называют размещением без повторений из $n$ элементов по $k$ и обозначают символом $A_n^k$ (от французского arrangement — «размещение», «расположение») либо $P(n, k)$ в англоязычной традиции.

Вернемся к нашему музыкальному сервису, где $n = 50$, а $k = 3$:

• На 1-е место претендуют 50 треков.
• На 2-е место претендуют 49 треков.
• На 3-е место претендуют 48 треков.

$$A_{50}^3 = 50 \times 49 \times 48 = 117\,600$$

Всего 117 600 уникальных вариантов формирования первой тройки. Никакого колоссального масштаба $50!$ здесь нет: процедура остановлена ровно после третьего шага.

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

---

Факториальная форма: искусство отсекать лишнее

Запись в виде длинной цепочки сомножителей $n \times (n - 1) \times \dots \times (n - k + 1)$ неудобна для алгебраических преобразований, доказательств теорем и компактных расчетов в теории вероятностей. Эту цепочку можно свернуть через факториалы.

Вспомним, что полный факториал $n!$ содержит произведение всех натуральных чисел от $n$ вниз до 1:

$$n! = \underbrace{n \times (n - 1) \times \dots \times (n - k + 1)}_{\text{нужные нам } k \text{ сомножителей}} \times \underbrace{(n - k) \times (n - k - 1) \times \dots \times 2 \times 1}_{\text{лишний "хвост" длиной } n - k}$$

Заметьте: ненужный «хвост» произведения представляет собой не что иное, как факториал оставшихся, не вошедших в выборку объектов, то есть $(n - k)!$.

Если мы разделим полное произведение $n!$ на факториал неиспользованного остатка $(n - k)!$, то весь «хвост» взаимно сократится:

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

Поясним каждый элемент формулы:

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

Практический расчет формулы

Рассчитаем число способов распределить золотую, серебряную и бронзовую медали среди 8 финалистов хакатона ($n = 8$, $k = 3$):

$$A_8^3 = \frac{8!}{(8 - 3)!} = \frac{8!}{5!} = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = 8 \times 7 \times 6 = 336$$

При ручных вычислениях и при проектировании быстрых алгоритмов никогда не вычисляют факториалы больших чисел «в лоб». Вычисление $8! = 40\,320$ с последующим делением на $5! = 120$ нерационально: на больших объемах данных это гарантированно приведет к арифметическому переполнению разрядной сетки (integer overflow). Вместо этого сокращение выполняют аналитически еще до вычислений, сводя расчет к перемножению $k$ чисел.

---

Граничные случаи и связь с перестановками

Формула $A_n^k = \frac{n!}{(n - k)!}$ математически согласована со всеми ранее изученными свойствами перестановок. Проверим граничные значения параметра $k$:

1. Выборка всех доступных элементов ($k = n$)

Что происходит, если количество слотов равно количеству объектов? Мы должны расставить все $n$ элементов по всем $n$ местам:

$$A_n^n = \frac{n!}{(n - n)!} = \frac{n!}{0!} = \frac{n!}{1} = n! = P_n$$

Полная перестановка без повторений $P_n$ — это частный случай размещения, когда длина выборки $k$ совпадает с объемом совокупности $n$. Здесь наглядно подтверждается строгое математическое равенство $0! = 1$: без него формула размещений перестала бы работать в критической точке $k = n$.

2. Выбор одного элемента ($k = 1$)

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

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

3. Пустая выборка ($k = 0$)

Сколькими способами можно выбрать 0 объектов из множества мощности $n$? Ровно одним — не выбирать ничего (пустое множество упорядочено тривиальным образом):

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

Сводная таблица демонстрирует, как меняется поведение $A_n^k$ в зависимости от $k$:

Значение $k$	Алгебраическое выражение	Комбинаторный смысл	Пример ($n = 5$)
$k = 0$	$\frac{n!}{n!} = 1$	Выбор пустого набора (ровно 1 способ)	$A_5^0 = 1$
$k = 1$	$\frac{n!}{(n-1)!} = n$	Выбор единственного лидера	$A_5^1 = 5$
$k < n$	$n \times (n-1) \times \dots \times (n-k+1)$	Частичная перестановка (Top-$k$ элементов)	$A_5^2 = 20$
$k = n$	$\frac{n!}{0!} = n!$	Полная перестановка всех элементов	$A_5^5 = 120$

---

Размещения в анализе данных и вероятностных моделях

Понимание размещений критически важно в Data Science при решении двух классов задач: вычислении мощностей выборочных пространств в классической вероятности и проектировании алгоритмов ранжирования.

Модель без возвращения и коллизии хеш-функций

Классическая вероятность события $A$ вычисляется как отношение благоприятных исходов к общему числу исходов: $P(A) = \frac{m}{N}$. Если мы проводим серию из $k$ испытаний без возвращения из совокупности объема $n$, то общее число упорядоченных траекторий описывается числом размещений.

Классическая иллюстрация этой схемы — парадокс дней рождения.

Представим группу из $k$ человек (например, $k = 23$). Какова вероятность того, что ни у кого из них не совпадет день рождения (предполагаем $n = 365$ равновероятных дней в году)?

1. Общее количество всевозможных распределений дат рождения для $k$ человек (если дни рождения могут повторяться):

$$N = 365 \times 365 \times \dots \times 365 = 365^k$$

(каждый следующий шаг не зависит от предыдущего).

2. Благоприятные исходы $m$, когда у всех $k$ человек дни рождения приходятся на разные дни. Первый человек может родиться в любой из 365 дней, второй — в любой из оставшихся 364, третий — в любой из 363 и так далее. Это в точности число размещений без повторений $A_{365}^k$:

$$m = A_{365}^k = 365 \times 364 \times \dots \times (365 - k + 1)$$

Вероятность отсутствия совпадений:

$$P(\text{все дни разные}) = \frac{A_{365}^k}{365^k} = \frac{365 \times 364 \times \dots \times (365 - k + 1)}{365^k}$$

При $k = 23$:

$$P(\text{все дни разные}) \approx 0{,}4927$$

Следовательно, вероятность обратного события — того, что хотя бы у двух человек из 23 совпадет день рождения:

$$1 - 0{,}4927 = 0{,}5073 \quad (\approx 50{,}7\%)$$

Этот же математический аппарат лежит в основе оценки коллизий хеш-функций в распределенных хранилищах данных (Hash Ring, базы данных NoSQL): если $k$ независимых ключей случайным образом отображаются в пространство хешей размера $n$, то отсутствие коллизий требует упорядоченного размещения $k$ уникальных хешей из $n$ доступных слотов.

Ранжирование и метрики Top-$k$

В задачах информационного поиска (Information Retrieval) и поисковых системах алгоритмы машинного обучения оптимизируют выдачу не по бинарному принципу «нашел / не нашел», а с учетом порядка. Выдача $k$ релевантных документов из найденных $n$ кандидатов — это упорядоченный кортеж.

Если поисковый робот нашел по запросу 10 релевантных статей ($n = 10$) и выводит на первую страницу выдачи ровно 4 ссылки ($k = 4$), то число всевозможных вариантов выдачи составляет:

$$A_{10}^4 = 10 \times 9 \times 8 \times 7 = 5\,040$$

Если алгоритм идеального ранжирования предполагает строго одну правильную последовательность документов по степени убывания пользы (от наиболее авторитетного к менее авторитетному), то вероятность того, что случайная модель угадает эту эталонную выдачу Top-4, равна:

$$P(\text{идеальный Top-4}) = \frac{1}{A_{10}^4} = \frac{1}{5\,040} \approx 0{,}000198 \quad (0{,}02\%)$$

Именно поэтому в задачах ранжирования используются специализированные метрики (например, MRR — Mean Reciprocal Rank, NDCG — Normalized Discounted Cumulative Gain), которые штрафуют алгоритм за ошибки в первых слотах размещения гораздо строже, чем за ошибки на последних позициях.

---

Архитектура перебора признаков: Greedy Forward Selection

Рассмотрим, как комбинаторика размещений объясняет выбор субоптимальных эвристик в машинном обучении.

В задаче регрессии у нас есть $n = 30$ сырых признаков. Мы хотим отобрать модель, содержащую ровно $k = 5$ признаков, упорядоченных по степени их добавления в конвейер. Если порядок добавления признаков имеет значение (например, каждый следующий шаг оценивает остаточную ошибку предыдущей комбинации):

$$A_{30}^5 = 30 \times 29 \times 28 \times 27 \times 26 = 17\,100\,720$$

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

Чтобы избежать комбинаторного тупика, алгоритм жадного прямого включения (Greedy Forward Selection) заменяет глобальное размещение серией локальных шагов:

1. На первом шаге обучаются $n$ моделей (по 1 признаку) и выбирается наилучший.
2. На втором шаге признак-победитель фиксируется в первом слоте, а среди оставшихся $n - 1$ признаков ищется второй.
3. Процедура повторяется $k$ раз.

Вместо произведения $A_{30}^5 \approx 1{,}71 \times 10^7$ алгоритм выполняет сумму операций:

$$30 + 29 + 28 + 27 + 26 = 140 \text{ обучений моделей}$$

Анализ формулы размещений позволяет инженеру данных четко понимать: где перебор в пространстве $A_n^k$ физически допустим, а где факториальный рост требует перехода к жадным или вероятностным эвристикам.

---

Главный вопрос порядка

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

• в музыкальном плейлисте важен трек-хедлайнер на первом месте;
• на пьедестале почета золото качественно отличается от бронзы;
• в хеш-таблице последовательность ключей определяет адресацию ячеек.

Во всех этих случаях перестановка элементов внутри уже выбранного подмножества порождает новый исход: набор (Трек A, Трек B) не эквивалентен набору (Трек B, Трек A).

Но что произойдет, если порядок элементов перестанет иметь значение?

Представьте, что из тех же 50 треков нам нужно собрать архивный zip-файл из 3 песен для фонового скачивания, или из 30 признаков в датасете отобрать 5 для одновременного обучения линейной модели $y = w_1 x_1 + \dots + w_5 x_5$, где слагаемые коммутативны. Сколько вариантов останется, если перестановки внутри группы перестанут считаться уникальными комбинациями? Ответ на этот вопрос дает следующая операция комбинаторики — сочетания.

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

Если алгоритм обучает модель на трёх признаках, ему совершенно безразлично, в каком порядке они подаются на вход: матрица с колонками [возраст, доход, стаж] несёт ровно ту же информацию, что и [доход, стаж, возраст]. Для каталога из 10 доступных признаков число упорядоченных троек составляет $A_{10}^3 = 10 \times 9 \times 8 = 720$. Однако обучать 720 моделей бессмысленно — подавляющее большинство из них обучится на одном и том же наборе данных.

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

От порядка к составу: рождение сочетаний

Каждый раз, когда порядок элементов перестаёт играть роль, пространство исходов резко сжимается. Возьмём конкретную тройку признаков: $\{A, B, C\}$. В рамках размещений эта тройка порождает несколько разных кортежей:

• $(A, B, C)$
• $(A, C, B)$
• $(B, A, C)$
• $(B, C, A)$
• $(C, A, B)$
• $(C, B, A)$

Все эти 6 цепочек представляют собой перестановки одних и тех же трёх элементов. Их количество в точности равно $3! = 3 \times 2 \times 1 = 6$. С точки зрения состава подмножества все 6 вариантов неразличимы: это одна и та же группа $\{A, B, C\}$.

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

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

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

Разберём каждый компонент этой формулы на практике:

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

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

Вернёмся к выбору 3 признаков из 10:

$$C_{10}^3 = \frac{10!}{3! \times (10 - 3)!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$$

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

Тип выборки	Влияет ли порядок?	Формула	Число выборок 3 из 10
Размещение ($A_n^k$)	Да (ранжирование, очередь)	$\frac{n!}{(n - k)!}$	720
Сочетание ($C_n^k$)	Нет (команда, подмножество)	$\frac{n!}{k!(n - k)!}$	120

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

Формула $C_n^k$ обладает выраженной симметрией. Если в выражении $\frac{n!}{k!(n - k)!}$ заменить $k$ на $n - k$, знаменатель не изменится: множители просто поменяются местами.

Свойство симметрии:

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

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

• Разбить датасет из 100 строк на обучающую выборку (80 строк) и тестовую (20 строк) можно $\binom{100}{80}$ способами.
• Выбрать 20 тестовых строк из 100 можно $\binom{100}{20}$ способами.
• Значения $\binom{100}{80}$ и $\binom{100}{20}$ строго равны. Вычисление через меньший индекс экономит арифметические действия: $\frac{100 \times 99 \times \dots \times 81}{20!}$ считать дольше, чем сразу разложить формулу относительно 20 множителей.

Проверим граничные значения формулы:

• $\binom{n}{0} = \frac{n!}{0! \times n!} = 1$: существует ровно один способ не выбрать ни одного объекта (пустое множество).
• $\binom{n}{n} = \frac{n!}{n! \times 0!} = 1$: существует единственный способ забрать все элементы разом.
• $\binom{n}{1} = \frac{n!}{1! \times (n - 1)!} = n$: выбрать один объект из $n$ кандидатов можно ровно $n$ способами.

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

Представим команду из $n$ аналитиков, в которой работает ведущий эксперт Анна. Нам нужно сформировать рабочую группу из $k$ человек. Разобьём все возможные группы на две взаимоисключающие категории по правилу сложения:

1. Группы, куда Анна вошла. Анна уже заняла одно место. Осталось добрать $k - 1$ человек из оставшихся $n - 1$ коллег. Это даёт $\binom{n - 1}{k - 1}$ вариантов.
2. Группы, куда Анна не вошла. Анна исключена из рассмотрения. Все $k$ мест заполняются оставшимися $n - 1$ кандидатами. Это даёт $\binom{n - 1}{k}$ вариантов.

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

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

Например, для выбора 3 человек из 5:

$$\binom{5}{3} = \binom{4}{2} + \binom{4}{3} = 6 + 4 = 10$$

Это тождество порождает треугольник Паскаля — числовую таблицу, где каждое число равно сумме двух стоящих над ним чисел. Строки нумеруются с $n = 0$, позиции в строке — с $k = 0$:

• Строка 0 ($n = 0$): $1$
• Строка 1 ($n = 1$): $1 \quad 1$
• Строка 2 ($n = 2$): $1 \quad 2 \quad 1$
• Строка 3 ($n = 3$): $1 \quad 3 \quad 3 \quad 1$
• Строка 4 ($n = 4$): $1 \quad 4 \quad 6 \quad 4 \quad 1$
• Строка 5 ($n = 5$): $1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1$

В строке под номером $n$ значения растут от краёв к центру, достигая пика при $k = n / 2$ (для чётных $n$) или на двух центральных значениях при $k = (n - 1)/2$ и $k = (n + 1)/2$ (для нечётных $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$ скобок, а из оставшихся $n - k$ скобок автоматически взять $a$. Сколькими способами можно указать те $k$ скобок, откуда будет извлечена переменная $b$? Ровно $\binom{n}{k}$ способами.

Отсюда вытекает теорема о биноме Ньютона:

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

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

• $\sum_{k = 0}^n$ — знак суммы по всем возможным размерам выборки $k$ от 0 до $n$.
• $\binom{n}{k}$ — биномиальный коэффициент, отражающий кратность одночлена.
• $a^{n - k} b^k$ — мономы степени $n$.

Например, при $n = 3$:

$$(a + b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2 b + \binom{3}{2}a b^2 + \binom{3}{3}b^3 = a^3 + 3a^2 b + 3a b^2 + b^3$$

Если подставить в формулу бинома $a = 1$ и $b = 1$, получается фундаментальное соотношение:

$$(1 + 1)^n = \sum_{k = 0}^n \binom{n}{k} 1^{n - k} 1^k \implies \sum_{k = 0}^n \binom{n}{k} = 2^n$$

Это равенство имеет прямое комбинаторное толкование: сумма биномиальных коэффициентов по всем $k$ равна общему числу всех возможных подмножеств множества из $n$ элементов (булеану). Для каждого из $n$ объектов у нас есть 2 исхода — либо включить его в подмножество, либо нет. По правилу умножения получаем $2 \times 2 \times \dots \times 2 = 2^n$.

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

В машинном обучении и A/B-тестировании сочетания выступают математическим каркасом вероятностных моделей.

Перебор признаков (Feature Selection)

Если датасет содержит $n = 20$ признаков, полный перебор всех возможных непустых комбинаций признаков потребует обучения:

$$\sum_{k = 1}^{20} \binom{20}{k} = 2^{20} - 1 = 1\,048\,575 \text{ моделей}$$

Число $2^n$ растёт экспоненциально, что делает исчерпывающий перебор невозможным уже при $n \geq 40$, вынуждая инженеров применять жадные эвристики и регуляризацию.

A/B-тесты и распределение Бернулли

В A/B-тестировании конверсия пользователя — это бинарный исход: клик (успех с вероятностью $p$) или отказ (неудача с вероятностью $1 - p$).

Если посадочную страницу посетили $n$ пользователей, какова вероятность зафиксировать ровно $k$ конверсий?

Любая конкретная последовательность из $k$ успехов и $n - k$ неудач (например, сначала все $k$ кликнули, затем $n - k$ ушли) имеет вероятность $p^k (1 - p)^{n - k}$. Но эти $k$ успехов могут распределиться среди $n$ посещений в любом порядке: кликнуть могут первые $k$ человек, последние $k$, или они распределятся равномерно по всей выборке.

Число способов расставить $k$ событий успеха по $n$ независимым испытаниям — это в точности число сочетаний $\binom{n}{k}$.

Так рождается формула биномиального распределения:

$$P(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}$$

Здесь биномиальный коэффициент служит весовым множителем: он показывает, сколько элементарных путей ведёт к суммарному итогу в $k$ успехов. Без понимания природы сочетаний невозможно корректно рассчитывать доверительные интервалы, проводить z-тесты пропорций и оценивать статистическую значимость экспериментов в аналитике данных.

Выборки и перестановки с повторениями

До сих пор каждый выбор подчинялся строгому ограничению: взятый элемент выбывал из игры, а все объекты множества считались различимыми. Мы считали перестановки уникальных этапов конвейера, формировали рейтинги Top-$k$ из разных кандидатов и собирали признаковые подмножества в булеане. Но реальные данные редко состоят из неповторимых сущностей.

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

---

Размещения с повторениями: независимый выбор с возвратом

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

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

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

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

• $n$ — мощность исходного алфавита (число уникальных типов объектов, доступных для выбора);
• $k$ — длина формируемой последовательности (число шагов или слотов);
• $\bar{A}_n^k$ — число всех возможных упорядоченных последовательностей длины $k$ с повторениями.

С практической точки зрения ключевое отличие от размещений без повторений ($A_n^k$) заключается в том, что длина выборки $k$ больше не ограничена размером алфавита $n$. Мы легко можем составить вектор длины $k = 100$ из алфавита $n = 2$ символов.

Пример из практики. Допустим, мы генерируем категориальный хеш-вектор длины $k = 4$ из шестнадцатеричных символов (алфавит от 0 до F, то есть $n = 16$). Число уникальных идентификаторов равно:

$$16^4 = 65\,536$$

Если бы символы не возвращались, число исходов составило бы лишь $A_{16}^4 = 16 \times 15 \times 14 \times 13 = 43\,680$. Разрешение повторений существенно расширяет емкость пространства адресов при фиксированной длине вектора.

---

Перестановки с повторениями и мультиномиальный коэффициент

Совершенно иная комбинаторная задача возникает, когда набор элементов задан целиком, но среди них есть одинаковые, неразличимые между собой объекты. Такую структуру называют мультимножеством.

Рассмотрим слово «ДАТА». В нем 4 буквы, однако буква «А» встречается 2 раза, а «Д» и «Т» — по 1 разу. Если бы все буквы были помечены уникальными индексами ($\text{Д}_1, \text{А}_1, \text{Т}_1, \text{А}_2$), мы получили бы стандартные $4! = 24$ перестановки. Однако физическая замена $\text{А}_1$ и $\text{А}_2$ местами в слове «ДАТА» не создает новой строки: «Д $\text{А}_1$ Т $\text{А}_2$» и «Д $\text{А}_2$ Т $\text{А}_1$» неразличимы для парсера.

Чтобы устранить этот избыточный учет, применим уже знакомый принцип факторизации: разделим общее число перестановок $n!$ на количество внутренних перестановок внутри групп одинаковых элементов. Для слова «ДАТА» получаем:

$$\frac{4!}{1! \times 2! \times 1!} = \frac{24}{2} = 12 \text{ уникальных анаграмм.}$$

Обобщим эту логику на произвольное число групп. Пусть имеется совокупность из $n$ объектов, разделенных на $m$ классов: $k_1$ объектов первого типа, $k_2$ объектов второго типа, $\dots$, $k_m$ объектов $m$-го типа, причем их сумма строго равна объему выборки:

$$k_1 + k_2 + \dots + k_m = n$$

Число уникальных перестановок такого мультимножества задается формулой:

$$P_{n}(k_1, k_2, \dots, k_m) = \frac{n!}{k_1! \times k_2! \times \dots \times k_m!}$$

Где:

• $n$ — общее число позиций в результирующей последовательности;
• $k_i$ — кратность (число вхождений) элементов $i$-го типа;
• $k_i!$ в знаменателе — поправка на неразличимость перестановок одинаковых элементов внутри своей группы.

Эта величина называется мультиномиальным коэффициентом и обозначается как $\binom{n}{k_1, k_2, \dots, k_m}$.

Обратите внимание на связь с предыдущим материалом: биномиальный коэффициент $C_n^k$ — это частный случай мультиномиального при $m = 2$ классах (например, $k$ успехов и $n - k$ неудач):

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

Если биномиальный коэффициент считает число способов расставить бинарные флаги (0 и 1) по $n$ позициям, то мультиномиальный решает задачу раскладки $n$ разнородных объектов по $m$ маркированным корзинам фиксированной вместимости ($k_1, k_2, \dots, k_m$).

Пример из практики. Представьте конвейер тестирования из $n = 9$ микросервисов. Мы распределяем их по трем стендам нагрузки: на стенд High-Load отправляются $k_1 = 4$ сервиса, на Standard — $k_2 = 3$, на Debug — оставшиеся $k_3 = 2$. Сколькими способами можно сформировать такую конфигурацию?

$$\binom{9}{4, 3, 2} = \frac{9!}{4! \times 3! \times 2!} = \frac{362\,880}{24 \times 6 \times 2} = 1\,260 \text{ вариантов.}$$

---

Метод перегородок: сочетания с повторениями

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

Типичная инженерная задача: распределить $k$ неразличимых запросов вычислительной нагрузки по $n$ доступным серверам кластера. Сервер может получить несколько запросов, один запрос или не получить вовсе. Нам не важно, в каком порядке запросы поступают на конкретный узел, критично лишь итоговое количество задач на каждом из них.

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

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

Представим $k$ неразличимых запросов в виде цепочки символов-шаров: $\bullet \bullet \dots \bullet$. Чтобы разделить их между $n$ серверами, достаточно расставить между шарами ровно $n - 1$ перегородку $|$.

Рассмотрим пример: $k = 5$ задач распределяются по $n = 3$ серверам:

$$\bullet \bullet \mid \bullet \mid \bullet \bullet$$

Эта запись кодирует исход:

• Первый сервер получил 2 задачи;
• Второй сервер получил 1 задачу;
• Третий сервер получил 2 задачи.

Если две перегородки стоят подряд ($\bullet \bullet \mid \mid \bullet \bullet \bullet$), средний сервер получил 0 задач. Если перегородка стоит в самом начале ($\mid \bullet \bullet \bullet \mid \bullet \bullet$), первый сервер остался пустым.

Любое допустимое распределение взаимно однозначно соответствует последовательности из $k$ шаров и $n - 1$ перегородок. Суммарная длина такой символьной строки составляет:

$$k + (n - 1) \text{ позиций.}$$

Задача свелась к базовому вопросу: сколькими способами можно выбрать места для $k$ шаров (или, что эквивалентно, для $n - 1$ перегородок) из общего числа позиций $n + k - 1$? Ответ дает сочетание без повторений:

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

Где:

• $n$ — количество типов объектов (или число доступных корзин/контейнеров);
• $k$ — суммарное количество неразличимых выбираемых объектов (шаров);
• $n - 1$ — количество виртуальных перегородок, разделяющих корзины;
• $\bar{C}_n^k$ — число возможных неупорядоченных наборов с повторениями.

Пример из практики. Аналитик собирает синтетический датасет для стресс-теста модели. Нужно распределить $k = 7$ однотипных признаков-заглушек по $n = 4$ слоям глубокой нейронной сети. Число возможных архитектурных схем распределения равно:

$$\bar{C}_4^7 = C_{4 + 7 - 1}^7 = C_{10}^7 = \frac{10!}{7! \times 3!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 \text{ конфигураций.}$$

---

Полная карта комбинаторных выборок

Теперь мы можем свести воедино все базовые схемы подсчета. Любая комбинаторная задача о выборке $k$ элементов из генеральной совокупности объема $n$ классифицируется по двум бинарным осям:

1. Порядок исходов: важен (последовательность) или не важен (состав подмножества).
2. Повторение элементов: запрещено (выборка без возвращения) или разрешено (выборка с возвращением).

Режим выбора	Без повторений (уникальные элементы)	С повторениями (с возвратом / одинаковые типы)
Упорядоченный (порядок важен)	Размещения: $A_n^k = \frac{n!}{(n - k)!}$	Размещения с повторениями: $\bar{A}_n^k = n^k$
Неупорядоченный (порядок безразличен)	Сочетания: $C_n^k = \frac{n!}{k!(n - k)!}$	Сочетания с повторениями: $\bar{C}_n^k = C_{n + k - 1}^k$

Эта матрица — главный навигатор комбинаторики. Перед тем как выписывать факториалы, задайте себе два вопроса:

• Меняется ли результат при перестановке двух элементов местами? Если да — вы в верхней строке (размещения). Если нет — в нижней (сочетания).
• Может ли один и тот же физический объект или тип быть задействован повторно? Если нет — левый столбец. Если да — правый столбец.

---

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

Выборки и перестановки с повторениями формируют фундамент вероятностных моделей в обработке естественного языка (NLP) и классическом машинном обучении.

1. Мешок слов (Bag of Words) и языковое моделирование

Когда документ представляется в виде мультимножества слов, порядок токенов в предложении часто игнорируется, но частота каждого слова строго фиксируется. Если словарь содержит $V$ уникальных лексем, то короткий документ из $k$ слов — это неупорядоченная выборка с повторениями, число возможных профилей которой описывается величиной $\bar{C}_V^k$.

Если же мы строим генеративную модель (например, $n$-граммы), где порядок токенов критичен, каждая позиция текста предсказывается из словаря объема $V$. Пространство возможных предложений длины $k$ взрывается как $V^k$.

2. Мультиномиальное распределение вероятностей

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

Если событие может завершиться одним из $m$ исходов с вероятностями $p_1, p_2, \dots, p_m$ (причем $\sum p_i = 1$), то вероятность наблюдать в серии из $n$ независимых испытаний ровно $k_1$ исходов первого типа, $k_2$ второго и $k_m$ последнего равна произведению мультиномиального коэффициента на соответствующие вероятности:

$$P(X_1 = k_1, \dots, X_m = k_m) = \frac{n!}{k_1! \times k_2! \times \dots \times k_m!} \times p_1^{k_1} \times p_2^{k_2} \times \dots \times p_m^{k_m}$$

Пояснение элементов формулы:

• $n$ — общее число проведенных независимых испытаний (размер выборки);
• $k_1, \dots, k_m$ — зафиксированные количества наступлений каждого из $m$ событий ($\sum k_i = n$);
• $p_1, \dots, p_m$ — элементарные вероятности наступления каждого события в одном испытании;
• Мультиномиальный коэффициент $\frac{n!}{k_1! \dots k_m!}$ подсчитывает точное количество элементарных цепочек испытаний, приводящих к требуемому итоговому составу.

Практический пример. В задаче многоклассовой классификации модель категоризирует обращения пользователей на 3 типа: «Технический сбой» ($p_1 = 0{,}5$), «Вопрос по оплате» ($p_2 = 0{,}3$) и «Спам» ($p_3 = 0{,}2$).

Какова вероятность того, что из следующих $n = 5$ поступивших тикетов ровно 2 окажутся сбоями, 2 — вопросами по оплате и 1 — спамом? Сначала считаем число конфигураций:

$$\binom{5}{2, 2, 1} = \frac{5!}{2! \times 2! \times 1!} = \frac{120}{4} = 30$$

Затем перемножаем вероятности реализации каждого исхода в цепочке:

$$P = 30 \times (0{,}5)^2 \times (0{,}3)^2 \times (0{,}2)^1 = 30 \times 0{,}25 \times 0{,}09 \times 0{,}2 = 0{,}135 \text{ (или } 13{,}5\%\text{).}$$

Без мультиномиального коэффициента мы учли бы только один конкретный порядок поступления тикетов (например, строго «Сбой-Сбой-Оплата-Оплата-Спам»), занизив истинную вероятность ровно в 30 раз.

Принцип включений-исключений

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

Представьте типичную задачу продуктовой аналитики. Мобильным приложением пользуются клиенты из разных каналов привлечения: 120 тысяч пришли через поисковую рекламу, а 90 тысяч — через рекомендации блогеров. Если без оглядки применить простое сложение, получится 210 тысяч пользователей. Однако в логах авторизации обнаруживается всего 160 тысяч уникальных идентификаторов. Куда исчезли 50 тысяч человек? Они никуда не исчезали: эти 50 тысяч пользователей кликнули по обоим каналам и при наивном суммировании были посчитаны дважды.

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

Два множества: устранение двойного учета

Начнем с фундаментального случая двух пересекающихся множеств $A$ и $B$. Мощность множества (число входящих в него уникальных элементов) обозначается вертикальными чертами: $|A|$ и $|B|$.

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

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

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

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

Вернемся к нашему примеру с пользователями:

• Реклама в поиске ($A$): $|A| = 120$ тысяч.
• Блогеры ($B$): $|B| = 90$ тысяч.
• Оба источника ($A \cap B$): $|A \cap B| = 50$ тысяч.

Считаем общий уникальный охват:

$$|A \cup B| = 120 + 90 - 50 = 160\text{ тысяч.}$$

Баланс сошелся с логами. Каждого человека из группы $A \cap B$ мы сначала учли дважды ($+1$ от $A$ и $+1$ от $B$), а затем один раз вычли ($-1$ от $A \cap B$). Итоговый вклад каждого пользователя равен ровно $1$.

Три множества: волновой эффект компенсаций

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

Разберем, какой след оставляет каждый элемент в итоговой сумме в зависимости от того, в скольких множествах он состоит:

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

Чтобы вернуть элементы центральной зоны обратно, необходимо компенсировать избыточное вычитание и прибавить тройное пересечение.

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

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

• $|A| + |B| + |C|$ — сумма мощностей отдельных множеств (первый порядок, знак плюс).
• $|A \cap B| + |A \cap C| + |B \cap C|$ — сумма всех возможных парных пересечений, их число равно числу сочетаний $C_3^2 = 3$ (второй порядок, знак минус).
• $|A \cap B \cap C|$ — пересечение всех трех множеств, число таких троек равно $C_3^3 = 1$ (третий порядок, знак плюс).

Практический расчет: стек технологий в резюме

Аналитический отдел исследовал базу из 1000 кандидатов на вакансию Data Scientist по трем ключевым навыкам: знание Python ($P$), SQL ($S$) и математической статистики ($M$). Данные анкетирования показали:

• Знают Python ($|P|$): 650 человек
• Знают SQL ($|S|$): 550 человек
• Знают статистику ($|M|$): 450 человек
• Знают Python и SQL ($|P \cap S|$): 350 человек
• Знают Python и статистику ($|P \cap M|$): 250 человек
• Знают SQL и статистику ($|S \cap M|$): 200 человек
• Владеют всеми тремя инструментами ($|P \cap S \cap M|$): 100 человек

Сколько кандидатов владеют хотя бы одним из этих навыков?

$$|P \cup S \cup M| = (650 + 550 + 450) - (350 + 250 + 200) + 100$$

$$|P \cup S \cup M| = 1650 - 800 + 100 = 950\text{ человек.}$$

Следовательно, кандидатов без единого профильного навыка из этого списка осталось ровно $1000 - 950 = 50$ человек.

Общий принцип для $n$ множеств

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

1. Складываем размеры всех отдельных множеств ($+$).
2. Вычитаем размеры всех парных пересечений ($-$).
3. Прибавляем размеры всех тройных пересечений ($+$).
4. Вычитаем пересечения четверок ($-$), и так далее, пока не дойдем до пересечения всех $n$ множеств.

Математически для семейства множеств $A_1, A_2, \dots, A_n$ формула выглядит следующим образом:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^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|$$

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

• Знак $\bigcup_{i=1}^n A_i$ обозначает объединение всех $n$ множеств.
• Суммы берутся по всем неупорядоченным наборам индексов: парных пересечений набирается ровно $C_n^2$, тройных — $C_n^3$, и в общем случае пересечений по $m$ множеств — ровно $C_n^m$ штук (вспоминаем формулу сочетаний из четвертой главы).
• Множитель $(-1)^{m-1}$ задает чередование знаков: нечетные размеры пересечений входят со знаком плюс, четные — со знаком минус.

Почему формула всегда дает ровно 1: мост к биному Ньютона

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

Возьмем произвольный объект $x$, который входит ровно в $k$ множеств из $n$ доступных ($1 \leq k \leq n$). Посмотрим, какой суммарный вес получит этот объект во всей формуле:

• В сумме одиночных множеств $\sum |A_i|$ он будет учтен во всех тех множествах, где присутствует, то есть ровно $C_k^1 = k$ раз.
• В сумме парных пересечений он будет учтен в каждой паре, составленной из «его» $k$ множеств. Таких пар насчитывается $C_k^2$ раз.
• В тройных пересечениях он учтется $C_k^3$ раз, и так далее до пересечений размера $k$. В пересечения размера $k + 1$ и выше объект $x$ физически войти не может, там его вклад равен нулю.

Соберем все слагаемые веса объекта $x$ вместе:

$$\text{Итоговый вес } x = C_k^1 - C_k^2 + C_k^3 - C_k^4 + \dots + (-1)^{k-1} C_k^k$$

Теперь вспомним разложение бинома Ньютона для выражения $(1 - 1)^k$, изученное в главе о сочетаниях:

$$0 = (1 - 1)^k = C_k^0 \cdot 1^k \cdot (-1)^0 - C_k^1 + C_k^2 - C_k^3 + \dots + (-1)^k C_k^k$$

Поскольку $C_k^0 = 1$, перенесем все остальные члены в левую часть уравнения:

$$C_k^1 - C_k^2 + C_k^3 - \dots + (-1)^{k-1} C_k^k = C_k^0 = 1$$

Магия биномиальных коэффициентов гарантирует: для любого $k \geq 1$ знакопеременная сумма сочетаний тождественно равна единице. Никакой элемент не теряется и не дублируется.

Классическая задача комбинаторики: беспорядки

Принцип включений-исключений незаменим не только для подсчета простых баз данных, но и для решения структурных задач теории перестановок. Наиболее известная из них — задача о беспорядках (derangements).

Беспорядок (или субфакториал, обозначаемый $!n$ или $D_n$) — это перестановка $n$ различных элементов, в которой ни один элемент не остается на своей исходной позиции.

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

Применим метод от противного. Общее число всех возможных перестановок из $n$ элементов нам известно из второй главы — это факториал $n!$.

Определим «неблагоприятные» множества $A_i$ ($i = 1, \dots, n$): событие, при котором $i$-й гость получил свою родную шляпу. Нас интересуют исходы, не попавшие ни в одно из множеств $A_i$.

1. Зафиксируем одного конкретного гостя на своем месте. Остальные $n - 1$ шляп можно распределить произвольно $(n - 1)!$ способами. Всего таких одиночных событий $n$, то есть $C_n^1$.
2. Зафиксируем двух конкретных гостей на своих местах. Оставшиеся $n - 2$ шляп распределяются $(n - 2)!$ способами. Таких пар $C_n^2$.
3. Для $m$ фиксированных гостей число способов равно $(n - m)!$, а число таких наборов гостей — $C_n^m$.

Применим принцип включений-исключений для объединения свойств:

$$|A_1 \cup \dots \cup A_n| = \sum_{m=1}^n (-1)^{m-1} C_n^m (n - m)!$$

Распишем биномиальный коэффициент $C_n^m$ через факториалы:

$$C_n^m (n - m)! = \frac{n!}{m!(n - m)!} (n - m)! = \frac{n!}{m!}$$

Тогда число беспорядков $!n$ равно разности между всеми перестановками $n!$ и теми, где хотя бы один элемент остался на месте:

$$!n = n! - |A_1 \cup \dots \cup A_n| = n! - \sum_{m=1}^n (-1)^{m-1} \frac{n!}{m!} = n! \sum_{m=0}^n \frac{(-1)^m}{m!}$$

Раскроем скобки:

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

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

• $n!$ — общее число перестановок $n$ элементов.
• Выражение в скобках — сумма первых членов ряда Тейлора для экспоненты $e^x$ в точке $x = -1$.

Поделив число благоприятных исходов $!n$ на общее число исходов $n!$, получим вероятность $P(D_n)$ того, что произойдет полный беспорядок:

$$P(D_n) = \frac{!n}{n!} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \approx \frac{1}{e} \approx 0{,}367879$$

Ряд сходится невероятно быстро: уже при $n \geq 5$ вероятность того, что ни один человек не получит свою вещь при случайной раздаче, практически неотличима от $1/e \approx 36{,}8\%$.

Принцип в вероятности и машинном обучении: границы Бонферрони

В реальных задачах Data Science точный расчет всех слагаемых формулы включений-исключений часто невозможен: если у нас есть $n = 50$ признаков или моделей, полное число пересечений составляет $2^{50} - 1 \approx 10^{15}$ операций — снова дает о себе знать комбинаторный взрыв.

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

Для вероятностей совместных событий $P(A_i)$ это выражается цепочкой приближений:

Порядок усечения	Оценка	Математическое выражение	Роль в анализе
1-й порядок	Верхняя граница (Union Bound)	$P\left(\bigcup A_i\right) \leq \sum P(A_i)$	Оценка вероятности хотя бы одной ошибки
2-й порядок	Нижняя граница	$P\left(\bigcup A_i\right) \geq \sum P(A_i) - \sum P(A_i \cap A_j)$	Учет парных корреляций факторов
3-й порядок	Верхняя граница	$P\left(\bigcup A_i\right) \leq \text{сумма (1)} - \text{сумма (2)} + \text{сумма (3)}$	Уточненный доверительный интервал

Самое популярное из них — неравенство первого порядка, известное в Data Science как Union Bound (граница объединения событий):

$$P(A_1 \cup A_2 \cup \dots \cup A_n) \leq \sum_{i=1}^n P(A_i)$$

Эта граница лежит в основе статистической поправки Бонферрони для множественной проверки гипотез. Если в A/B-тестировании вы одновременно проверяете 20 различных метрик с порогом значимости $\alpha = 0{,}05$, то вероятность ложноположительного срабатывания хотя бы в одной из них (Family-Wise Error Rate) без поправки может достигать:

$$P(\text{ошибка}) \leq 20 \times 0{,}05 = 1{,}0$$

Чтобы суммарный риск ошибки по всем тестам не превышал желаемые $5\%$, порог значимости для каждого отдельного теста делят на число сравнений: $\alpha_{\text{new}} = 0{,}05 / 20 = 0{,}0025$. Так комбинаторный принцип включений-исключений защищает аналитиков от ложных открытий в экспериментах с большими массивами данных.