В мире математики существуют концепции, которые действуют как «магические мосты», соединяя на первый взгляд не связанные между собой области. Одной из них является производящая функция (Generating Function). Путем преобразования дискретной «последовательности» в непрерывную «функцию» сложные комбинаторные задачи можно свести к алгебраическим вычислениям.
В этой статье мы начнем с базовой идеи производящих функций и подробно объясним их удивительную мощь — от вычисления комбинаций оплаты монетами до вывода общего члена последовательности Фибоначчи. Кроме того, мы затронем их применение к формальным степенным рядам (FPS) в алгоритмах и спортивном программировании.
1. Что такое производящая функция?
Пусть задана последовательность \(a_0, a_1, a_2, \dots\). Рассмотрим функцию \(A(x)\), в которой каждый член является коэффициентом при соответствующей степени \(x\).
\[ A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{n=0}^{\infty} a_n x^n \]Эта функция \(A(x)\) называется обыкновенной производящей функцией (Ordinary Generating Function) для последовательности \(\{a_n\}\).
Зачем выполнять такое преобразование? Потому что операции над последовательностями можно заменить алгебраическими операциями над функциями. Такие операции, как сдвиг, сложение или свертка последовательностей, преобразуются в знакомые операции, такие как сложение, умножение, дифференцирование и интегрирование функций.
graph LR
A["Последовательность (Дискретная)"] -->|"Преобразование в производящую функцию"| B["Функция (Непрерывная)"]
B -->|"Алгебраические операции (Производная, Произведение)"| C["Новая функция"]
C -->|"Извлечение коэффициентов"| D["Новая последовательность"]
A -.->|"Сложные операции"| D
2. Комбинации оплаты монетами и производящие функции
Чтобы интуитивно понять силу производящих функций, давайте рассмотрим задачу «оплаты монетами».
Задача: Найдите количество комбинаций \(a_n\) для оплаты ровно \(n\) иен с использованием монет достоинством 1 иена, 2 иены и 5 иен.
Мы решаем эту задачу с помощью производящих функций. Для каждой монеты мы создаем многочлен, соответствующий количеству используемых монет.
- Выбор монет по 1 иене: \(1 + x + x^2 + x^3 + \dots\) (0 монет, 1 монета, 2 монеты, …)
- Выбор монет по 2 иены: \(1 + x^2 + x^4 + x^6 + \dots\)
- Выбор монет по 5 иен: \(1 + x^5 + x^{10} + x^{15} + \dots\)
Рассмотрим функцию \(f(x)\), полученную путем их перемножения.
\[ f(x) = (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^5 + x^{10} + \dots) \]Коэффициент при \(x^n\) при раскрытии скобок в этом уравнении будет в точности равен количеству комбинаций \(a_n\) для оплаты \(n\) иен. Используя формулу суммы бесконечной геометрической прогрессии \(1 + r + r^2 + \dots = \frac{1}{1-r}\), функцию \(f(x)\) можно кратко выразить в виде рациональной функции:
\[ f(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \]Другими словами, не используя сложные рекуррентные соотношения или циклические вычисления, вы можете найти количество комбинаций для любого \(n\), просто найдя коэффициенты разложения Тейлора этой функции. В программировании эта концепция является важной основой для динамического программирования (DP).
Свертка и умножение многочленов
Почему произведение функций соответствует подсчету комбинаций? Давайте посмотрим, что происходит, когда мы перемножаем производящие функции \(A(x), B(x)\) двух последовательностей \(a_n\) и \(b_n\).
\[ A(x)B(x) = (a_0 + a_1 x + a_2 x^2 + \dots)(b_0 + b_1 x + b_2 x^2 + \dots) \]Коэффициент при \(x^n\) при раскрытии скобок будет \(\sum_{k=0}^{n} a_k b_{n-k}\). Это называется сверткой (Convolution). В примере с монетами сложение комбинаций вроде «набрать \(k\) иен монетами по 1 иене и \(n-k\) иен монетами по 2 иены» автоматически вычисляется с помощью этого произведения функций.
3. Применение к последовательности Фибоначчи
Далее, в качестве более продвинутого применения, давайте найдем общий член последовательности Фибоначчи. Последовательность Фибоначчи \(F_n\) определяется следующим образом:
- \(F_0 = 0\)
- \(F_1 = 1\)
- \(F_n = F_{n-1} + F_{n-2} \quad (n \ge 2)\)
Пусть производящая функция этой последовательности равна \(F(x) = \sum_{n=0}^{\infty} F_n x^n\).
\[ \begin{aligned} F(x) &= F_0 + F_1 x + \sum_{n=2}^{\infty} F_n x^n \\ &= 0 + x + \sum_{n=2}^{\infty} (F_{n-1} + F_{n-2}) x^n \\ &= x + x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} + x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} \\ &= x + x \sum_{m=1}^{\infty} F_m x^m + x^2 \sum_{k=0}^{\infty} F_k x^k \end{aligned} \]Здесь, поскольку \(F_0 = 0\), то \(\sum_{m=1}^{\infty} F_m x^m = F(x)\). Следовательно,
\[ F(x) = x + x F(x) + x^2 F(x) \]Решение этого уравнения относительно \(F(x)\) дает производящую функцию для последовательности Фибоначчи.
\[ F(x) = \frac{x}{1 - x - x^2} \]Удивительно, но информация о бесконечно продолжающейся последовательности Фибоначчи была сжата в одну простую дробную функцию.
Разложение на простейшие дроби и общий член
Чтобы извлечь общий член последовательности из этого выражения, мы раскладываем знаменатель на множители и выполняем разложение на простейшие дроби. Рассматривая решения уравнения \(1 - x - x^2 = 0\), пусть \(\alpha = \frac{1 + \sqrt{5}}{2}\) (золотое сечение) и \(\beta = \frac{1 - \sqrt{5}}{2}\). Знаменатель можно разложить на множители как \((1 - \alpha x)(1 - \beta x)\).
\[ F(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \alpha x} - \frac{1}{1 - \beta x} \right) \]Снова применяя формулу суммы геометрической прогрессии в обратную сторону, мы раскладываем каждое слагаемое в степенной ряд.
\[ \frac{1}{1 - \alpha x} = \sum_{n=0}^{\infty} \alpha^n x^n, \quad \frac{1}{1 - \beta x} = \sum_{n=0}^{\infty} \beta^n x^n \]Подстановка этих выражений и сравнение коэффициентов при \(x^n\) приводит к знаменитой формуле Бине.
\[ F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) \]
graph TD
S["Рекуррентное соотношение Фибоначчи"] -->|"Определить производящую функцию F(x)"| EQ["Составить уравнение для функции"]
EQ -->|"Решить алгебраически"| GF["F(x) = x / (1 - x - x^2)"]
GF -->|"Разложение на простейшие дроби"| PF["(A / (1 - αx)) + (B / (1 - βx))"]
PF -->|"Разложение в степенной ряд и сравнение коэффициентов"| AN["Общий член (Формула Бине)"]
4. Экспоненциальные производящие функции и перестановки
При работе с комбинаторными задачами, в которых учитывается порядок, то есть с «перестановками», в игру вступает экспоненциальная производящая функция (Exponential Generating Function).
Для последовательности \(a_n\) экспоненциальная производящая функция \(E(x)\) определяется следующим образом:
\[ E(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n = a_0 + a_1 x + \frac{a_2}{2!} x^2 + \frac{a_3}{3!} x^3 + \dots \]При делении на \(n!\) вычисления с учетом порядка (такие как дифференцирование) принимают очень аккуратную форму. Например, экспоненциальная производящая функция для последовательности \(1, 1, 1, \dots\), в которой все элементы равны \(1\), равна \(e^x\).
\[ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots \]Используя это свойство, количество способов упорядочить элементы или количество перестановок, удовлетворяющих нескольким условиям, можно выразить как произведение экспоненциальных функций.
5. Эволюция к формальным степенным рядам (FPS)
В современной информатике и спортивном программировании производящие функции реализуются как формальные степенные ряды (Formal Power Series, FPS). В FPS нас не волнует, будет ли сходиться результат при подстановке конкретного числового значения вместо \(x\) (аналитические свойства); основное внимание уделяется просто алгебраическому манипулированию «последовательностью коэффициентов» как многочленами.
С использованием быстрого преобразования Фурье (БПФ - FFT) или теоретико-числового преобразования (NTT) произведение двух многочленов степени \(N\) (т. е. свертку последовательностей длины \(N\)) можно найти с вычислительной сложностью \(\mathcal{O}(N \log N)\). Это позволяет значительно ускорить вычисления, для которых при использовании динамического программирования потребовалось бы время \(\mathcal{O}(N^2)\).
6. Заключение
Производящая функция — это не просто «коробка для хранения последовательности». Это «переводчик», который преобразует закономерности и свойства последовательности в функциональную форму, что позволяет применять мощные математические инструменты, такие как математический анализ и алгебра.
- Подсчет комбинаций заменяется произведением функций.
- Решение рекуррентного соотношения заменяется решением уравнения и разложением в ряд Тейлора.
Эта идея играет активную роль в самых разных областях: от разработки алгоритмов до сложнейших задач чистой математики. Обязательно добавьте этот новый взгляд на последовательности как на «функции» в свой набор инструментов для мышления.