# Питер Шор о связи диагоналей треугольника Паскаля и чисел Фибоначчи

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

---

## Магия производящих функций: от чисел Фибоначчи до треугольника Паскаля
[[JUMP:0:00]]

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

### 🛠 Основы манипуляции производящими функциями
[[JUMP: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}$.

### 🔢 Числа Фибоначчи через «телеграфный канал»
[[JUMP: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}$.

### 📐 Замощения и странные рекурренции
[[JUMP:41:14]]

Разбирая задачу о замощении полоски $2 \times n$ треугольными и зигзагообразными плитками, лектор показал, как находить функции для более сложных условий. Полученная производящая функция $g(x) = \frac{1 - x^2}{1 - x^2 - 2x^3}$ привела к неинтуитивной рекуррентной формуле $f_n = f_{n-2} + 2f_{n-3}$, что наглядно демонстрирует мощь метода: алгебраические преобразования функции сами «подсказывают» закон изменения последовательности.

### 🔺 Связь с треугольником Паскаля
[[JUMP:51:57]]

Заключительная часть была посвящена удивительной связи между диагоналями треугольника Паскаля и числами Фибоначчи. Шор доказал, что если подставить $x = z^2$ и $y = z$ в двумерную производящую функцию треугольника Паскаля $F(x, y) = \frac{1}{1 - x - y}$, то результатом будет именно та самая функция $\frac{1}{1 - z - z^2}$, описывающая числа Фибоначчи.

Профессор подчеркнул: этот результат можно доказать и комбинаторно, группируя последовательности точек и тире по количеству элементов, что дает еще один взгляд на природу биномиальных коэффициентов.