Раздел 1 · Последовательность

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

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

На примере перестановок градуировку можно увидеть как отображение от объектов к их степеням. Перестановки одного размера переходят в одно и то же число и тем самым образуют слой \mathcal C_n=\mathfrak S_n.

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

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

Раздел 2 · Аддитивная градуировка

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

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

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

Снабдим множество допустимых частей \mathcal P градуировкой \deg:\mathcal P\to\mathbb Z_{\gt0}, а \mathcal P_k=\{p\in\mathcal P:\deg p=k\} — его слой степени k. Обозначим число элементов этого слоя через \nu_k=|\mathcal P_k|. Потребуем, чтобы операция \mu была согласована с градуировкой: если u\in\mathcal C_{n-k} и p\in\mathcal P_k, то

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

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

Теперь требуется работать со всей последовательностью a_0,a_1,\ldots как с одним алгебраическим объектом. Такое представление не должно смешивать компоненты разных степеней или терять отдельные коэффициенты. Отсюда возникает первое требование к искомой конструкции.

Требование 1

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

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

\data{notation-key=encoding-map}{\Phi}(a)=\sum_{n\ge0}a_ne_n

Раздел 3 · Алгебра индексов

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

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

Определение

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

Свёрткой последовательностей a и b называется последовательность c=\data{notation-key=sequence-convolution}{a*b}. Её коэффициенты задаются равенством

(\data{notation-key=sequence-convolution}{a*b})_n=c_n=\sum_{i+j=n}a_i b_j=\sum_{i=0}^{n}a_i b_{n-i}

\begin{aligned}(\data{notation-key=sequence-convolution}{a*b})_n=c_n&=\sum_{i+j=n}a_i b_j\\&=\sum_{i=0}^{n}a_i b_{n-i}\end{aligned}

Следовательно, исходная рекурсия записывается как a_n=(\nu*a)_n при n\ge1. Та же операция имеет прямой комбинаторный смысл. Пусть \mathcal A и \mathcal B — градуированные множества со слоями \mathcal A_i,\mathcal B_j и числами элементов a_i,b_j. На произведении \mathcal A\times\mathcal B положим

Пара имеет степень n, если её компоненты имеют степени i и j с i+j=n. Поэтому число пар степени n равно \sum_{i+j=n}a_i b_j=(\data{notation-key=sequence-convolution}{a*b})_n: свёртка считает объекты, составленные из двух независимо выбранных градуированных компонентов.

Односторонние последовательности полагаются равными нулю при отрицательных индексах. Зафиксируем a, а b запишем в обратном порядке. Для вычисления c_n верхняя строка сдвигается так, чтобы b_0 оказался над a_n.

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

Требование 2

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

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

\data{notation-key=encoding-map}{\Phi}(\data{notation-key=sequence-convolution}{a*b})=\data{notation-key=encoding-map}{\Phi}(a)\,\data{notation-key=encoding-map}{\Phi}(b)

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

Для образов e_n=\data{notation-key=encoding-map}{\Phi}(\delta^{(n)}) отсюда следует e_i e_j=e_{i+j} и e_0=1. Следовательно, e_n=e_1^n. Обозначение x=e_1 даёт e_n=x^n, а коэффициентная линейность определяет всё представление:

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

Раздел 4 · Умножение и формальный ряд

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

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

При изменении итоговой степени сцена перечисляет все допустимые разложения n=i+j и суммирует соответствующие произведения коэффициентов.

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

Тем самым \data{notation-key=encoding-map}{\Phi}(\data{notation-key=sequence-convolution}{a*b})=\data{notation-key=encoding-map}{\Phi}(a)\data{notation-key=encoding-map}{\Phi}(b). Базис 1,x,x^2,\ldots определяется аддитивностью индексов, а не выбирается независимо от свёртки.

Теперь оба исходных требования выполнены: коэффициенты восстанавливаются по правилу \data{notation-key=coefficient-extractor}{[x^n]}\data{notation-key=ordinary-generating-function}{A(x)}=a_n, а произведение рядов соответствует свёртке последовательностей. Полученное представление имеет стандартное название.

Определение

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

Обыкновенной производящей функцией (ordinary generating function, OGF) последовательности a_0,a_1,a_2,\ldots называется формальный степенной ряд

\data{notation-key=ordinary-generating-function}{A(x)}=a_0+a_1x+a_2x^2+\cdots=\sum_{n\ge0}a_nx^n

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

Оператор \data{notation-key=coefficient-extractor}{[x^n]} извлекает n-ю координату: \data{notation-key=coefficient-extractor}{[x^n]}\data{notation-key=ordinary-generating-function}{A(x)}=a_n. Поэтому последовательность и её производящая функция взаимно однозначно определяют друг друга.

Раздел 5 · Рекуррентные уравнения

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

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

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

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

Коэффициент перед a_{n-k} равен h_k=\nu_k, поэтому

Поэтому для n\ge1

В общем случае рекурсии a_n=\gamma_1a_{n-1}+\cdots+\gamma_da_{n-d} соответствует ядро h=(0,\gamma_1,\ldots,\gamma_d,0,0,\ldots): порядок рекурсии определяет число его ненулевых коэффициентов.

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

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

Раздел 6 · Алгебраическое уравнение

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

Производящая функция ядра равна H(x)=\data{notation-key=encoding-map}{\Phi}(h)=x+x^2, а \data{notation-key=encoding-map}{\Phi}(\delta^{(0)})=1. Мультипликативность \data{notation-key=encoding-map}{\Phi} переводит свёрточное уравнение в алгебраическое:

Соберём слагаемые с \data{notation-key=ordinary-generating-function}{A(x)} в левой части и разделим на получившийся множитель:

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

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

Коэффициенты этого разложения и есть искомая последовательность. Рациональную функцию можно разложить двумя способами: последовательно находить коэффициенты из равенства Q(x)\data{notation-key=ordinary-generating-function}{A(x)}=P(x) или преобразовать дробь в сумму базисных функций с уже известными коэффициентами.

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

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

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

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

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

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

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

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

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

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

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

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

Раздел 7 · Общий рациональный случай

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

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

Пусть \data{notation-key=ordinary-generating-function}{A(x)}=P(x)/Q(x), где Q(0)\ne0. Искомый степенной ряд — не результат формального «раскрытия дроби», а единственный ряд \data{notation-key=ordinary-generating-function}{A(x)}=\sum_{n\ge0}a_nx^n, удовлетворяющий уравнению Q(x)\data{notation-key=ordinary-generating-function}{A(x)}=P(x).

Запишем Q(x)=\sum_{k=0}^{r}q_kx^k и P(x)=\sum_{n\ge0}p_nx^n, полагая p_n=0 выше степени многочлена P. Сравнение коэффициентов в равенстве Q(x)\data{notation-key=ordinary-generating-function}{A(x)}=P(x) даёт один и тот же шаг для каждой степени:

Здесь a_k=0 при k\lt0. При n=0 формула определяет a_0, при n=1 — a_1, и так далее. Поэтому именно условие q_0=Q(0)\ne0 позволяет на каждом шаге однозначно найти следующий коэффициент. Так устроено деление формальных степенных рядов: чтобы узнать коэффициент степени n, не требуется знать весь бесконечный ряд — достаточно уже найденных коэффициентов меньших степеней.

Раздел 8 · Общий рациональный случай

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

Исходная задача — разложить рациональную функцию \data{notation-key=ordinary-generating-function}{A(x)}=P(x)/Q(x) в формальный степенной ряд при x=0:

Предыдущий способ последовательно находит коэффициенты этого ряда из равенства Q(x)\data{notation-key=ordinary-generating-function}{A(x)}=P(x). Теперь получим явную формулу для a_n=\data{notation-key=coefficient-extractor}{[x^n]}\data{notation-key=ordinary-generating-function}{A(x)}, в которой зависимость от n видна непосредственно.

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

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

Определение

Семейство функций Gλ,r

\data{notation-key=partial-fraction-family}{G_{\lambda,r}}(x):=\frac{1}{(1-\lambda x)^r}, \quad r\ge1

При r=1 это геометрический ряд: G_{\lambda,1}(x)=\sum_{n\ge0}\lambda^n x^n. При произвольном r функция \data{notation-key=partial-fraction-family}{G_{\lambda,r}}(x)=G_{\lambda,1}(x)^r остаётся произведением известных рядов; её коэффициенты явно вычислим ниже.

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

Здесь H(x) — многочлен, N — конечное число слагаемых, c_k — их коэффициенты, а параметры \mu_k,r_k будут определены множителями знаменателя Q. Дальнейшие шаги строят именно это представление.

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

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

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

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

Поскольку Q(0)\ne0, разделим P и Q на Q(0) и будем считать, что Q(0)=1. Пусть q_d — старший коэффициент Q, \xi_1,\ldots,\xi_s — его различные корни, а m_1,\ldots,m_s — их кратности. Ни один корень не равен нулю.

Именно на втором шаге возникает деление на корень: после вынесения постоянного множителя -\xi_j переменная внутри скобки принимает вид x/\xi_j.

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

Теперь знаменатель непосредственно указывает, какие функции G_{\lambda_j,r} должны войти в искомое представление: для множителя кратности m_j нужны значения r=1,\ldots,m_j.

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

Таким образом, семейство \data{notation-key=partial-fraction-basis}{\mathcal G_Q}=\{G_{\lambda_j,r}:1\le j\le s,\ 1\le r\le m_j\} является искомым базисом, а числа \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}} — координатами дроби R/Q в этом базисе.

3. Находим координаты \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}}

Числа \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}} не извлекаются из степенного ряда. Это неизвестные коэффициенты в разложении дроби по базису \data{notation-key=partial-fraction-basis}{\mathcal G_Q}. Чтобы найти их, умножим разложение на Q(x). Знаменатели исчезнут, и получится тождество многочленов

Каждое выражение Q(x)/(1-\lambda_jx)^r теперь является многочленом. Сравнение коэффициентов при 1,x,\ldots,x^{\deg Q-1} даёт линейную систему для всех \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}}. Единственность разложения на простейшие дроби означает, что эта система имеет ровно одно решение.

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

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

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

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

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

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

Итак, координаты \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}} находятся алгебраически. Теперь остаётся другая задача: понять, какой коэффициент при x^n вносит каждая базисная функция.

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

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

Координаты \data{notation-key=partial-fraction-coordinate}{\rho_{j,r}} пока оставим символическими и решим одну универсальную задачу: вычислим \data{notation-key=coefficient-extractor}{[x^n]}\data{notation-key=partial-fraction-family}{G_{\lambda,r}}(x) для произвольной кратности r.

Равенство \data{notation-key=partial-fraction-family}{G_{\lambda,r}}=G_{\lambda,1}^{r} представляет эту функцию как произведение r одинаковых геометрических рядов. По правилу умножения рядов коэффициент при x^n собирается по всем решениям n_1+\cdots+n_r=n в неотрицательных целых числах. Каждое решение даёт один и тот же множитель \lambda^n, а число решений равно \binom{n+r-1}{r-1}: это стандартная формула для числа слабых композиций n на r частей. Поэтому

Виджет показывает, как кратность r меняет полиномиальный множитель перед экспонентой \lambda^n.

Теперь подставим найденный коэффициент в разложение \data{notation-key=ordinary-generating-function}{A(x)}:

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

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

Теорема

Структура коэффициентов рациональной функции

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

a_n=\sum_{j=1}^{s}\pi_j(n)\lambda_j^n \quad \deg \pi_j\lt m_j

Простой множитель 1-\lambda_jx даёт чистую экспоненту \rho_j\lambda_j^n. Множитель кратности m_j добавляет перед той же экспонентой полином степени не выше m_j-1.