В рамках открытых лекций Массачусетского технологического института (MIT OpenCourseWare) преподаватель Бринмор Чепмен представил детальный разбор продвинутых методов подсчета в комбинаторике. Лекция посвящена трем фундаментальным китам комбинаторного анализа: принципу включений-исключений, принципу Дирихле и методу двойного подсчета. Автор наглядно демонстрирует, как простые бытовые аналогии — от раздачи игральных карт до подсчета волос у жителей Бостона — перерастают в мощный математический аппарат.
🃏 Принцип включений-исключений: от игральных карт до функции Эйлера 0:12
Комбинаторный анализ традиционно начинается с базового правила сложения для непересекающихся множеств. Наглядным примером служит стандартная колода карт: если посчитать количество королей и дам, ответ будет равен восьми, поскольку в колоде четыре короля и четыре дамы, и ни одна карта не может быть одновременно и тем, и другим. Однако ситуация существенно усложняется, когда множества начинают пересекаться. Чепмен предлагает задачу: определить количество карт, которые являются либо червами, либо «картинками» (валетами, дамами, королями). В колоде содержится 13 червовых карт и 12 «картинок». Простое сложение дает 25, но этот результат ошибочен. Причиной ошибки становится двойной подсчет: три карты — червовые валет, дама и король — принадлежат обоим множествам одновременно. Чтобы получить корректный результат, необходимо вычесть размер их пересечения из общей суммы, что дает в итоге 22 карты.
Этот эмпирический подход лежит в основе принципа включений-исключений (часто обозначаемого аббревиатурой PIE — Principle of Inclusion-Exclusion). Для двух произвольных множеств $A$ и $B$ формула их объединения выглядит следующим образом:
$$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$$
Визуализировать данную закономерность проще всего с помощью классических диаграмм Венна, где пересекающиеся круги наглядно иллюстрируют избыточно учтенную область.
При переходе к трем множествам ($A$, $B$ и $C$) структура формулы усложняется. Если просто сложить их размеры и вычесть попарные пересечения, то элементы, находящиеся на стыке всех трех множеств, окажутся учтенными ноль раз. Они прибавляются трижды в составе индивидуальных множеств и трижды вычитаются в составе попарных пересечений. Для компенсации этого эффекта тройное пересечение необходимо вернуть обратно в уравнение. Итоговая формула принимает вид:
$$\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert$$
Одним из канонических применений этого принципа является вычисление функции Эйлера (тотиента). Задача состоит в том, чтобы найти количество целых чисел от $1$ до $n$, взаимно простых с числом $n$. Предположив для простоты, что $n$ является произведением трех различных простых чисел $p$, $q$ и $r$, можно определить размер множеств, делящихся на каждое из них:
- Количество чисел, делящихся на $p$, составляет $\frac{n}{p}$.
- Количество чисел, делящихся на $q$, равняется $\frac{n}{q}$.
- Количество чисел, делящихся на $r$, составляет $\frac{n}{r}$.
Используя формулу включений-исключений для поиска дополнения к объединению этих множеств, математики приходят к элегантному общему выражению тотиента Эйлера:
$$n \cdot \left(1 - \frac{1}{p}\right) \cdot \left(1 - \frac{1}{q}\right) \cdot \left(1 - \frac{1}{r}\right)$$
В общем виде для произвольного количества множеств знаки слагаемых чередуются в зависимости от четности количества пересекаемых множеств, что формально доказывается через анализ вклада каждого элемента вселенной рассуждений в общую сумму.
🐦 Принцип Дирихле и загадка бостонских шевелюр 26:44
Второй важнейший инструмент комбинаторики — принцип Дирихле, в англоязычной традиции именуемый «принципом голубиных ящиков» (pigeonhole principle). Исторически его название восходит к средневековым голубятням. Суть принципа тривиальна: если пернатых оказывается больше, чем ящиков, то как минимум двум птицам придется разделить одно жилище. В терминах теории множеств это означает, что если размер множества $A$ (голуби) строго больше размера множества $B$ (ящики), то тотальная функция $f: A \to B$ принципиально не может быть инъективной.
Простейшие примеры действия этого закона окружают нас повсюду:
- В аудитории, где присутствует более 26 студентов, как минимум двое учащихся будут иметь имена, начинающиеся на одну и ту же букву английского алфавита.
- При наличии в ящике носков $n$ различных цветов, достаточно вытащить $n + 1$ носок, чтобы гарантированно получить хотя бы одну одноцветную пару.
Принцип Дирихле часто позволяет делать поразительные, неконструктивные выводы. Математики знают лишь о факте существования искомого объекта, но не могут указать, где именно он находится. Ярким примером служит демографический факт: население Бостона составляет около 650 000 человек, в то время как по биологическим данным на голове у среднестатистического человека растет менее 200 000 волос.
Поскольку численность жителей существенно превышает верхний предел количества волос, принцип Дирихле гарантирует, что в городе найдутся как минимум два человека с абсолютно идентичной шевелюрой. Более того, Чепмен формулирует обобщенный принцип Дирихле: если размер множества $A$ превосходит размер множества $B$ более чем в $k$ раз, мы гарантированно получаем коллизию порядка $k + 1$. Поскольку 650 000 более чем в три раза превосходит 200 000, можно с уверенностью утверждать, что в Бостоне проживает не менее четырех человек с одинаковым числом волос на голове.
Применение принципа Дирихле в серьезных задачах требует математической изобретательности, поскольку определить, что именно считать «голубями», а что — «ящиками», бывает непросто. В качестве продвинутого примера рассматривается задача о размещении 33 ладей на стандартной шахматной доске размером $8 \times 8$ клеток. Необходимо доказать, что при любой конфигурации фигур можно выбрать пять ладей, ни одна из которых не атакует другую (то есть все пять занимают уникальные строки и столбцы).
В роли «голубей» здесь выступают сами лади. Ключ к решению кроется в правильном конструировании восьми «ящиков». Для этого клетки шахматной доски нумеруются от 1 до 8 по диагоналям со смещением и циклическим переносом. Каждая такая группа содержит ровно восемь клеток, расположенных в абсолютно разных строках и столбцах. Поделив 33 ладьи на 8 диагональных групп, по обобщенному принципу Дирихле мы получаем коллизию:
$$33 > 4 \cdot 8$$
Это означает, что хотя бы в одной из групп окажется не менее пяти ладей. Поскольку клетки внутри одной группы гарантированно не пересекаются по строкам и столбцам, данные пять ладей не будут угрожать друг другу.
📐 Двойной подсчет и сокровища треугольника Паскаля 47:27
Заключительная часть лекции посвящена методу комбинаторных доказательств, также известному как двойной подсчет (double counting). Стратегия метода заключается в том, чтобы взять одно конкретное множество и вычислить количество его элементов двумя принципиально разными способами. Поскольку подсчитывается один и тот же объект, полученные математические выражения обязаны быть равны. Это позволяет доказывать сложные тождества без использования алгебраических преобразований.
Первое рассматриваемое тождество связывает сумму биномиальных коэффициентов с экспонентой:
$$\sum_{k=0}^n \binom{n}{k} = 2^n$$
Для его доказательства Бринмор Чепмен предлагает подсчитать количество бинарных последовательностей длины $n$. С одной стороны, применяя правило произведения, для каждой из $n$ позиций у нас есть два варианта выбора (0 или 1), что напрямую дает $2^n$ комбинаций. С другой стороны, эти же последовательности можно разбить на непересекающиеся классы по количеству единиц в них. Число последовательностей длины $n$, содержащих ровно $k$ единиц, по определению равно биномиальному коэффициенту $\binom{n}{k}$. Суммируя эти классы от $0$ до $n$, мы получаем левую часть уравнения.
Данное тождество является частным случаем знаменитой биномиальной теоремы, описывающей разложение степени двучлена:
$$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$
При раскрытии скобок выражение представляет собой сумму $2^n$ слагаемых, состоящих из различных комбинаций переменных $x$ и $y$. Группировка подобных членов приводит к появлению коэффициентов, соответствующих путям в треугольнике Паскаля. Концепция легко расширяется до мультиномиальной теоремы, где вместо двух переменных рассматривается сумма из $m$ слагаемых, возведенная в степень $n$.
Еще одно фундаментальное комбинаторное равенство — тождество Паскаля:
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
Алгебраическое доказательство через факториалы лектор иронично называет «грязным мусором», признаваясь в собственной профессиональной лени и нежелании тратить на это время. Вместо этого применяется изящный двойной подсчет на базе тех же бинарных последовательностей длины $n$ с ровно $k$ единицами. Общий объем этого множества равен $\binom{n}{k}$.
Затем множество разбивается на два непересекающихся подмножества по значению последнего бита:
- Если последовательность оканчивается на единицу, то в оставшихся $n - 1$ позициях необходимо разместить $k - 1$ единицу, что можно сделать $\binom{n-1}{k-1}$ способами.
- Если последовательность оканчивается на ноль, то все $k$ единиц должны быть распределены по первым $n - 1$ позициям, что дает $\binom{n-1}{k}$ вариантов.
Сложение этих двух вариантов по правилу суммы доказывает тождество Паскаля. Из него напрямую вытекает геометрия треугольника Паскаля, где каждое число является суммой двух стоящих над ним элементов. Кроме того, треугольник таит в себе множество других математических связей: например, сумма элементов вдоль его диагоналей неожиданно формирует последовательность чисел Фибоначчи. В качестве финального упражнения для самостоятельной работы Чепмен предлагает слушателям доказать методом двойного подсчета равенство суммы квадратов биномиальных коэффициентов строки центральному элементу удвоенной строки:
$$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$
