Генерация функций для чисел Каталана: теория и практика 0:01
Питер Шор, профессор MIT, в ходе своей лекции подробно разбирает метод производящих функций для решения комбинаторных задач. Центральной темой занятия становится вывод формулы для чисел Каталана, а также применение теоремы о последовательностях для анализа тайлингов 2xN-полос. Помимо математического аппарата, лекция включает разбор практических примеров и ответы на вопросы студентов по подготовке к предстоящему тестированию.
🌳 Числа Каталана и бинарные деревья 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$).
🧮 Решение квадратичного уравнения 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}$
🛤️ Пути Дика и альтернативный вывод 25:43
Альтернативный метод вывода основан на разбиении путей Дика на последовательности "поднятых" путей, которые касаются оси только в конечных точках.
- Теорема о последовательностях: Производящая функция последовательностей объектов определяется как $1 / (1 - A(x))$, где $A(x)$ — производящая функция самих объектов.
- Применение: Поскольку любой путь Дика является последовательностью таких "фундаментальных" путей, формула $C(x) = 1 / (1 - D(x))$ позволяет вывести то же самое уравнение.
🧱 Задачи на тайлинг 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 единицы, но метод производящих функций делает процесс систематическим и менее подверженным ошибкам.
