В рамках курса Массачусетского технологического института (MIT) по комбинаторике профессор Питер Шор разбирает фундаментальные методы подсчета сложных структур. Лекция охватывает путь от классической теоремы Кэли о количестве остовных деревьев до мощного инструмента производящих функций, позволяющего решать комбинаторные задачи с помощью алгебраических манипуляций.
🌲 Теорема Кэли: сколько способов соединить точки? 0: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}$.
🛠️ Элегантное доказательство через двойной подсчет 6:03
Питер Шор отмечает, что существует множество способов доказать теорему Кэли. По его мнению, доказательство через поиск биекции (взаимно однозначного соответствия) между деревьями и последовательностями чисел от 1 до $n$ является «невероятно сложным и совершенно неинтуитивным». Вместо этого он предлагает метод двойного подсчета одного и того же объекта разными способами.
В качестве такого объекта выбираются помеченные корневые деревья с упорядоченными ребрами.
Процесс подсчета строится следующим образом:
- Первый способ: Мы берем количество обычных помеченных деревьев ($T_n$), умножаем на $n$ (выбор корня) и на $(n-1)!$ (количество способов упорядочить ребра).
- Второй способ: Мы строим дерево из «леса» (набора изолированных вершин), добавляя по одному ребру за раз.
Шор демонстрирует, что на каждом шаге $k$ при добавлении ребра у нас есть $n$ вариантов выбора узла, в который «втыкается» новое ребро, и $n-k-1$ вариантов выбора дерева, которое станет новой ветвью. Перемножение этих вариантов дает искомую формулу, подтверждающую, что $T_n = n^{n-2}$.
📈 Производящие функции: «механический» метод решения 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$ — решки.
🎲 Алгебра событий: сложение и умножение 39:58
Шор объясняет, как операции над множествами объектов отражаются на их производящих функциях:
- Сложение: Если у нас есть два непересекающихся класса объектов, производящая функция их объединения равна сумме их индивидуальных функций.
- Умножение: Соответствует декартову произведению классов. Это крайне полезно при расчете сумм независимых событий, например, при броске кубиков.
Профессор приводит пример с 6-гранным и 8-гранным кубиками. Чтобы узнать количество способов получить сумму $n$, нужно перемножить многочлены, представляющие каждый кубик. Например, расчет показывает, что существует ровно 5 способов выбросить сумму 10 (пары 6+4, 5+5, 4+6, 3+7, 2+8).
💰 Задача о размене монет 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)$, что позволяет использовать методы анализа бесконечных рядов.
🧪 Доказательство тождеств через производные 1:02:13
В финале лекции Питер Шор демонстрирует «трюк», который делает производящие функции по-настоящему мощными: использование дифференцирования для нахождения сложных сумм.
Рассматривается задача: найти значение суммы $\sum_{k=0}^{n} k \binom{n}{k}$. Вместо прямого подсчета Шор предлагает:
- Взять производящую функцию для биномиальных коэффициентов: $(1+x)^n = \sum \binom{n}{k} x^k$.
- Продифференцировать обе части по $x$. Это превращает $x^k$ в $k x^{k-1}$, «вынося» индекс $k$ в качестве коэффициента.
- Подставить $x = 1$.
Результат получается мгновенно: $n \cdot 2^{n-1}$. Для сравнения, профессор приводит альтернативный метод доказательства через «выбор лидера в комитете», который дает тот же результат, но требует иного логического подхода.
Шор завершает лекцию утверждением, что хотя эти примеры можно решить и другими способами, производящие функции станут незаменимыми при анализе более сложных структур, таких как числа Фибоначчи.
