# Питер Шор из MIT объясняет теорему Кэли и магию производящих функций Источник: https://www.youtube.com/watch?v=HpQUVd1MGso Канал: MIT OpenCourseWare Опубликовано: 17.12.2025 --- В рамках курса Массачусетского технологического института (MIT) по комбинаторике профессор Питер Шор разбирает фундаментальные методы подсчета сложных структур. Лекция охватывает путь от классической теоремы Кэли о количестве остовных деревьев до мощного инструмента производящих функций, позволяющего решать комбинаторные задачи с помощью алгебраических манипуляций. ## 🌲 Теорема Кэли: сколько способов соединить точки? [[JUMP:00:12]] Одной из центральных тем лекции является теорема Кэли, которая отвечает на вопрос: сколько различных помеченных деревьев можно построить на $n$ вершинах? Питер Шор начинает с простых примеров, чтобы аудитория могла самостоятельно угадать закономерность: * **Для n = 2:** существует только 1 способ (линия между вершинами 1 и 2). * **Для n = 3:** существует 3 способа. * **Для n = 4:** существует 16 способов. Здесь Шор поясняет, что деревья могут иметь разную структуру: например, «путь» (линия) дает 12 вариантов разметки, а «звезда» (центральный узел и три листа) — еще 4. * **Для n = 5:** сумма всех возможных конфигураций дает 125. На основе этой последовательности (1, 3, 16, 125...) выводится общая формула теоремы Кэли: число помеченных деревьев на $n$ вершинах равно $n^{n-2}$. ## 🛠️ Элегантное доказательство через двойной подсчет [[JUMP:06:03]] Питер Шор отмечает, что существует множество способов доказать теорему Кэли. По его мнению, доказательство через поиск биекции (взаимно однозначного соответствия) между деревьями и последовательностями чисел от 1 до $n$ является «невероятно сложным и совершенно неинтуитивным». Вместо этого он предлагает метод двойного подсчета одного и того же объекта разными способами. В качестве такого объекта выбираются **помеченные корневые деревья с упорядоченными ребрами**. Процесс подсчета строится следующим образом: 1. **Первый способ:** Мы берем количество обычных помеченных деревьев ($T_n$), умножаем на $n$ (выбор корня) и на $(n-1)!$ (количество способов упорядочить ребра). 2. **Второй способ:** Мы строим дерево из «леса» (набора изолированных вершин), добавляя по одному ребру за раз. Шор демонстрирует, что на каждом шаге $k$ при добавлении ребра у нас есть $n$ вариантов выбора узла, в который «втыкается» новое ребро, и $n-k-1$ вариантов выбора дерева, которое станет новой ветвью. Перемножение этих вариантов дает искомую формулу, подтверждающую, что $T_n = n^{n-2}$. ## 📈 Производящие функции: «механический» метод решения [[JUMP:29:03]] Профессор переходит к производящим функциям, называя их чрезвычайно полезным концептом. По словам Шора, преимущество этого метода заключается в его «механичности»: если для обычного комбинаторного доказательства требуется творческое озарение, то производящие функции позволяют прийти к результату через стандартную алгебру. Производящая функция для последовательности $a_0, a_1, a_2 \dots$ определяется как: $$F(x) = \sum_{i=0}^{\infty} a_i x^i$$ Здесь переменная $x$ не имеет физического смысла; Шор называет её инструментом для «отслеживания» индексов элементов последовательности. Ключевые примеры использования: * **Биномиальные коэффициенты:** Производящая функция для сочетаний $\binom{k}{n}$ — это просто $(1+x)^k$, что следует из бинома Ньютона. * **Вероятность:** При подбрасывании смещенной монеты $k$ раз вероятность выпадения $n$ орлов описывается функцией $(q + px)^k$, где $p$ — вероятность орла, а $q$ — решки. ## 🎲 Алгебра событий: сложение и умножение [[JUMP:39:58]] Шор объясняет, как операции над множествами объектов отражаются на их производящих функциях: * **Сложение:** Если у нас есть два непересекающихся класса объектов, производящая функция их объединения равна сумме их индивидуальных функций. * **Умножение:** Соответствует декартову произведению классов. Это крайне полезно при расчете сумм независимых событий, например, при броске кубиков. Профессор приводит пример с 6-гранным и 8-гранным кубиками. Чтобы узнать количество способов получить сумму $n$, нужно перемножить многочлены, представляющие каждый кубик. Например, расчет показывает, что существует ровно 5 способов выбросить сумму 10 (пары 6+4, 5+5, 4+6, 3+7, 2+8). ## 💰 Задача о размене монет [[JUMP:56:04]] Еще один классический пример — подсчет способов составить сумму в $n$ центов, имея ограниченный или неограниченный набор номиналов. Если у нас есть 6 пенни, 1 никель (5 центов) и 2 дайма (10 центов), производящая функция будет выглядеть как произведение трех скобок: $$(1 + x + \dots + x^6) \cdot (1 + x^5) \cdot (1 + x^{10} + x^{20})$$ Развернув это выражение, коэффициент при $x^{21}$ покажет, что существует всего 2 способа набрать 21 цент таким набором монет. Для бесконечного количества монет формула упрощается до вида $1/(1-x^k)$, что позволяет использовать методы анализа бесконечных рядов. ## 🧪 Доказательство тождеств через производные [[JUMP:1:02:13]] В финале лекции Питер Шор демонстрирует «трюк», который делает производящие функции по-настоящему мощными: использование дифференцирования для нахождения сложных сумм. Рассматривается задача: найти значение суммы $\sum_{k=0}^{n} k \binom{n}{k}$. Вместо прямого подсчета Шор предлагает: 1. Взять производящую функцию для биномиальных коэффициентов: $(1+x)^n = \sum \binom{n}{k} x^k$. 2. Продифференцировать обе части по $x$. Это превращает $x^k$ в $k x^{k-1}$, «вынося» индекс $k$ в качестве коэффициента. 3. Подставить $x = 1$. Результат получается мгновенно: $n \cdot 2^{n-1}$. Для сравнения, профессор приводит альтернативный метод доказательства через «выбор лидера в комитете», который дает тот же результат, но требует иного логического подхода. Шор завершает лекцию утверждением, что хотя эти примеры можно решить и другими способами, производящие функции станут незаменимыми при анализе более сложных структур, таких как числа Фибоначчи.