Аналитическая теория чисел

Вывод производящей функции

Как превратить правило построения объектов в формулу для их числа? Если размеры складываются, подсчёт составных объектов приводит к свёртке последовательностей. Производящая функция выбрана именно так, чтобы эта свёртка стала обычным умножением. Благодаря этому рекурсии превращаются в алгебраические уравнения, из решений которых снова можно извлечь исходные коэффициенты.

Слои градуированного множества

Пусть $C$ — множество дискретных объектов, снабжённое отображением степени $\deg : C \to Z_{\geq 0}$ . Обозначим через $C_{n} = {u \in C ∣ \deg u = n}$ слой степени $n$ , а через $a_{n} = | C_{n} |$ — число объектов в этом слое. Результат подсчёта — не отдельное число, а вся последовательность

a = (a_{0}, a_{1}, a_{2}, \dots)

На примере перестановок градуировку можно увидеть как отображение от объектов к их степеням. Перестановки одного размера переходят в одно и то же число и тем самым образуют слой $C_{n} = S_{n}$ .

Перейдите от степени один к двум, затем к трём. До каждого переключения сосчитайте перестановки нужного размера. Различайте число точек в слое и число значений градуировки.

Простейшие примеры одной и той же конструкции:

Примеры градуированных множеств
Объекты	Градуированное множество $C$	Степень	Слой $C_{n}$	Число $a_{n}$
Двоичные слова	${0, 1}^{*}$	$\deg w = \| w \|$	${0, 1}^{n}$	$2^{n}$
Перестановки	$⨆_{m \geq 0} S_{m}$	$\deg σ = n$ для $σ \in S_{n}$	$S_{n}$	$n!$
Мономы от $d$ переменных	Все мономы от $d$ переменных	Полная степень	Мономы полной степени $n$	$(\binom{n + d - 1}{d - 1})$
Упорядоченные суммы	$(k_{1}, \dots, k_{r})$ , где $k_{i} \in S \subseteq Z_{> 0}$	$k_{1} + \dots + k_{r}$	Последовательности с суммой $n$	$\| C_{n} \|$

Индекс здесь несёт математическую информацию: он задаёт степень. Поэтому последовательность хранит не только значения $a_{n}$ , но и их положение в градуировке: объекты разных степеней принадлежат разным компонентам.

Сложение степеней порождает рекурсию

Таблица выше иллюстрировала только наличие градуировки. Теперь наложим дополнительное условие, которому не обязано удовлетворять произвольное градуированное множество: объект должен допускать каноническое разложение по последней присоединённой части.

Здесь участвуют два множества с разными ролями. $C$ состоит из объектов, которые мы считаем, а $P$ — из допустимых частей, присоединяемых на одном шаге построения. Включение $P \subseteq C$ не предполагается; связь между множествами задаёт операция комбинирования

μ : C \times P ⟶ C, (u, p) ⟼ u \cdot p

Далее рассматривается случай, когда операция определена для каждой пары $(u, p)$ : любая допустимая часть может быть присоединена к любому уже построенному объекту.

Для двоичных слов $C = {0, 1}^{*}$ , тогда как $P ≃ {0, 1}$ — отдельная копия алфавита, а комбинирование есть дописывание соответствующей буквы. Для упорядоченных сумм $C$ состоит из конечных последовательностей слагаемых, $P ≃ S$ — из отдельных разрешённых слагаемых, а комбинирование приписывает слагаемое в конец.

Чтобы получить рекурсию, нужно однозначно обратить последний шаг этой операции. Предположим, что каждый объект положительной степени допускает представление $u \cdot p$ , где $u$ — объект меньшей степени, а $p$ — одна допустимая часть. Для упорядоченной суммы такой частью служит последнее слагаемое, для слова — последняя буква, для замощения — последняя плитка.

Снабдим множество допустимых частей $P$ градуировкой $\deg : P \to Z_{> 0}$ , а $P_{k} = {p \in P ∣ \deg p = k}$ — его слой степени $k$ . Обозначим число элементов этого слоя через $ν_{k} = | P_{k} |$ . Потребуем, чтобы операция $μ$ была согласована с градуировкой: если $u \in C_{n - k}$ и $p \in P_{k}$ , то

\deg (u \cdot p) = (n - k) + k = n

Потребуем, чтобы это представление $u \cdot p$ было единственным. Степень $k = \deg p$ последней части разбивает $C_{n}$ на непересекающиеся подмножества. После удаления части остаётся объект из $C_{n - k}$ . Обозначим через $C_{n, k}$ подмножество объектов, у которых последняя часть имеет степень $k$ :

Фиксируем степень последней части
$C_{n, k} ≃ C_{n - k} \times P_{k}$
Разбиваем слой на непересекающиеся части
$C_{n} = ⨆_{k = 1}^{n} C_{n, k} ≃ ⨆_{k = 1}^{n} C_{n - k} \times P_{k}$
Результат: Переходим к числу объектов
$a_{n} = \sum_{k = 1}^{n} ν_{k} a_{n - k}, a_{n} = | C_{n} |, ν_{k} = | P_{k} |$

Для упорядоченных разложений числа последнее слагаемое канонично, поэтому достаточно одного индекса $n$ . В неупорядоченных разбиениях требуется дополнительное состояние — например, максимальное разрешённое слагаемое, — но рекурсия по-прежнему возникает из разбиения множества объектов на непересекающиеся случаи.

Теперь требуется работать со всей последовательностью $a_{0}, a_{1}, \dots$ как с одним алгебраическим объектом. Такое представление не должно смешивать компоненты разных степеней или терять отдельные коэффициенты. Отсюда возникает первое требование к искомой конструкции.

Представление должно быть инъективным и коэффициентно-линейным. Индексу $n$ соответствует базисный элемент $e_{n}$ , а последовательности $a$ — формальная сумма

Φ (a) = \sum_{n \geq 0} a_{n} e_{n}

Сложение индексов определяет базис

Рекурсия из предыдущего раздела имеет вид $a_{n} = \sum_{k = 0}^{n} ν_{k} a_{n - k}$ , если положить $ν_{0} = 0$ . Её правая часть зависит только от двух последовательностей и правила сложения индексов. Абстрагируем это правило.

Свёрткой последовательностей $a$ и $b$ называется последовательность $c = a * b$ . Её коэффициенты задаются равенством

(a * b)_{n} = c_{n} = \sum_{i + j = n} a_{i} b_{j}

(a * b)_{n} = c_{n} = \sum_{i = 0}^{n} a_{i} b_{n - i}

Следовательно, исходная рекурсия записывается как $a_{n} = (ν * a)_{n}$ при $n \geq 1$ . Та же операция имеет прямой комбинаторный смысл. Пусть $A$ и $B$ — градуированные множества со слоями $A_{i}, B_{j}$ и числами элементов $a_{i}, b_{j}$ . На произведении $A \times B$ положим

\deg (u, v) = \deg u + \deg v

Пара имеет степень $n$ , если её компоненты имеют степени $i$ и $j$ с $i + j = n$ . Поэтому число пар степени $n$ равно $\sum_{i + j = n} a_{i} b_{j} = (a * b)_{n}$ : свёртка считает объекты, составленные из двух независимо выбранных градуированных компонентов.

Односторонние последовательности полагаются равными нулю при отрицательных индексах. Зафиксируем $a$ , а $b$ запишем в обратном порядке. Для вычисления $c_{n}$ верхняя строка сдвигается так, чтобы $b_{0}$ оказался над $a_{n}$ .

Начните с нулевого индекса, затем сдвигайте строку по одной позиции. Перед сдвигом назовите новую пару множителей и пару, которая перестанет участвовать. Объясните, почему развернуть одну строку необходимо.

Область перекрытия содержит ровно пары $(a_{i}, b_{n - i})$ , входящие в сумму. Изменение $n$ сдвигает верхнюю строку и меняет состав суммы.

Представление должно переводить свёртку в умножение.

Φ (a * b) = Φ (a) Φ (b)

Пусть $δ^{(n)}$ — последовательность с единственной ненулевой координатой на месте $n$ . Тогда

δ^{(i)} * δ^{(j)} = δ^{(i + j)}

Для образов $e_{n} = Φ (δ^{(n)})$ отсюда следует $e_{i} e_{j} = e_{i + j}$ и $e_{0} = 1$ . Следовательно, $e_{n} = e_{1}^{n}$ . Обозначение $x = e_{1}$ даёт $e_{n} = x^{n}$ , а коэффициентная линейность определяет всё представление:

A (x) = Φ (a) = \sum_{n \geq 0} a_{n} x^{n}

Здесь $x$ обозначает образ $δ^{(1)}$ , а не числовой аргумент. Для операций с коэффициентами сходимость ряда не требуется.

Коэффициент произведения считает разложения

Возьмём $a = (1, 2, 1)$ и $b = (1, 1, 2)$ . Для суммарной степени $3$ два ненулевых вклада соответствуют разложениям $3 = 1 + 2$ и $3 = 2 + 1$ . Эти вклады равны $a_{1} b_{2} = 4$ и $a_{2} b_{1} = 1$ , поэтому $c_{3} = 5$ .

Для нулевой степени найдите единственную допустимую пару. Затем выберите степень три и перечислите допустимые разложения с учётом степеней обоих многочленов. Сравните число пар с суммой их весов: это одна и та же величина лишь в специальном случае.

При умножении рядов равенство $x^{i} x^{j} = x^{i + j}$ собирает в коэффициенте при $x^{n}$ все пары мономов с $i + j = n$ . Следовательно,

[x^{n}] A (x) B (x) = \sum_{i = 0}^{n} a_{i} b_{n - i} = (a * b)_{n}

Тем самым $Φ (a * b) = Φ (a) Φ (b)$ . Базис $1, x, x^{2}, \dots$ определяется аддитивностью индексов, а не выбирается независимо от свёртки.

Теперь оба исходных требования выполнены: коэффициенты восстанавливаются по правилу $[x^{n}] A (x) = a_{n}$ , а произведение рядов соответствует свёртке последовательностей. Полученное представление имеет стандартное название.

Обыкновенной производящей функцией (ordinary generating function, OGF) последовательности $a_{0}, a_{1}, a_{2}, \dots$ называется формальный степенной ряд

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots = \sum_{n \geq 0} a_{n} x^{n}

Если коэффициенты лежат в кольце $R$ , такие ряды образуют кольцо $R [[x]]$ . Равенство и операции в нём определяются коэффициентно; числовая подстановка вместо $x$ и аналитическая сходимость не используются.

Оператор $[x^{n}]$ извлекает $n$ -ю координату: $[x^{n}] A (x) = a_{n}$ . Поэтому последовательность и её производящая функция взаимно однозначно определяют друг друга.

A (x) = 2 - 3 x + 5 x^{4} + \dots

[x^{4}] A (x) = 5, [x^{2}] A (x) = 0

Рекурсия как свёртка с ядром

Вернёмся к конструкции из раздела 2. Пусть $C$ состоит из конечных упорядоченных сумм слагаемых $1$ и $2$ , а степень равна сумме слагаемых. Множество допустимых частей $P ≃ {1, 2}$ имеет по одной части каждой из степеней $1$ и $2$ , поэтому

ν_{1} = ν_{2} = 1, ν_{k} = 0 (k \notin {1, 2})

Удаление последнего слагаемого даёт рекурсию $a_{n} = a_{n - 1} + a_{n - 2}$ . При соглашении $a_{m} = 0$ для $m < 0$ она справедлива для $n \geq 1$ , а $a_{0} = 1$ соответствует пустой сумме. Тем самым $a_{0} = a_{1} = 1$ , и $a_{n}$ является сдвинутой последовательностью Фибоначчи.

Последовательность $ν$ , считающая допустимые части, уже является ядром свёртки; его не требуется угадывать. Обозначим $h = ν$ . Чтобы согласовать индексы, запишем правую часть рекурсии в порядке слагаемых $(h * a)_{n} = \sum_{k = 0}^{n} h_{k} a_{n - k}$ :

a_{n - 1} + a_{n - 2} = 0 \cdot a_{n} + 1 \cdot a_{n - 1} + 1 \cdot a_{n - 2}

Коэффициент перед $a_{n - k}$ равен $h_{k} = ν_{k}$ , поэтому

h_{k} = {\begin{cases} 1, & если k \in {1, 2} \\ 0, & иначе \end{cases}

h = (0, 1, 1, 0, 0, \dots)

Поэтому для $n \geq 1$

a_{n} = (h * a)_{n} = \sum_{k = 0}^{n} h_{k} a_{n - k}

В общем случае рекурсии $a_{n} = γ_{1} a_{n - 1} + \dots + γ_{d} a_{n - d}$ соответствует ядро $h = (0, γ_{1}, \dots, γ_{d}, 0, 0, \dots)$ : порядок рекурсии определяет число его ненулевых коэффициентов.

При первом доступном индексе вычислите следующий член по двум предыдущим. Сдвиньте ядро на один шаг и повторите вычисление. Какие коэффициенты остаются прежними и какие данные заменяются?

Остаётся включить начальные условия. При $n = 0$ свёртка равна нулю, а $a_{0} = 1$ . При $n = 1$ она уже даёт требуемое значение:

(h * a)_{0} = 0 (h * a)_{1} = h_{1} a_{0} = 1 = a_{1}

Поэтому единственная поправка требуется при нулевом индексе, и вся последовательность удовлетворяет уравнению

a = δ^{(0)} + h * a

От свёртки к производящей функции

Производящая функция ядра равна $H (x) = Φ (h) = x + x^{2}$ , а $Φ (δ^{(0)}) = 1$ . Мультипликативность $Φ$ переводит свёрточное уравнение в алгебраическое:

Переводим свёртку в произведение
$A (x) = 1 + H (x) A (x)$
Результат: Подставляем функцию ядра
$A (x) = 1 + (x + x^{2}) A (x)$

Соберём слагаемые с $A (x)$ в левой части и разделим на получившийся множитель:

Собираем слагаемые с производящей функцией
$(1 - x - x^{2}) A (x) = 1$
Результат: Делим на обратимый множитель
$A (x) = \frac{1}{1 - x - x^{2}}$

Переход к последней строке корректен в кольце формальных рядов: ряд $1 - x - x^{2}$ имеет обратный, поскольку его постоянный коэффициент равен единице и потому обратим в $R$ .

С этого момента исходная задача принимает точную алгебраическую форму: нужно разложить полученную рациональную функцию в формальный степенной ряд при $x = 0$ ,

A (x) = \frac{P (x)}{Q (x)} = \sum_{n \geq 0} a_{n} x^{n}

Коэффициенты этого разложения и есть искомая последовательность. Рациональную функцию можно разложить двумя способами: последовательно находить коэффициенты из равенства $Q (x) A (x) = P (x)$ или преобразовать дробь в сумму базисных функций с уже известными коэффициентами.

Сначала применим оба способа к примеру Фибоначчи, а затем сформулируем их для произвольных многочленов $P$ и $Q$ .

Читаем коэффициенты последовательно

Сдвиг ряда на $k$ позиций выражается умножением на $x^{k}$ :

[x^{n}] (x^{k} A (x)) = {\begin{cases} a_{n - k} & n \geq k \\ 0 & n < k \end{cases}

В данном случае достаточно выписать три сдвинутых ряда:

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots

x A (x) = a_{0} x + a_{1} x^{2} + a_{2} x^{3} + \dots

x^{2} A (x) = a_{0} x^{2} + a_{1} x^{3} + \dots

Теперь вычтем вторую и третью строки из первой и соберём одинаковые степени $x$ :

(1 - x - x^{2}) A (x) = a_{0} + (a_{1} - a_{0}) x + D (x)

D (x) = \sum_{n \geq 2} d_{n} x^{n}

d_{n} = a_{n} - a_{n - 1} - a_{n - 2}

Правая часть исходного равенства — постоянный ряд $1 = 1 + 0 x + 0 x^{2} + \dots$ . Два формальных ряда равны тогда и только тогда, когда совпадают коэффициенты при каждой степени. Поэтому

{\begin{cases} a_{0} = 1 \\ a_{1} - a_{0} = 0 \\ a_{n} - a_{n - 1} - a_{n - 2} = 0, & n \geq 2 \end{cases}

Таким образом, сравнение коэффициентов возвращает начальные условия и исходную рекурсию.

Получаем явную формулу

Чтобы выразить коэффициент непосредственно через $n$ , разложим знаменатель. Пусть $φ = (1 + \sqrt{5}) / 2$ и $ψ = (1 - \sqrt{5}) / 2$ . Тогда

Факторизуем знаменатель
$1 - x - x^{2} = (1 - φ x) (1 - ψ x)$
Результат: Разлагаем на простейшие дроби
$A (x) = \frac{φ}{\sqrt{5}} \frac{1}{1 - φ x} - \frac{ψ}{\sqrt{5}} \frac{1}{1 - ψ x}$

В кольце формальных рядов геометрическое разложение имеет вид $(1 - λ x)^{- 1} = \sum_{n \geq 0} λ^{n} x^{n}$ . Следовательно,

A (x) = \sum_{n \geq 0} \frac{φ^{n + 1} - ψ^{n + 1}}{\sqrt{5}} x^{n}

Коэффициент при $x^{n}$ теперь читается непосредственно:

a_{n} = [x^{n}] A (x) = \frac{φ^{n + 1} - ψ^{n + 1}}{\sqrt{5}}

При нумерации $a_{0} = a_{1} = 1$ это число Фибоначчи $F_{n + 1}$ .

Способ 1. Последовательное извлечение коэффициентов

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

Пусть $A (x) = P (x) / Q (x)$ , где $Q (0) \neq 0$ . Искомый степенной ряд — не результат формального «раскрытия дроби», а единственный ряд $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ , удовлетворяющий уравнению $Q (x) A (x) = P (x)$ .

Запишем $Q (x) = \sum_{k = 0}^{r} q_{k} x^{k}$ и $P (x) = \sum_{n \geq 0} p_{n} x^{n}$ , полагая $p_{n} = 0$ выше степени многочлена $P$ . Сравнение коэффициентов в равенстве $Q (x) A (x) = P (x)$ даёт одну и ту же трёхступенчатую процедуру для каждой степени:

Раскрываем коэффициент произведения
$[x^{n}] (Q (x) A (x)) = q_{0} a_{n} + \sum_{k = 1}^{r} q_{k} a_{n - k}$
Приравниваем коэффициенту правой части
$q_{0} a_{n} + \sum_{k = 1}^{r} q_{k} a_{n - k} = p_{n}$
Результат: Выражаем неизвестный коэффициент
$a_{n} = \frac{1}{q_{0}} (p_{n} - \sum_{k = 1}^{r} q_{k} a_{n - k})$

Здесь $a_{k} = 0$ при $k < 0$ . При $n = 0$ формула определяет $a_{0}$ , при $n = 1$ — $a_{1}$ , и так далее. Поэтому именно условие $q_{0} = Q (0) \neq 0$ позволяет на каждом шаге однозначно найти следующий коэффициент. Так устроено деление формальных степенных рядов: чтобы узнать коэффициент степени $n$ , не требуется знать весь бесконечный ряд — достаточно уже найденных коэффициентов меньших степеней.

От рациональной функции к явной формуле

Исходная задача — разложить рациональную функцию $A (x) = P (x) / Q (x)$ в формальный степенной ряд при $x = 0$ :

\frac{P (x)}{Q (x)} = \sum_{n \geq 0} a_{n} x^{n}

Предыдущий способ последовательно находит коэффициенты этого ряда из равенства $Q (x) A (x) = P (x)$ . Теперь получим явную формулу для $a_{n} = [x^{n}] A (x)$ , в которой зависимость от $n$ видна непосредственно.

Идея: перейти к функциям с известными рядами

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

G_{λ, r} (x) := \frac{1}{(1 - λ x)^{r}}, r \geq 1

При $r = 1$ это геометрический ряд: $G_{λ, 1} (x) = \sum_{n \geq 0} λ^{n} x^{n}$ . При произвольном $r$ функция $G_{λ, r} (x) = G_{λ, 1} (x)^{r}$ остаётся произведением известных рядов; её коэффициенты явно вычислим ниже.

Искомое представление имеет форму

A (x) = H (x) + \sum_{k = 1}^{N} c_{k} G_{μ_{k}, r_{k}} (x)

Здесь $H (x)$ — многочлен, $N$ — конечное число слагаемых, $c_{k}$ — их коэффициенты, а параметры $μ_{k}, r_{k}$ будут определены множителями знаменателя $Q$ . Дальнейшие шаги строят именно это представление.

1. Отделяем уже готовую часть

Многочлен $H (x)$ сам является конечным степенным рядом: его коэффициенты уже видны. Если $\deg P \geq \deg Q$ , находим эту часть обычным делением $P$ на $Q$ . Оно единственным образом определяет частное $H (x)$ и остаток $R (x)$ :

Делим числитель на знаменатель
$P (x) = H (x) Q (x) + R (x), \deg R < \deg Q$
Результат: Отделяем многочленную часть
$A (x) = H (x) + \frac{R (x)}{Q (x)}$

Если $\deg P < \deg Q$ , деление не требуется: полагаем $H (x) = 0$ и $R (x) = P (x)$ . После отделения $H$ остаётся дробь $R / Q$ со свойством $\deg R < \deg Q$ . Такая дробь называется правильной.

2. Знаменатель определяет базис

Поскольку $Q (0) \neq 0$ , разделим $P$ и $Q$ на $Q (0)$ и будем считать, что $Q (0) = 1$ . Пусть $q_{d}$ — старший коэффициент $Q$ , $ξ_{1}, \dots, ξ_{s}$ — его различные корни, а $m_{1}, \dots, m_{s}$ — их кратности. Ни один корень не равен нулю.

Факторизуем знаменатель по корням
$Q (x) = q_{d} \prod_{j = 1}^{s} (x - ξ_{j})^{m_{j}}$
Выносим множитель из каждого корня
$x - ξ_{j} = - ξ_{j} (1 - \frac{x}{ξ_{j}})$
Собираем постоянный множитель
$q_{d} \prod_{j = 1}^{s} (- ξ_{j})^{m_{j}} = Q (0) = 1$
Результат: Используем единичную нормировку
$Q (x) = \prod_{j = 1}^{s} {(1 - \frac{x}{ξ_{j}})}^{m_{j}}$

Именно на втором шаге возникает деление на корень: после вынесения постоянного множителя $- ξ_{j}$ переменная внутри скобки принимает вид $x / ξ_{j}$ .

Введём обратные к корням величины $λ_{j} = ξ_{j}^{- 1}$ . Именно они удобны для степенных рядов: множитель принимает вид $1 - λ_{j} x$ , а обратная к нему функция порождает геометрическую прогрессию с коэффициентами $λ_{j}^{n}$ . Поэтому

Q (x) = \prod_{j = 1}^{s} (1 - λ_{j} x)^{m_{j}}

Теперь знаменатель непосредственно указывает, какие функции $G_{λ_{j}, r}$ должны войти в искомое представление: для множителя кратности $m_{j}$ нужны значения $r = 1, \dots, m_{j}$ .

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

\frac{R (x)}{Q (x)} = \sum_{j = 1}^{s} \sum_{r = 1}^{m_{j}} ρ_{j, r} G_{λ_{j}, r} (x)

Таким образом, искомый базис — это семейство

G_{Q} = {G_{λ_{j}, r} : 1 \leq j \leq s, 1 \leq r \leq m_{j}}

Числа $ρ_{j, r}$ — координатами дроби $R / Q$ в этом базисе.

3. Находим координаты ρⱼ,ᵣ

Числа $ρ_{j, r}$ не извлекаются из степенного ряда. Это неизвестные коэффициенты в разложении дроби по базису $G_{Q}$ . Чтобы найти их, умножим разложение на $Q (x)$ . Знаменатели исчезнут, и получится тождество многочленов

Записываем разложение по базису
$\frac{R (x)}{Q (x)} = \sum_{j = 1}^{s} \sum_{r = 1}^{m_{j}} ρ_{j, r} \frac{1}{(1 - λ_{j} x)^{r}}$
Результат: Умножаем на общий знаменатель
$R (x) = \sum_{j = 1}^{s} \sum_{r = 1}^{m_{j}} ρ_{j, r} \frac{Q (x)}{(1 - λ_{j} x)^{r}}$

Каждое выражение $Q (x) / (1 - λ_{j} x)^{r}$ теперь является многочленом. Сравнение коэффициентов при $1, x, \dots, x^{\deg Q - 1}$ даёт линейную систему для всех $ρ_{j, r}$ . Единственность разложения на простейшие дроби означает, что эта система имеет ровно одно решение.

Пример: два простых множителя

Пусть $α \neq β$ и $Q (x) = (1 - α x) (1 - β x)$ . Числитель правильной дроби имеет степень меньше двух, поэтому записывается как $R (x) = u + v x$ . Ищем для него новые координаты $C, D$ в базисе $G_{α, 1}, G_{β, 1}$ .

Разлагаем по двум базисным дробям
$\frac{u + v x}{(1 - α x) (1 - β x)} = C G_{α, 1} (x) + D G_{β, 1} (x)$
Получаем числитель
$(C + D) - (β C + α D) x$
Результат: Сравниваем коэффициенты
${\begin{cases} u = C + D \\ v = - (β C + α D) \end{cases}$

Определитель этой системы равен $β - α \neq 0$ , поэтому для каждого линейного числителя существует единственная пара $C, D$ . Разложение на простейшие дроби здесь буквально является сменой координат в двумерном пространстве числителей.

Если множитель $1 - λ x$ имеет кратность $m$ , нужны все функции $G_{λ, 1}, \dots, G_{λ, m}$ . После приведения к общему знаменателю их числители равны $(1 - λ x)^{m - 1}, \dots, 1$ и образуют базис многочленов степени меньше $m$ .

Для простого множителя соответствующую координату можно получить без решения всей системы: умножить дробь на $1 - λ_{j} x$ и подставить корень $x = 1 / λ_{j}$ . Все остальные слагаемые исчезнут:

ρ_{j} = {(1 - λ_{j} x) \frac{R (x)}{Q (x)} |}_{x = 1 / λ_{j}}

При кратности $m_{j}$ сначала выделяется функция $F_{j} (x) = (1 - λ_{j} x)^{m_{j}} R (x) / Q (x)$ . Её значение в корне даёт $ρ_{j, m_{j}}$ , первая производная — следующую координату, и так далее. В общем виде, для $0 \leq k < m_{j}$ ,

ρ_{j, m_{j} - k} = \frac{F_{j}^{(k)} (1 / λ_{j})}{(- λ_{j})^{k} k!}

Итак, координаты $ρ_{j, r}$ находятся алгебраически. Теперь остаётся другая задача: понять, какой коэффициент при $x^{n}$ вносит каждая базисная функция.

4. Извлекаем коэффициенты базисных функций

Для $r = 1$ коэффициенты уже известны из геометрического ряда: $[x^{n}] G_{λ, 1} (x) = λ^{n}$ . Этого достаточно для простого множителя $1 - λ x$ . Но множитель кратности $m > 1$ добавляет в базис функции $G_{λ, 2}, \dots, G_{λ, m}$ , и их коэффициенты ещё предстоит найти.

Координаты $ρ_{j, r}$ пока оставим символическими и решим одну универсальную задачу: вычислим $[x^{n}] G_{λ, r} (x)$ для произвольной кратности $r$ .

Равенство $G_{λ, r} = G_{λ, 1}^{r}$ представляет эту функцию как произведение $r$ одинаковых геометрических рядов. По правилу умножения рядов коэффициент при $x^{n}$ собирается по всем решениям $n_{1} + \dots + n_{r} = n$ в неотрицательных целых числах. Каждое решение даёт один и тот же множитель $λ^{n}$ , а число решений равно $(\binom{n + r - 1}{r - 1})$ : это стандартная формула для числа слабых композиций $n$ на $r$ частей. Поэтому

G_{λ, r} (x) = \sum_{n \geq 0} (\binom{n + r - 1}{r - 1}) λ^{n} x^{n}

Начните с простого множителя и последовательно увеличивайте кратность. До переключения предскажите степень полинома перед экспонентой. Проверьте ответ по общей формуле, а не только по нескольким первым членам.

Теперь подставим найденный коэффициент в разложение $A (x)$ :

Подставляем базисное разложение
$A (x) = H (x) + \sum_{j = 1}^{s} \sum_{r = 1}^{m_{j}} ρ_{j, r} G_{λ_{j}, r} (x)$
Результат: Извлекаем коэффициент
$a_{n} = [x^{n}] H (x) + \sum_{j = 1}^{s} \sum_{r = 1}^{m_{j}} ρ_{j, r} (\binom{n + r - 1}{r - 1}) λ_{j}^{n}$

При фиксированном $j$ все слагаемые содержат одну экспоненту $λ_{j}^{n}$ . Соберём их полиномиальные множители:

π_{j} (n) := \sum_{r = 1}^{m_{j}} ρ_{j, r} (\binom{n + r - 1}{r - 1}), \deg π_{j} < m_{j}

Поскольку $H$ — многочлен, $[x^{n}] H (x) = 0$ для всех достаточно больших $n$ . Поэтому остаётся сумма по различным множителям знаменателя.

Для всех достаточно больших $n$

a_{n} = \sum_{j = 1}^{s} π_{j} (n) λ_{j}^{n} \deg π_{j} < m_{j}

Простой множитель $1 - λ_{j} x$ даёт чистую экспоненту $ρ_{j} λ_{j}^{n}$ . Множитель кратности $m_{j}$ добавляет перед той же экспонентой полином степени не выше $m_{j} - 1$ .

Вывод производящей функции

Слои градуированного множества

Градуировка перестановок

Сложение степеней порождает рекурсию

Сохранение координат

Сложение индексов определяет базис

Свёртка последовательностей

Переворот и сдвиг

Свёртка переходит в умножение

Коэффициент произведения считает разложения

Коэффициент произведения

Обыкновенная производящая функция