Представление производящей функций в виде непрерывных дробей

Определения

Определение:

Непрерывная дробь (англ. continued fraction) — это конечное или бесконечное математическое выражение вида $a_0+\cfrac{b_1}{a_1+\cfrac{b_2}{a_2+\cfrac{b_3}{a_3+\ldots}}} = \biggl[ a_0;\cfrac{b_1}{a_1},\cfrac{b_2}{a_2},\cfrac{b_3}{a_3}, \cdots \biggr]\;$ где $a_{0}$ и $b_n$ есть целые числа, а $a_n$ — натуральные числа (положительные целые).

Если $b_i = 1$ для всех $i$, выражение называется простой непрерывной дробью (англ. regular continued fraction).

В некоторой литературе вместо термина «непрерывная дробь» используют термин «цепная дробь».

Определение:

Конечная непрерывная дробь (англ. finite continued fraction) — это непрерывная дробь, которая состоит из конечных наборов $\langle a_0, a_1, a_2, a_3,\ldots, a_n \rangle$ и $\langle b_1, b_2, b_3,\ldots, b_n \rangle.$

Определение:

K-подходящей дробью (англ. k-suitable fraction) непрерывной дроби $\biggl[ a_0;\cfrac{b_k}{a_k} \biggr]^{n}_{1}$ называют обыкновенную дробь $\cfrac{P_k}{Q_k} \equiv \biggl[ a_0;\cfrac{b_1}{a_1},\cdots,\cfrac{b_k}{a_k} \biggr] (k = 1,2\cdots)$, где $k \leqslant n$, а $P_i, Q_i$ - многочлены $i$-ой степени

Разложение дробно-рациональной производящей функции

Утверждение:

Дробно-рациональная производящая функция всегда раскладывается в конечную непрерывную дробь.

$\triangleright$

Если у нас есть дробно-рациональная производящая функция $\; f(x) = \cfrac{c_{1,0}+c_{1,1}x+c_{1,2}x^2+\cdots}{c_{0,0}+c_{0,1}x+c_{0,2}x^2+\cdots},$ то в общем случае: $\; f(x) = \cfrac{1}{\cfrac{c_{0,0}}{c_{1,0}}+\cfrac{c_{0,0}+c_{0,1}x+c_{0,2}x^2+\cdots}{c_{1,0}+c_{1,1}x+c_{1,2}x^2+\cdots}-\cfrac{c_{0,0}}{c_{1,0}}} = \cfrac{c_{1,0}}{c_{0,0}+xf_1(x)},$ где $\; f_1(x) = \cfrac{c_{2,0}+c_{2,1}x+c_{2,2}x^2+\cdots}{c_{1,0}+c_{1,1}x+c_{1,2}x^2+\cdots}$ и $\; c_{2,k} = c_{1,0} \cdot c_{0,k+1} - c_{0,0} \cdot c_{1,k+1} \; (k=0,1, \cdots).$ Аналогично $\; f_1(x) = \cfrac{c_{2,0}}{c_{1,0}+xf_2(x)},$ где $\; f_1(x) = \cfrac{c_{3,0}+c_{3,1}x+c_{3,2}x^2+\cdots}{c_{2,0}+c_{2,1}x+c_{2,2}x^2+\cdots}$ и $\; c_{3,k} = c_{2,0} \cdot c_{1,k+1} - c_{1,0} \cdot c_{2,k+1} \; (k=0,1, \cdots)$ и так далее. Таким Образом $\; f(x) = \cfrac{c_{1,0}}{c_{0,0}+\cfrac{c_{2,0}x}{c_{1,0}+\cfrac{c_{3,0}}{c_{2,0}+\ldots}}} = \biggl[ 0;\cfrac{c_{1,0}}{c_{0,0}},\cfrac{c_{2,0}x}{c_{1,0}},\cfrac{c_{3,0}x}{c_{2,0}}, \cdots , \cfrac{c_{n,0}x}{c_{n-1,0}} \biggr],$ При чем легко убедиться, что непрерывная дробь получится конечной.

$\triangleleft$

Функция Каталана в виде непрерывной дроби

Рассмотрим производящую функцию для чисел Каталана

$Cat(s) = c_0 + c_1s + c_2s^2 + \cdots = 1 + s + 2s^2 + 5s^3 + \cdots$

Возведя ее в квадрат и умножив результат на $s$, получим

$sCat^2(s) = c^2_0s + (c_0c_1 + c_1c_0)s^2 + (c_0c_2 + c_1c_1 + c_2c_0)s^3 + \cdots = s + 2s^2 + 5s^3 + 14s^4 + \cdots = Cat(s) − 1,$

что дает нам квадратное уравнение на производящую функцию

$sCat^{2}(s) − Cat(s) + 1 = 0.$

Перепишем это уравнение в виде

$Cat(s) - sCat^{2}(s)= 1,$

или

$Cat(s) = \cfrac{1}{1 - sCat(s)}.$

Подставив выражение для $Cat(s)$ из левой части равенства в правую часть того же равенства, получим

$Cat(s) = \cfrac{1}{1 - \cfrac{s}{1 - sCat(s)}}.$

Подставляя вновь выражение для $Cat(s)$ в получившееся равенство и продолжая этот процесс, мы получаем представление для функции Каталана в виде непрерывной дроби:

$Cat(s) = \cfrac{1}{1 - \cfrac{s}{1 - \cfrac{s}{1 - \cdots}}}.$

Полученное разложение нужно понимать следующим образом. Если мы оборвем непрерывную дробь на $n$-м шаге (оставив вместо нее конечную непрерывную дробь, которая представляет собой рациональную функцию), то коэффициенты разложения полученной функции по степеням $s$ будут совпадать с коэффициентами разложения функции $Cat(s)$ вплоть до члена $s^{n}$. Заметим, что из-за наличия множителя $s$ в числителе очередной дроби, присоединяемой на $(n + 1)$-м шаге, увеличение числа членов в непрерывной дроби не приводит к изменению первых $n$ коэффициентов в ее разложении. Например,

$\cfrac{1}{1 - s} = \boldsymbol{1 + s} + s^2 + s^3 + s^4 + \cdots,$

$\cfrac{1}{1 - \cfrac{s}{1 - s}} = \boldsymbol{1 + s + 2s^2} + 4s^3 + 8s^4 + \cdots,$

$\cfrac{1}{1 - \cfrac{s}{1 - \cfrac{s}{1 - s}}} = \boldsymbol{1 + s + 2s^2 + 5s^3} + 13s^4 + \cdots$

Стабилизирующаяся часть разложения выделена.

Треугольник Дика

Треугольник Дика перечисляет пути в положительном квадранте плоскости, выходящие из начала координат и составленные из векторов $(1, 1)$ и $(1, −1)$.

Изменим несколько треугольник Дика, поставив на стрелках числа. А именно, поставим на каждой стрелке номер того ряда, в котором она находится. Номер на стрелке мы будем интерпретировать как ее кратность, то есть как число различных стрелок, проходящих в данном направлении. В результате одному пути в треугольнике Дика отвечает несколько «различных» путей в треугольнике с кратностями. Их число равно произведению кратностей всех ребер, входящих в данный путь. То есть значение элемента треугольника, которому раньше соответствовал путь в точку плоскости $(m;n)$, теперь равно следующему: $c_{m,n} = (n+1)c_{m-1,n+1}+nc_{m-1,n-1}$.

Теорема:

Производящая функция $F_{0}(s) = 1 + s^2 + 5s^4 + 61s^6 + 1385s^8 + \cdots$ для нижней стороны треугольника Дика представляется в виде непрерывной дроби $F_{0}(s) = \cfrac{1}{1 - \cfrac{1^2s^{2}}{1 - \cfrac{2^2s^2}{1 - \cfrac{3^2s^2}{1 - \cdots}}}}.$

Доказательство:

$\triangleright$

Производящая функция $F_0(s)$ перечисляет различные пути с началом и концом на высоте $0$. Обозначим через $F_i(s)$ производящую функцию, перечисляющую пути с началом и концом на высоте $i$, которые не опускаются ниже уровня $i$, по их длине. Тогда $F_0(s) = \cfrac{1}{1 - s^2F_1(s)}.$ Действительно, каждый путь с началом и концом на высоте $0$ единственным образом разбивается на такие участки, что Концы пути на каждом участке лежат на высоте $0$. Высота всех промежуточных точек пути на каждом участке больше нуля. Если отбросить начальный и конечный отрезок такого участка, то мы получим путь, начинающийся и заканчивающийся на высоте $1$. Аналогично, $F_1(s) = \cfrac{1}{1 - 4s^2F_2(s)}.$ Появление четверки в коэффициенте при $s^2$ объясняется тем, что к данному пути, начало и конец которого лежат на высоте $2$, начальный и конечный векторы, превращающие его в путь на высоте $1$, можно добавить четырьмя «различными» способами. Продолжая это рассуждение, мы заключаем, что $F_k(s) = \cfrac{1}{1 - (k+1)^2s^2F_{k+1}(s)},$ и непрерывная дробь теперь выписывается очевидным образом: $F_0(s) = \cfrac{1}{1 - s^2F_1(s)} = \cfrac{1}{1 - \cfrac{s^2}{1 - 4s^2F_2(s)}} = \cfrac{1}{1 - \cfrac{1s^{2}}{1 - \cfrac{4s^2}{1 - \cfrac{9s^2}{1 - \cdots}}}}.$

$\triangleleft$

См. также

• Производящая функция
• Арифметические действия с формальными степенными рядами

Источники информации

• Лекции о производящих функциях
• Непрерывная дробь
• Демидович Б. П., Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М.: Физматлит, 1963. — С. 53—73. — 660 с.