302
правки
Изменения
→Функция Каталана в виде непрерывной дроби
<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 + \cdots == s + 2s^2 + 5s^3 + 14s^4 + \cdots = Cat(s) − 1,</tex>
что дает нам квадратное уравнение на производящую функцию
<tex>s^{2}CatsCat^{2}(s) − Cat(s) + 1 = 0.</tex>
Перепишем это уравнение в виде
<tex>Cat(s) - s^{2}CatsCat^{2}(s)= 1,</tex>
или
<tex>Cat(s) = \cfrac{1}{1 - s^{2}CatsCat^{2}(s)}.</tex>
Подставив выражение для <tex>Cat(s)</tex> из левой части равенства в
правую часть того же равенства, получим
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - s^{2}CatsCat(s)}}.</tex>
Подставляя вновь выражение для <tex>Cat(s)</tex> в получившееся равенство и продолжая этот процесс, мы получаем представление для
функции Каталана в виде непрерывной дроби:
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s^{2}}{1 - \cfrac{s^{2}}{1 - \cdots}}}.</tex>
Полученное разложение нужно понимать следующим образом. Если мы оборвем непрерывную дробь на <tex>n</tex>-м шаге (оставив вместо нее конечную непрерывную дробь, которая представляет собой рациональную функцию), то коэффициенты разложения полученной функции по степеням <tex>s</tex> будут совпадать с коэффициентами разложения функции <tex>Cat(s)</tex> вплоть до члена <tex>s^{2n}</tex>.
