# Питер Шор: «Производящие функции — ключ к комбинаторным задачам»

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

---

## Генерация функций для чисел Каталана: теория и практика
[[JUMP:0:01]]

Питер Шор, профессор MIT, в ходе своей лекции подробно разбирает метод производящих функций для решения комбинаторных задач. Центральной темой занятия становится вывод формулы для чисел Каталана, а также применение теоремы о последовательностях для анализа тайлингов 2xN-полос. Помимо математического аппарата, лекция включает разбор практических примеров и ответы на вопросы студентов по подготовке к предстоящему тестированию.

### 🌳 Числа Каталана и бинарные деревья
[[JUMP:1:11]]

Числа Каталана ($C_n$) являются фундаментальным инструментом комбинаторики, позволяющим подсчитывать различные объекты, такие как корневые бинарные деревья и пути Дика. Пути Дика представляют собой последовательности шагов, которые никогда не опускаются ниже нулевой отметки на координатной плоскости и ведут из точки $(0, 0)$ в $(2n, 0)$.

Для нахождения производящей функции $C(x) = \sum_{n=0}^{\infty} C_n x^n$ профессор Шор использует рекуррентное соотношение:
$C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1}$

*   **Логика рекурсии:** При построении бинарного дерева с $2n+1$ узлами мы добавляем новый корень, который соединяет два поддерева. Если левое поддерево содержит $2j+1$ узлов, то правое — $2n-j-1$ узлов.
*   **Проверка:** Для $C_3 = 5$, сумма произведений $C_j C_{n-j-1}$ дает верный результат: $5 \cdot 1 + 2 \cdot 1 + 1 \cdot 2 + 1 \cdot 5 = 14$ (для $C_4$).

### 🧮 Решение квадратичного уравнения
[[JUMP:7:34]]

Для производящей функции чисел Каталана выводится квадратичное уравнение:
$C(x) = x C(x)^2 + 1$

После приведения к стандартному виду $C(x)^2 - C(x) + 1 = 0$, решение требует выбора одного из двух корней. Профессор демонстрирует, что при подстановке $x=0$ значение функции должно быть равно $1$. Применение формулы с отрицательным знаком дает лимит, равный единице, что подтверждает правильность выбора.

Далее с помощью биномиальной теоремы Шор разлагает функцию в ряд. В ходе кропотливых вычислений, приравнивая коэффициенты, он приходит к классической формуле:
$C_n = \frac{1}{n+1} \binom{2n}{n}$

### 🛤️ Пути Дика и альтернативный вывод
[[JUMP:25:43]]

Альтернативный метод вывода основан на разбиении путей Дика на последовательности "поднятых" путей, которые касаются оси только в конечных точках.

*   **Теорема о последовательностях:** Производящая функция последовательностей объектов определяется как $1 / (1 - A(x))$, где $A(x)$ — производящая функция самих объектов.
*   **Применение:** Поскольку любой путь Дика является последовательностью таких "фундаментальных" путей, формула $C(x) = 1 / (1 - D(x))$ позволяет вывести то же самое уравнение.

### 🧱 Задачи на тайлинг
[[JUMP:44:16]]

Вторая часть лекции посвящена подсчету количества способов замостить полосу $2 \times n$ плитками двух типов.

*   **Фундаментальные тайлинги ($a_n$):** Тайлинги, которые нельзя разделить вертикальной линией на две независимые части. Для нечетных $n$ существует два таких тайлинга, для четных — ноль.
*   **Общее количество ($b_n$):** Используя теорему о последовательностях, профессор получает производящую функцию $B(x) = \frac{1 - x^2}{1 - x^2 - 2x^3}$.

Из этой функции можно напрямую считать рекуррентное соотношение: $b_n = b_{n-2} + 2b_{n-3}$. Шор подчеркивает, что этот результат можно получить и интуитивно, рассматривая способы продления тайлинга на 2 или 3 единицы, но метод производящих функций делает процесс систематическим и менее подверженным ошибкам.