1632
правки
Изменения
м
rollbackEdits.php mass rollback
|proof = Если у нас есть дробно-рациональная производящая функция
<tex>\; f(x) = \cfrac{c_{101,0}+c_{111,1}x+c_{121,2}x^2+\cdots}{c_{000,0}+c_{010,1}x+c_{020,2}x^2+\cdots},</tex>
то в общем случае:
<tex>\; f(x) = \cfrac{1}{\cfrac{c_{000,0}}{c_{101,0}}+\cfrac{c_{000,0}+c_{010,1}x+c_{020,2}x^2+\cdots}{c_{101,0}+c_{111,1}x+c_{121,2}x^2+\cdots}-\cfrac{c_{000,0}}{c_{101,0}}} = \cfrac{c_{101,0}}{c_{000,0}+xf_1(x)},</tex>
где
<tex>\; f_1(x) = \cfrac{c_{202,0}+c_{212,1}x+c_{222,2}x^2+\cdots}{c_{101,0}+c_{111,1}x+c_{121,2}x^2+\cdots}</tex>
и
<tex>\; c_{2k2,k} = c_{101,0} \cdot c_{0,\: k+1} - c_{000,0} \cdot c_{1,\: k+1} \; (k=0,1, \cdots).</tex>
Аналогично
<tex>\; f_1(x) = \cfrac{c_{202,0}}{c_{101,0}+xf_2(x)},</tex>
где
<tex>\; f_1(x) = \cfrac{c_{303,0}+c_{313,1}x+c_{323,2}x^2+\cdots}{c_{202,0}+c_{212,1}x+c_{222,2}x^2+\cdots}</tex>
и
<tex>\; c_{3k3,k} = c_{202,0} \cdot c_{1,\: k+1} - c_{101,0} \cdot c_{2,\: k+1} \; (k=0,1, \cdots)</tex>
и так далее. Таким Образом
<tex>\; f(x) = \cfrac{c_{101,0}}{c_{000,0}+\cfrac{c_{202,0}x}{c_{101,0}+\cfrac{c_{303,0}}{c_{202,0}+\ldots}}} = \biggl[ 0;\cfrac{c_{101,0}}{c_{000,0}},\cfrac{c_{202,0}x}{c_{101,0}},\cfrac{c_{303,0}x}{c_{202,0}}, \cdots , \cfrac{c_{n0n,0}x}{c_{n-1, \: 0}} \biggr], </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^2 3 + \cdots == s + 2s^2 + 5s^3 + 14s^4 + \cdots = Cat(s) − 1,</tex>
что дает нам квадратное уравнение на производящую функцию
или
<tex>Cat(s) = \cfrac{1}{1 - sCat^{2}(s)}.</tex>
Подставив выражение для <tex>Cat(s)</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^{2nn}</tex>.
Заметим, что из-за наличия множителя <tex>s</tex> в числителе очередной дроби, присоединяемой на <tex>(n + 1)</tex>-м шаге, увеличение числа членов в непрерывной дроби не приводит к изменению первых <tex>n</tex> коэффициентов в ее разложении. Например,
Изменим несколько треугольник Дика, поставив на стрелках числа. А именно, поставим на каждой стрелке номер того ряда, в котором она находится. Номер на стрелке
мы будем интерпретировать как ее кратность, то есть как число различных стрелок, проходящих в данном направлении. В результате одному пути в треугольнике Дика отвечает несколько «различных» путей в треугольнике с кратностями. Их число равно произведению кратностей всех ребер, входящих в данный путь. То есть значение элемента треугольника, которому раньше соответствовал путь в точку плоскости <tex>(m;n)</tex>, теперь равно следующему: <tex>c_{m,n} = (n+1)c_{m-1,n+1}+nc_{m-1,n-1}</tex>.
[[Файл:R6.PNG]]
