Магия производящих функций: от чисел Фибоначчи до треугольника Паскаля 0:00
На шестой лекции курса MIT OpenCourseWare профессор Питер Шор подробно разобрал применение производящих функций для решения комбинаторных задач. Эти математические инструменты позволяют превращать сложные рекуррентные последовательности в алгебраические уравнения, облегчая поиск формул для членов последовательностей.
🛠 Основы манипуляции производящими функциями 0:14
Производящая функция $A(x) = \sum a_n x^n$ служит мощным инструментом для анализа последовательностей. Шор выделил ключевые операции:
- Сложение: Для двух классов объектов $A$ и $B$ их сумма $A(x) + B(x)$ соответствует дизъюнктному объединению.
- Умножение: Прямое произведение классов $A \times B$ выражается произведением их функций $A(x) \cdot B(x)$.
- Последовательности: Для нахождения функции, описывающей все возможные конечные последовательности элементов из набора $A$, используется формула $S(x) = \frac{1}{1 - A(x)}$.
В качестве примера Шор привел бинарные строки: если набор содержит 0 и 1, то $A(x) = 2x$, а функция для всех таких последовательностей — $S(x) = \frac{1}{1 - 2x}$.
🔢 Числа Фибоначчи через «телеграфный канал» 9:12
Интересным практическим приложением стала задача о передаче сообщений, состоящих из точек (длина 1) и тире (длина 2). Количество способов составить сообщение длиной $n$ порождает классическую последовательность Фибоначчи.
Шор отметил, что определение чисел Фибоначчи может варьироваться:
- В его лекционных записях традиционно используется $f_0=1, f_1=1$.
- По мнению профессора, Wikipedia стала «дефолтным арбитром» определений, где последовательность сдвинута ($f_0=0, f_1=1$).
Для вывода формулы $f_n = \frac{1}{\sqrt{5}} \left( \phi_+^{n+1} - \phi_-^{n+1} \right)$ Шор использовал метод частичных дробей. Полученная производящая функция для чисел Фибоначчи имеет вид $f(x) = \frac{1}{1 - x - x^2}$.
📐 Замощения и странные рекурренции 41:14
Разбирая задачу о замощении полоски $2 \times n$ треугольными и зигзагообразными плитками, лектор показал, как находить функции для более сложных условий. Полученная производящая функция $g(x) = \frac{1 - x^2}{1 - x^2 - 2x^3}$ привела к неинтуитивной рекуррентной формуле $f_n = f_{n-2} + 2f_{n-3}$, что наглядно демонстрирует мощь метода: алгебраические преобразования функции сами «подсказывают» закон изменения последовательности.
🔺 Связь с треугольником Паскаля 51:57
Заключительная часть была посвящена удивительной связи между диагоналями треугольника Паскаля и числами Фибоначчи. Шор доказал, что если подставить $x = z^2$ и $y = z$ в двумерную производящую функцию треугольника Паскаля $F(x, y) = \frac{1}{1 - x - y}$, то результатом будет именно та самая функция $\frac{1}{1 - z - z^2}$, описывающая числа Фибоначчи.
Профессор подчеркнул: этот результат можно доказать и комбинаторно, группируя последовательности точек и тире по количеству элементов, что дает еще один взгляд на природу биномиальных коэффициентов.
