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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разложение дробно-рациональной производящей функции)
(Функция Каталана в виде непрерывной дроби)
 
(не показано 18 промежуточных версий этого же участника)
Строка 13: Строка 13:
  
 
{{Определение  
 
{{Определение  
|definition='''K-подходящей дробью''' (англ. ''finite continued fraction'')  непрерывной дроби <tex> \biggl[ a_0;\cfrac{b_k}{a_k} \biggr]^{n}_{1} </tex> называют обыкновенную дробь <tex>\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)</tex>, где <tex>k \leqslant n</tex>, а <tex>P_i, Q_i</tex> - многочлены <tex>i</tex>-ой степени}}
+
|definition='''K-подходящей дробью''' (англ. ''k-suitable fraction'')  непрерывной дроби <tex> \biggl[ a_0;\cfrac{b_k}{a_k} \biggr]^{n}_{1} </tex> называют обыкновенную дробь <tex>\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)</tex>, где <tex>k \leqslant n</tex>, а <tex>P_i, Q_i</tex> - многочлены <tex>i</tex>-ой степени}}
  
 
==Разложение дробно-рациональной производящей функции==
 
==Разложение дробно-рациональной производящей функции==
Строка 19: Строка 19:
 
|statement=
 
|statement=
 
[[Теорема_о_связи_между_рациональностью_производящей_функции_и_линейной_рекуррентностью_задаваемой_ей_последовательности| Дробно-рациональная производящая функция]] всегда раскладывается в конечную непрерывную дробь.
 
[[Теорема_о_связи_между_рациональностью_производящей_функции_и_линейной_рекуррентностью_задаваемой_ей_последовательности| Дробно-рациональная производящая функция]] всегда раскладывается в конечную непрерывную дробь.
|proof = Если
+
|proof = Если у нас есть дробно-рациональная производящая функция
  
<tex>f(x) = \cfrac{c_{10}+c_{11}x+c_{12}x^2+\cdots}{c_{00}+c_{01}x+c_{02}x^2+\cdots},</tex>
+
<tex>\; 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},</tex>
  
то в общем случае, проведя преобразования, будем иметь:
+
то в общем случае:
  
<tex>f(x) = \cfrac{1}{\cfrac{c_{00}}{c_{10}}+\cfrac{c_{00}+c_{01}x+c_{02}x^2+\cdots}{c_{10}+c_{11}x+c_{12}x^2+\cdots}-\cfrac{c_{00}}{c_{10}}} = \cfrac{c_{10}}{c_{00}+xf_1(x)},</tex>  
+
<tex>\; 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)},</tex>  
  
 
где
 
где
  
<tex>f_1(x) = \cfrac{c_{20}+c_{21}x+c_{22}x^2+\cdots}{c_{10}+c_{11}x+c_{12}x^2+\cdots}</tex>
+
<tex>\; 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}</tex>
  
 
и
 
и
  
<tex>c_{2k} = c_{10} \cdot c_{0,\: k+1} - c_{00} \cdot c_{1,\: k+1} \; (k=0,1, \cdots).</tex>
+
<tex>\; c_{2,k} = c_{1,0} \cdot c_{0,k+1} - c_{0,0} \cdot c_{1,k+1} \; (k=0,1, \cdots).</tex>
  
 
Аналогично
 
Аналогично
  
<tex>f_1(x) = \cfrac{c_{20}}{c_{10}+xf_2(x)},</tex>
+
<tex>\; f_1(x) = \cfrac{c_{2,0}}{c_{1,0}+xf_2(x)},</tex>
  
 
где
 
где
  
<tex>f_1(x) = \cfrac{c_{30}+c_{31}x+c_{32}x^2+\cdots}{c_{20}+c_{21}x+c_{22}x^2+\cdots}</tex>
+
<tex>\; 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}</tex>
  
 
и
 
и
  
<tex>c_{3k} = c_{20} \cdot c_{1,\: k+1} - c_{10} \cdot c_{2,\: k+1} \; (k=0,1, \cdots)</tex>
+
<tex>\; c_{3,k} = c_{2,0} \cdot c_{1,k+1} - c_{1,0} \cdot c_{2,k+1} \; (k=0,1, \cdots)</tex>
  
и так далее.
+
и так далее. Таким Образом
  
Таким Образом
+
<tex>\; 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], </tex>
  
<tex>f(x) = </tex>
+
При чем легко убедиться, что непрерывная дробь получится конечной.}}
  
 +
==Функция Каталана в виде непрерывной дроби==
 +
Рассмотрим [[Производящая_функция| производящую функцию]] для [[Числа_Каталана| чисел Каталана]]
  
 +
<tex>Cat(s) = c_0 + c_1s + c_2s^2 + \cdots = 1 + s + 2s^2 + 5s^3 + \cdots</tex>
  
}}
+
Возведя ее в квадрат и умножив результат на <tex>s</tex>, получим
  
 +
<tex>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,</tex>
  
 +
что дает нам квадратное уравнение на производящую функцию
  
 
+
<tex>sCat^{2}(s) − Cat(s) + 1 = 0.</tex>
#Любая конечная дробь представима в виде некоторой рациональной дроби <tex>\cfrac{P_n}{Q_n}</tex>, которую называют '''n-ой подходящей дробью'''.
 
#Всякий многочлен или дробно-рациональная функция может быть разложена в непрерывную дробь.
 
#:Например для функции <tex>f(x)=\displaystyle\frac{1-x}{1-5x+6x^2}</tex>:
 
#:
 
#:<tex>f(x)=\cfrac{1}{1-\cfrac{4 x}{1-\cfrac{2 x}{-4+6x}}}\;</tex>
 
#:
 
#Рациональная функция раскладывается в конечную непрерывную дробь.
 
 
 
==Функция Каталана в виде непрерывной дроби==
 
[[Производящая_функция| Производящая функция]] для [[Числа_Каталана| чисел Каталана]] удовлетворяет квадратному уравнению
 
 
 
<tex>s^{2}Cat^{2}(s) − Cat(s) + 1 = 0.</tex>
 
 
   
 
   
 
Перепишем это уравнение в виде
 
Перепишем это уравнение в виде
  
<tex>Cat(s) - s^{2}Cat^{2}(s)= 1,</tex>
+
<tex>Cat(s) - sCat^{2}(s)= 1,</tex>
  
 
или
 
или
  
<tex>Cat(s) = \cfrac{1}{1 - s^{2}Cat^{2}(s)}.</tex>
+
<tex>Cat(s) = \cfrac{1}{1 - sCat(s)}.</tex>
  
 
Подставив выражение для <tex>Cat(s)</tex> из левой части равенства в
 
Подставив выражение для <tex>Cat(s)</tex> из левой части равенства в
 
правую часть того же равенства, получим
 
правую часть того же равенства, получим
  
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - s^{2}Cat(s)}}.</tex>
+
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s}{1 - sCat(s)}}.</tex>
  
 
Подставляя вновь выражение для <tex>Cat(s)</tex> в получившееся равенство и продолжая этот процесс, мы получаем представление для
 
Подставляя вновь выражение для <tex>Cat(s)</tex> в получившееся равенство и продолжая этот процесс, мы получаем представление для
 
функции Каталана в виде непрерывной дроби:
 
функции Каталана в виде непрерывной дроби:
  
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - \cfrac{s^{2}}{1 - \cdots}}}.</tex>
+
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s}{1 - \cfrac{s}{1 - \cdots}}}.</tex>
  
Полученное разложение нужно понимать следующим образом. Если мы оборвем непрерывную дробь на <tex>n</tex>-м шаге (оставив вместо нее конечную непрерывную дробь, которая представляет собой рациональную функцию), то коэффициенты разложения полученной функции по степеням <tex>s</tex> будут совпадать с коэффициентами разложения функции <tex>Cat(s)</tex> вплоть до члена <tex>s^{2n}</tex>.
+
Полученное разложение нужно понимать следующим образом. Если мы оборвем непрерывную дробь на <tex>n</tex>-м шаге (оставив вместо нее конечную непрерывную дробь, которая представляет собой рациональную функцию), то коэффициенты разложения полученной функции по степеням <tex>s</tex> будут совпадать с коэффициентами разложения функции <tex>Cat(s)</tex> вплоть до члена <tex>s^{n}</tex>.
Заметим, что из-за наличия множителя <tex>s^2</tex> в числителе очередной дроби, присоединяемой на <tex>(n + 1)</tex>-м шаге, увеличение числа членов в непрерывной дроби не приводит к изменению первых <tex>n</tex> коэффициентов в ее разложении. Например,
+
Заметим, что из-за наличия множителя <tex>s</tex> в числителе очередной дроби, присоединяемой на <tex>(n + 1)</tex>-м шаге, увеличение числа членов в непрерывной дроби не приводит к изменению первых <tex>n</tex> коэффициентов в ее разложении. Например,
  
<tex>\cfrac{1}{1 - s^{2}} = \boldsymbol{1 + s^2} + s^4 + s^6 + s^8 + \cdots,</tex>
+
<tex>\cfrac{1}{1 - s} = \boldsymbol{1 + s} + s^2 + s^3 + s^4 + \cdots,</tex>
  
<tex>\cfrac{1}{1 - \cfrac{s^2}{1 - s^2}} = \boldsymbol{1 + s^2 + 2s^4} + 4s^6 + 8s^8 + \cdots,</tex>
+
<tex>\cfrac{1}{1 - \cfrac{s}{1 - s}} = \boldsymbol{1 + s + 2s^2} + 4s^3 + 8s^4 + \cdots,</tex>
  
<tex>\cfrac{1}{1 - \cfrac{s^{2}}{1 - \cfrac{s^{2}}{1 - s^2}}} = \boldsymbol{1 + s^2 + 2s^4 + 5s^6} + 13s^8 + \cdots</tex>
+
<tex>\cfrac{1}{1 - \cfrac{s}{1 - \cfrac{s}{1 - s}}} = \boldsymbol{1 + s + 2s^2 + 5s^3} + 13s^4 + \cdots</tex>
  
 
Стабилизирующаяся часть разложения выделена.
 
Стабилизирующаяся часть разложения выделена.
Строка 108: Строка 101:
  
 
Изменим несколько треугольник Дика, поставив на стрелках числа. А именно, поставим на каждой стрелке номер того ряда, в котором она находится. Номер на стрелке
 
Изменим несколько треугольник Дика, поставив на стрелках числа. А именно, поставим на каждой стрелке номер того ряда, в котором она находится. Номер на стрелке
мы будем интерпретировать как ее кратность, то есть как число различных стрелок, проходящих в данном направлении. В результате одному пути в треугольнике Дика отвечает несколько «различных» путей в треугольнике с кратностями. Их число равно произведению кратностей всех ребер, входящих в данный путь.
+
мы будем интерпретировать как ее кратность, то есть как число различных стрелок, проходящих в данном направлении. В результате одному пути в треугольнике Дика отвечает несколько «различных» путей в треугольнике с кратностями. Их число равно произведению кратностей всех ребер, входящих в данный путь. То есть значение элемента треугольника, которому раньше соответствовал путь в точку плоскости <tex>(m;n)</tex>, теперь равно следующему: <tex>c_{m,n} = (n+1)c_{m-1,n+1}+nc_{m-1,n-1}</tex>.
  
 
[[Файл:R6.PNG]]
 
[[Файл:R6.PNG]]

Текущая версия на 20:59, 8 мая 2018

Определения[править]

Определение:
Непрерывная дробь (англ. continued fraction) — это конечное или бесконечное математическое выражение вида

[math]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]\;[/math]

где [math]a_{0}[/math] и [math]b_n[/math] есть целые числа, а [math]a_n[/math] — натуральные числа (положительные целые).


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

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


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


Определение:
K-подходящей дробью (англ. k-suitable fraction) непрерывной дроби [math] \biggl[ a_0;\cfrac{b_k}{a_k} \biggr]^{n}_{1} [/math] называют обыкновенную дробь [math]\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)[/math], где [math]k \leqslant n[/math], а [math]P_i, Q_i[/math] - многочлены [math]i[/math]-ой степени


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

Утверждение:
Дробно-рациональная производящая функция всегда раскладывается в конечную непрерывную дробь.
[math]\triangleright[/math]

Если у нас есть дробно-рациональная производящая функция

[math]\; 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},[/math]

то в общем случае:

[math]\; 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)},[/math]

где

[math]\; 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}[/math]

и

[math]\; c_{2,k} = c_{1,0} \cdot c_{0,k+1} - c_{0,0} \cdot c_{1,k+1} \; (k=0,1, \cdots).[/math]

Аналогично

[math]\; f_1(x) = \cfrac{c_{2,0}}{c_{1,0}+xf_2(x)},[/math]

где

[math]\; 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}[/math]

и

[math]\; c_{3,k} = c_{2,0} \cdot c_{1,k+1} - c_{1,0} \cdot c_{2,k+1} \; (k=0,1, \cdots)[/math]

и так далее. Таким Образом

[math]\; 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], [/math]

При чем легко убедиться, что непрерывная дробь получится конечной.
[math]\triangleleft[/math]

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

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

[math]Cat(s) = c_0 + c_1s + c_2s^2 + \cdots = 1 + s + 2s^2 + 5s^3 + \cdots[/math]

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

[math]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,[/math]

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

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

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

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

или

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

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

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

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

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

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

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

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

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

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

Треугольник Дика[править]

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

R3.PNG

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

R6.PNG


Теорема:
Производящая функция [math]F_{0}(s) = 1 + s^2 + 5s^4 + 61s^6 + 1385s^8 + \cdots[/math] для нижней стороны треугольника Дика представляется в

виде непрерывной дроби

[math]F_{0}(s) = \cfrac{1}{1 - \cfrac{1^2s^{2}}{1 - \cfrac{2^2s^2}{1 - \cfrac{3^2s^2}{1 - \cdots}}}}.[/math]
Доказательство:
[math]\triangleright[/math]

Производящая функция [math]F_0(s)[/math] перечисляет различные пути с началом и концом на высоте [math]0[/math]. Обозначим через [math]F_i(s)[/math] производящую функцию, перечисляющую пути с началом и концом на высоте [math]i[/math], которые не опускаются ниже уровня [math]i[/math], по их длине. Тогда

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

Действительно, каждый путь с началом и концом на высоте [math]0[/math] единственным образом разбивается на такие участки, что

  1. Концы пути на каждом участке лежат на высоте [math]0[/math].
  2. Высота всех промежуточных точек пути на каждом участке больше нуля.

Если отбросить начальный и конечный отрезок такого участка, то мы получим путь, начинающийся и заканчивающийся на высоте [math]1[/math]. Аналогично,

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

Появление четверки в коэффициенте при [math]s^2[/math] объясняется тем, что к данному пути, начало и конец которого лежат на высоте [math]2[/math], начальный и конечный векторы, превращающие его в путь на высоте [math]1[/math], можно добавить четырьмя «различными» способами. Продолжая это рассуждение, мы заключаем, что

[math]F_k(s) = \cfrac{1}{1 - (k+1)^2s^2F_{k+1}(s)},[/math]

и непрерывная дробь теперь выписывается очевидным образом:

[math]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}}}}.[/math]
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]