В мире математики существуют концепции, которые действуют как «магические мосты», соединяя на первый взгляд не связанные между собой области. Одной из них является производящая функция (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. Заключение
Производящая функция — это не просто «коробка для хранения последовательности». Это «переводчик», который преобразует закономерности и свойства последовательности в функциональную форму, что позволяет применять мощные математические инструменты, такие как математический анализ и алгебра.
- Подсчет комбинаций заменяется произведением функций.
- Решение рекуррентного соотношения заменяется решением уравнения и разложением в ряд Тейлора.
Эта идея играет активную роль в самых разных областях: от разработки алгоритмов до сложнейших задач чистой математики. Обязательно добавьте этот новый взгляд на последовательности как на «функции» в свой набор инструментов для мышления.