# Магия комбинаторики: от серийных номеров долларов до покерных комбинаций

Источник: https://www.youtube.com/watch?v=9X6HtUsxnDc
Канал: MIT OpenCourseWare
Опубликовано: 22.07.2025

---

В рамках академического курса Массачусетского технологического института (MIT) OpenCourseWare состоялась лекция, посвященная фундаментальным методам комбинаторного подсчета. Преподаватель Закари Эйбел подробно разобрал переход от базового правила произведения к правилу деления, объяснил природу биномиальных коэффициентов и продемонстрировал, как применять эти инструменты для анализа вероятностей в реальной жизни — от проверки серийных номеров на банкнотах до расчета сложнейших покерных рук. На примере классических задач комбинаторики лектор показал, почему интуитивные догадки часто подводят и как строгие математические алгоритмы защищают от ошибок избыточного подсчета.

## 🧮 Обобщенное правило произведения и загадка долларовых купюр
[[JUMP:0:12]]

Комбинаторика во многом строится на последовательном совершении выбора. Как напоминает Закари Эйбел, обобщенное правило произведения гласит: если процесс конструирования объекта состоит из последовательности шагов, и на каждом $i$-м шаге у нас есть фиксированное количество вариантов $n_i$ (независимо от предыдущих выборов), то общее число способов собрать такой объект равно произведению всех вариантов:

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

Классическим примером работы этого правила является расчет возможных перестановок в стандартной колоде карт. Для выбора первой карты доступно 52 варианта, для второй — 51, для третьей — 50 и так далее, что в итоге дает $52!$ (пятьдесят два факториал) возможных комбинаций. При этом конкретный выбор на предыдущем этапе меняет состав доступных карт, но само их число на каждом конкретном шаге остается неизменным.

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

Если цифры в номере могут повторяться, то для каждой позиции существует ровно 10 вариантов (от 0 до 9). В таком случае работает регулярное правило произведения: число доступных вариантов не меняется и не зависит от предыдущих шагов. Общее количество таких серийных номеров составляет:

$$10^8 = 100\ 000\ 000$$

Однако ситуация кардинально меняется, если поставить условие, что все 8 цифр в номере должны быть уникальными (дискретными). Для подсчета таких номеров Закари Эйбел использует метод «визуальных ячеек»:

* Для первой цифры доступно 10 вариантов.
* Для второй цифры остается 9 вариантов (нельзя повторять первую).
* Для третьей — 8 вариантов, и так далее до последней ячейки, где останется 3 варианта.

Согласно обобщенному правилу произведения, количество банкнот с полностью уникальными цифрами равно произведению чисел от 10 до 3. 

Поделив это число на общее количество возможных номеров ($10^8$), математики получают точную пропорцию: лишь около 1,8% от всех отпечатанных долларовых купюр обладают серийными номерами без повторяющихся цифр. Проведя экспресс-опрос среди студентов в аудитории, лектор убеждается в верности расчетов: ни у одного из присутствующих, имевших при себе наличные деньги, не оказалось купюры с уникальным набором цифр.

## 🔄 Правило деления: от биекций к отображениям «k-к-1»
[[JUMP:9:14]]

До этого момента в курсе лекций ключевым инструментом сопоставления множеств выступало правило биекции, или взаимно-однозначное соответствие. В математическом представлении биекция означает, что из каждого элемента множества $A$ выходит ровно одна стрелка, и в каждый элемент множества $B$ входит ровно одна стрелка. Если такое соответствие установлено, то размеры множеств равны ($|A| = |B|$).

Закари Эйбел предлагает обобщить этот принцип, перейдя к так называемому правилу деления, которое описывает соответствие типа «$k$-к-1».



Если из каждого элемента множества $A$ выходит одна стрелка, но в каждый элемент множества $B$ входит ровно $k$ стрелок, это означает, что элементы левого множества разбиты на группы строго одинакового размера $k$, каждая из которых проецируется на один элемент справа. Формально правило формулируется следующим образом:

$$\frac{|A|}{k} = |B|$$

Иными словами, если мы знаем размер избыточного множества $A$ и точно понимаем, в какое количество раз ($k$) мы пересчитали каждый целевой объект из множества $B$, мы можем просто разделить величину $|A|$ на коэффициент избыточности $k$.

## 👑 Рыцари Круглого стола и строго возрастающие последовательности
[[JUMP:12:49]]

Первое практическое применение правила деления лектор демонстрирует на классической задаче о рыцарях Круглого стола. Предположим, что $n$ рыцарей необходимо рассадить за круглым столом на $n$ одинаково удаленных друг от друга мест. При этом варианты рассадки, которые можно получить простым поворотом стола (ротацией), считаются эквивалентными. Математиков интересует не конкретный стул под каждым рыцарем, а исключительно циклический порядок их расположения.

Для решения задачи формируется два множества:

* Множество $A$ — все линейные перестановки рыцарей в ряд (их количество нам известно и равно $n!$).
* Множество $B$ — уникальные циклические рассадки, которые необходимо найти.

Функция $f$ переводит линейный ряд в круг, просто «замыкая» концы цепочки. Чтобы понять, является ли это отображение симметричным, Эйбел разбирает пример с 5 рыцарями. Линейные последовательности `1, 4, 5, 2, 3` и `4, 5, 2, 3, 1` при замыкании в круг дают абсолютно идентичный циклический порядок. 

Поскольку у круга из $n$ элементов существует ровно $n$ возможных точек старта для чтения по часовой стрелке, каждая уникальная круговая рассадка порождается ровно $n$ различными линейными последовательностями. Соответственно, перед нами отображение типа «$n$-к-1». Применяя правило деления, получаем итоговую формулу для количества круговых рассадок:

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

Вторым примером использования правила деления становится подсчет трехзначных серийных номеров, цифры в которых расположены в строго возрастающем порядке (например, `0, 1, 2` или `2, 4, 9`). Варианты с нарушением порядка (`4, 2, 3`) или с повторениями (`2, 2, 5`) исключаются.

Закари Эйбел предлагает альтернативный взгляд: задача эквивалентна поиску количества подмножеств размером в 3 цифры из 10 доступных (от 0 до 9). Если мы выбрали три любые цифры, существует только один-единственный способ расставить их по возрастанию. Чтобы связать это с перестановками, вводится функция $g$, которая берет полную перестановку всех 10 цифр и превращает первые три цифры в подмножество.

Чтобы определить коэффициент избыточности $k$, лектор анализирует конкретное подмножество цифр, например $\{3, 6, 7\}$. Сколько перестановок из 10 элементов дадут на первых трех позициях эти цифры?

1.  Первые три позиции должны быть заняты цифрами 3, 6 и 7 в любом порядке. Количество способов их переставить равно $3!$.
2.  Оставшиеся 7 позиций могут быть заняты другими семью цифрами в абсолютно любом порядке. Количество способов их переставить равно $7!$.

Используя правило произведения, находим, что для любого выбранного подмножества существует ровно $3! \cdot 7!$ порождающих его перестановок. Значит, функция осуществляет отображение типа «$3! \cdot 7!$-к-1». Поскольку общее число перестановок 10 цифр равно $10!$, размер целевого множества подмножеств равен:

$$\frac{10!}{3! \cdot 7!}$$

## 🍕 Формула «n выбрать k» и биномиальные коэффициенты
[[JUMP:32:52]]

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

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



В математическом мире эта запись имеет специальное обозначение — переменные $n$ и $k$ в круглых скобках без знака дроби. Читается эта конструкция как «$n$ выбрать $k$» (n choose k). Название «биномиальный коэффициент» закрепилось за ней из-за важной роли в алгебраическом разложении биномов.

Эйбел иллюстрирует универсальность формулы бытовыми примерами:

* **Заказ пиццы:** если из 15 доступных топпингов по условиям промо-акции нужно выбрать ровно 3, количество уникальных рецептов пиццы составит «15 выбрать 3», то есть $\frac{15!}{3! \cdot 12!}$.
* **Выбор волонтеров:** чтобы набрать команду из 4 добровольцев в лекционной аудитории на 200 студентов, существует $\binom{200}{4}$ способов.
* **Подбрасывание монеты:** если подбросить симметричную монету 100 раз, общее число возможных исходов (последовательностей орлов и решек) составит $2^{100}$. 

Для поиска количества последовательностей, в которых выпадет ровно 50 орлов и 50 решек, применяется биекция между позициями «орлов» в строке и подмножествами. Нам необходимо выбрать 50 конкретных бросков из 100, которые станут орлами, что дает $\binom{100}{50}$ комбинаций.

Интересно, что отношение идеального баланса $\binom{100}{50}$ к общему числу исходов $2^{100}$ составляет всего около 8%. Закари Эйбел подчеркивает, что этот результат часто кажется людям контринтуитивным, ведь исход 50/50 является математически самым ожидаемым и центральным. Тем не менее, точечно попасть в него сложно, а при увеличении числа бросков до 1000 вероятность идеального паритета падает примерно до 1%.

## 🃏 Искусство комбинаторных «рецептов»: подсчет покерных комбинаций
[[JUMP:39:33]]

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

В качестве полигона для испытаний Эйбел выбирает правила игры в покер. Классическая колода содержит 52 карты, разделенные на 13 рангов (от двойки до туза) и 4 масти (черви, трефы, пики, бубны). Покерная рука представляет собой подмножество из 5 карт. Соответственно, общее число возможных рук — это $\binom{52}{5}$.

Первая задача — подсчитать количество комбинаций «каре» (четыре одинаковых карты одного ранга и одна посторонняя карта). Преподаватель составляет простой «рецепт»:

1.  Выбрать ранг $R$, для которого мы заберем из колоды все 4 карты (например, четыре тройки).
2.  Выбрать одну дополнительную карту $C$ из оставшихся в колоде, ранг которой не равен $R$.

Чтобы доказать математическую строгость рецепта, необходимо проверить, формирует ли функция выбора биекцию между пространством инструкций (множество $A$) и реальными руками на столе (множество $B$). Проверка включает три критических вопроса:

* **Тотальность (Total):** Действительно ли любой рецепт создаст валидный объект? Да, поскольку выбрав ранг и карту другого ранга, мы гарантированно получим руку из 5 карт, содержащую каре.
* **Сюръективность (Surjective):** Можно ли построить абсолютно любую целевую комбинацию по этому рецепту? Да, для любого каре на столе мы всегда можем однозначно ткнуть пальцем в ранг, которого там 4 штуки, и в побочную карту.
* **Инъективность (Injective):** Строится ли каждая рука ровно одним уникальным способом? Да, здесь нет двусмысленности, порядок выбора шагов жестко фиксирован.

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

* Шаг 1 (выбор ранга): 13 вариантов.
* Шаг 2 (выбор побочной карты): $52 - 4 = 48$ вариантов.

Итоговое количество рук с комбинацией каре равно $13 \cdot 48 = 624$.

## ⚠️ Когда рецепты подводят: ловушки избыточного подсчета
[[JUMP:56:02]]

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

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

1.  Выбрать трефовую карту (13 вариантов).
2.  Выбрать червовую карту (13 вариантов).
3.  Выбрать пиковую карту (13 вариантов).
4.  Выбрать бубновую карту (13 вариантов).
5.  Выбрать пятую карту из любых оставшихся в колоде ($52 - 4 = 48$ вариантов).

Закари Эйбел тестирует этот рецепт на конкретном примере руки: `{6♦, Q♥, A♠, 2♣, J♠}`. Согласно рецепту, мы могли на шаге 3 выбрать `A♠`, а на шаге 5 в качестве побочной карты вытащить `J♠`. Но ничто не мешало нам на шаге 3 выбрать `J♠`, а в качестве пятой карты на шаге 5 получить `A♠`. 

Один и тот же финальный набор карт на руках игрока может быть получен двумя разными путями в рамках рецепта. Биекция нарушена. Однако, проанализировав структуру, лектор понимает, что этот рецепт дает строгое отображение «2-к-1», поскольку в такой руке всегда будет одна масть, представленная двумя картами, и они всегда могут поменяться местами в алгоритме. Результат по правилу произведения можно спасти, разделив его на 2:

$$\frac{13^4 \cdot 48}{2}$$

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

1.  Выбрать масть $S$, которая будет содержать две карты (4 варианта). Остальные три масти автоматически сортируются по алфавиту для исключения путаницы.
2.  Выбрать две карты масти $S$ сразу подмножеством, используя сочетания ($\binom{13}{2}$ вариантов).
3.  Выбрать по одной карте для трех оставшихся мастей ($13 \cdot 13 \cdot 13$ вариантов).

Финальная формула приобретает вид $4 \cdot \binom{13}{2} \cdot 13^3$, что математически тождественно предыдущему результату.

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

1.  Выбрать ранг $R$ для пары (13 вариантов).
2.  Выбрать 2 карты этого ранга ($\binom{4}{2}$ вариантов).
3.  Выбрать 3 любые другие карты из колоды ($\binom{50}{3}$ вариантов).

Закари Эйбел показывает, почему этот алгоритм несостоятелен, разбирая несколько потенциальных исходов игры на руках:

* Если у игрока две пары (`А-А` и `2-2`), этот рецепт может собрать такую руку 2 различными способами (сначала выбрав ранг тузов или сначала выбрав ранг двоек).
* Если у игрока трио (`А-А-А`), рецепт может составить эту комбинацию 3 способами, выбирая разные пары внутри трех тузов.
* Если у игрока фулл-хаус (`А-А-А-3-3`), у рецепта появляется 4 пути генерации.
* Если у игрока каре (`А-А-А-А`), то количество путей генерации возрастает до $\binom{4}{2} = 6$ способов.

Поскольку коэффициент избыточности меняется от руки к руке и зависит от структуры конкретного набора карт, данное отображение не является ни биекцией, ни отображением типа «$k$-к-1». Закари Эйбел призывает студентов к предельной бдительности: при проектировании комбинаторных алгоритмов критически важно задавать себе вопросы о том, все ли объекты строятся и строятся ли они уникально.