В рамках курса лекций Массачусетского технологического института (MIT) профессор Питер Шор представляет глубокое погружение в комбинаторику и методы подсчета элементов. В центре внимания лекции находятся фундаментальные концепции сочетаний, биекций и чисел Каталана, связывающие воедино различные математические структуры. Автор демонстрирует, как классические задачи теории графов и путей на плоскости находят изящные геометрические решения через универсальные комбинаторные формулы.
🔢 Сочетания, мультиномиальные коэффициенты и магия двойного подсчета 0:41
Классическая задача выбора $k$ элементов из множества объемом $n$ объектов имеет интуитивный, но требующий осторожности путь решения. Если выбирать предметы поочередно, то для первого объекта существует $n$ вариантов, для второго — $n - 1$, а для последнего — $n - k + 1$ вариантов. Однако такой прямолинейный подсчет приводит к избыточности. Если из множества чисел от 1 до 5 необходимо выбрать два элемента, то пары (3, 4) и (4, 3) дадут одно и то же итоговое подмножество. Чтобы скорректировать этот избыточный учет, полученное произведение необходимо разделить на количество возможных перестановок выбранных элементов, то есть на $k!$. Это приводит к стандартной формуле биномиального коэффициента:
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Одним из наиболее элегантных методов доказательства теорем о биномиальных коэффициентах является метод двойного подсчета. Его суть заключается в том, что если одно и то же множество объектов подсчитывается двумя разными способами, то полученные выражения должны быть тождественно равны.
В качестве примера можно рассмотреть задачу выбора $k$ элементов из $n$ объектов, зафиксировав один конкретный элемент. Возможны два сценария:
- Этот элемент входит в выбранное подмножество. Тогда из оставшихся $n - 1$ объектов нужно выбрать $k - 1$ элементов.
- Этот элемент не входит в подмножество. В таком случае все $k$ элементов выбираются из оставшихся $n - 1$ объектов.
Такой подход позволяет без сложных алгебраических вычислений доказать знаменитое тождество Паскаля, на котором строится одноименный треугольник:
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
Из симметрии треугольника Паскаля наглядно следует и свойство палиндромичности строк: $\binom{n}{k} = \binom{n}{n-k}$.
Когда задачу требуется расширить на разделение $n$ предметов по нескольким группам (например, на три группы размерами $a$, $b$ и $c$, где $a + b + c = n$), на сцену выходят мультиномиальные коэффициенты. Формула принимает вид:
$$\frac{n!}{a!b!c!}$$
Доказать ее можно последовательным выбором: сначала формируется первая группа из $a$ элементов, затем из оставшихся предметов выбирается группа $b$. При перемножении соответствующих биномиальных коэффициентов промежуточные факториалы сокращаются. Этот принцип без труда обобщается на любое количество подмножеств $k$.
🔄 Метод биекции и классическая задача о шарах и перегородках 14:13
Комбинаторы питают особую профессиональную слабость к биективным доказательствам, поскольку они раскрывают глубинную структурную взаимосвязь между совершенно разными классами задач. Функция считается биекцией, если она одновременно инъективна (не отображает разные элементы в одну точку) и сюръективна (покрывает всю область значений). Ключевое свойство биекции — ее обратимость: существование обратной функции гарантирует, что размеры двух исследуемых множеств абсолютно идентичны.
Проиллюстрировать силу биективного метода можно на задаче о распределении $n$ неразличимых шаров по $j$ цветным корзинам (или раскрашивании шаров). Профессор приводит пример с 4 шарами и 3 цветами, где прямой перебор вариантов дает в сумме 15 комбинаций. В процессе подсчета Питер Шор иронично замечает, что лекторам часто тяжело дается элементарная арифметика, ошибочно назвав число 15 результатом сочетания $\binom{5}{2}$ вместо правильного $\binom{6}{2}$.
Чтобы решить эту задачу в общем виде, применяется изящное биективное преобразование — метод «шаров и перегородок» (stars and bars):
- Шары выстраиваются в ряд.
- Между группами шаров разных цветов устанавливаются пространственные разделители. Для разделения на $j$ цветов требуется ровно $j - 1$ перегородка.
- Задача сводится к поиску всех возможных позиций для перегородок в общем ряду, состоящем из предметов и разделителей.
Поскольку мы имеем дело с $n$ шарами и $j - 1$ перегородками, общее число позиций равно $n + j - 1$. Из них нужно выбрать места для перегородок, что дает нам точную формулу биномиального коэффициента $\binom{n+j-1}{j-1}$. Данная функция полностью обратима, а значит, биекция доказана.
📈 Пути Дика и загадочные числа Каталана 31:01
Одной из самых красивых последовательностей в дискретной математике являются числа Каталана, обозначаемые как $C_n$. Они служат решением для огромного спектра комбинаторных задач. Как отмечает Шор, бывший профессор MIT Ричард Стенли в своих трудах собрал около 200 различных математических объектов, структура которых описывается этой последовательностью.
Классическим представлением чисел Каталана являются пути Дика. Путь Дика — это траектория на координатной сетке от точки $(0,0)$ до точки $(2n,0)$ длиной в $2n$ шагов. Каждый шаг совершается строго по диагонали вверх-вправо $(1, 1)$ или вниз-вправо $(1, -1)$. Главное условие: траектория никогда не должна опускаться ниже оси абсцисс ($x$-оси). Первые элементы последовательности выглядят следующим образом: 1, 2, 5, 14, 42, 132.
Удивительно, но те же самые числа Каталана кодируют структуру корневых плоских деревьев, а также строго бинарных деревьев, где каждый узел имеет либо двух детей, либо ни одного. В таком бинарном дереве количество внутренних (нелистовых) узлов всегда ровно на единицу меньше количества листьев.
Явная формула для вычисления чисел Каталана выглядит так:
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$
Доказательство этой формулы строится на принципе отражения. Общее число всех возможных путей из $(0,0)$ в $(2n,0)$ без ограничений по оси составляет $\binom{2n}{n}$, поскольку нам в любом случае требуется сделать ровно $n$ шагов вверх и $n$ шагов вниз. Чтобы найти число валидных путей Дика, необходимо из этого общего количества вычесть «плохие» пути — те, которые хотя бы раз пересекают запретную линию и опускаются до уровня $-1$.
Здесь применяется изящный геометрический трюк: если взять «плохой» путь и строго зеркально отразить всю его оставшуюся часть после первого же касания уровня $-1$, то конец пути вместо точки $(2n, 0)$ гарантированно попадет в точку $(2n, -2)$. Количество таких путей жестко фиксировано и описывается формулой $\binom{2n}{n-1}$. Проведя несложные алгебраические преобразования и вынеся общий множитель, математики получают каноническую формулу Каталана.
🌳 Связывая деревья и пути: структурная биекция 1:00:36
Чтобы окончательно доказать, что бинарные деревья подчиняются той же математической закономерности, Шор демонстрирует алгоритм построения прямой биекции между ними и путями Дика.
Процесс трансформации устроен следующим образом:
- Выполняется обход бинарного дерева в глубину (depth-first order), обходя узлы по внешней стороне.
- Каждому внутреннему узлу дерева при первом его посещении ставится в соответствие шаг вверх ($+1$).
- Каждому листу дерева ставится в соответствие шаг вниз ($-1$).
- Самый последний шаг, который неизбежно ведет к финальному листу, отбрасывается.
В результате получается последовательность из $n$ шагов вверх и $n$ шагов вниз. Тот факт, что траектория никогда не зайдет в отрицательную полуплоскость, гарантируется структурой самого дерева: при правильном обходе мы физически не можем встретить листьев больше, чем пройдено внутренних ветвей, пока не доберемся до самого конца графа. Любое корректно построенное бинарное дерево однозначно разворачивается в уникальный путь Дика, и наоборот.
🧮 Асимптотика и формула Стирлинга 1:14:33
В финальной части лекции профессор затрагивает вопрос о том, как быстро растут комбинаторные значения при стремлении $n$ к бесконечности. Для оценки факториалов больших чисел используется аппроксимация Стирлинга:
$$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$
Подставив это выражение в формулу центрального биномиального коэффициента, можно увидеть, что большинство громоздких экспоненциальных членов взаимно уничтожаются. В итоге получается лаконичная асимптотическая оценка:
$$\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$$
Соответственно, для чисел Каталана $C_n$ скорость их роста на бесконечности пропорциональна выражению:
$$C_n \approx \frac{4^n}{\sqrt{\pi} n^{3/2}}$$
Подводя итог, Питер Шор делится методологическим наблюдением: практически все элементы формулы Стирлинга можно вывести с помощью базового математического анализа или теории вероятностей. Единственной по-настоящему сложной и неочевидной задачей при доказательстве этой асимптотики остается строгое обоснование появления константы $\sqrt{\pi}$.
