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

Определения

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

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

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

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

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

Любая конечная дробь представима в виде некоторой рациональной дроби [math]\cfrac{P_n}{Q_n}[/math], которую называют n-ой подходящей дробью.

Свойства

Всякий многочлен или дробно-рациональная функция может быть разложена в непрерывную дробь:

[math]\cfrac{b_1}{a_1+\cfrac{b_2 x}{a_2+\cfrac{b_3 x}{a_3+\ldots}}}\;[/math]

Например для функции [math]f(x)=\displaystyle\frac{1-x}{1-5x+6x^2}[/math]:

[math]f(x)=\cfrac{1}{1-\cfrac{4 x}{1-\cfrac{2 x}{-4+6x}}}\;[/math]

Теорема (Разложение рациональной функции):

Любая рациональная функция раскладывается в конечную непрерывную дробь.

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

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

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

[math]s^{2}Cat^{2}(s) − Cat(s) + 1 = 0.[/math]

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

[math]Cat(s) - s^{2}Cat^{2}(s)= 1,[/math]

или

[math]Cat(s) = \cfrac{1}{1 - s^{2}Cat^{2}(s)}.[/math]

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

[math]Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - s^{2}Cat(s)}}.[/math]

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

[math]Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - \cfrac{s^{2}}{1 - \cdots}}}.[/math]

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

[math]\cfrac{1}{1 - s^{2}} = \boldsymbol{1 + s^2} + s^4 + s^6 + s^8 + \cdots,[/math]

[math]\cfrac{1}{1 - \cfrac{s^2}{1 - s^2}} = \boldsymbol{1 + s^2 + 2s^4} + 4s^6 + 8s^8 + \cdots,[/math]

[math]\cfrac{1}{1 - \cfrac{s^{2}}{1 - \cfrac{s^{2}}{1 - s^2}}} = \boldsymbol{1 + s^2 + 2s^4 + 5s^6} + 13s^8 + \cdots[/math]

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

См. также

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

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

• Лекции о производящих функциях
• Непрерывная дробь