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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
==Определения==
 
 
{{Определение  
 
{{Определение  
|definition='''Непрерывная дробь''' (англ. ''continued fraction'') — это конечное или бесконечное математическое выражение вида
+
|definition=
<tex>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]\;</tex>
+
'''Непрерывная дробь''' (англ. ''continued fraction'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый следующий член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и номер члена последовательности <tex>n</tex>, вместе с заданными первыми p членами, где  <tex>p</tex> — порядок рекуррентного соотношения.
где <tex>a_{0}</tex> и <tex>b_n</tex> есть целые числа, а <tex>a_n</tex> — натуральные числа (положительные целые).}}
 
 
 
Если <tex>b_i = 1</tex> для всех <tex>i</tex>, выражение называется [[Цепная_дробь | простой непрерывной дробью]] (англ. ''regular continued fraction'').
 
 
 
В некоторой литературе вместо термина «непрерывная дробь» используют термин '''«цепная дробь»'''.
 
 
 
{{Определение
 
|definition='''Конечная непрерывная дробь''' (англ. ''finite continued fraction'')  — это непрерывная дробь, которая состоит из конечных наборов <tex>\langle a_0, a_1, a_2, a_3,\ldots, a_n \rangle</tex> и <tex>\langle b_1, b_2, b_3,\ldots, b_n \rangle.</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>-ой степени}}
 
 
 
==Разложение дробно-рациональной производящей функции==
 
{{Утверждение
 
|statement=
 
[[Теорема_о_связи_между_рациональностью_производящей_функции_и_линейной_рекуррентностью_задаваемой_ей_последовательности| Дробно-рациональная производящая функция]] всегда раскладывается в конечную непрерывную дробь.
 
|proof = Если у нас есть дробно-рациональная производящая функция
 
 
 
<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_{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_{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_{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_{2,0}}{c_{1,0}+xf_2(x)},</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_{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>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>Cat(s) - sCat^{2}(s)= 1,</tex>
 
 
 
или
 
 
 
<tex>Cat(s) = \cfrac{1}{1 - sCat(s)}.</tex>
 
 
 
Подставив выражение для <tex>Cat(s)</tex> из левой части равенства в
 
правую часть того же равенства, получим
 
 
 
<tex>Cat(s) = \cfrac{1}{1 - \cfrac{s}{1 - sCat(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^{n}</tex>.
 
Заметим, что из-за наличия множителя <tex>s</tex> в числителе очередной дроби, присоединяемой на <tex>(n + 1)</tex>-м шаге, увеличение числа членов в непрерывной дроби не приводит к изменению первых <tex>n</tex> коэффициентов в ее разложении. Например,
 
 
 
<tex>\cfrac{1}{1 - s} = \boldsymbol{1 + s} + s^2 + s^3 + s^4 + \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}{1 - \cfrac{s}{1 - s}}} = \boldsymbol{1 + s + 2s^2 + 5s^3} + 13s^4 + \cdots</tex>
 
 
 
Стабилизирующаяся часть разложения выделена.
 
 
 
==Треугольник Дика==
 
Треугольник Дика перечисляет пути в положительном квадранте плоскости, выходящие из начала координат и составленные из векторов <tex>(1, 1)</tex> и <tex>(1, −1)</tex>.
 
 
 
[[Файл:R3.PNG]]
 
 
 
Изменим несколько треугольник Дика, поставив на стрелках числа. А именно, поставим на каждой стрелке номер того ряда, в котором она находится. Номер на стрелке
 
мы будем интерпретировать как ее кратность, то есть как число различных стрелок, проходящих в данном направлении. В результате одному пути в треугольнике Дика отвечает несколько «различных» путей в треугольнике с кратностями. Их число равно произведению кратностей всех ребер, входящих в данный путь. То есть значение элемента треугольника, которому раньше соответствовал путь в точку плоскости <tex>(m;n)</tex>, теперь равно следующему: <tex>c_{m,n} = (n+1)c_{m-1,n+1}+nc_{m-1,n-1}</tex>.
 
 
 
[[Файл:R6.PNG]]
 
 
 
 
 
{{Теорема
 
|statement=Производящая функция <tex>F_{0}(s) = 1 + s^2 + 5s^4 + 61s^6 + 1385s^8 + \cdots</tex> для нижней стороны треугольника Дика представляется в
 
виде непрерывной дроби
 
 
 
<tex>F_{0}(s) = \cfrac{1}{1 - \cfrac{1^2s^{2}}{1 - \cfrac{2^2s^2}{1 - \cfrac{3^2s^2}{1 - \cdots}}}}.</tex>
 
 
 
|proof=Производящая функция <tex>F_0(s)</tex> перечисляет различные пути с началом и концом на высоте <tex>0</tex>. Обозначим через <tex>F_i(s)</tex> производящую функцию, перечисляющую пути с началом и концом на высоте <tex>i</tex>, которые не опускаются ниже уровня <tex>i</tex>, по их длине.
 
Тогда
 
 
 
<tex>F_0(s) = \cfrac{1}{1 - s^2F_1(s)}.</tex>
 
 
 
Действительно, каждый путь с началом и концом на высоте <tex>0</tex> единственным образом разбивается на такие участки, что
 
#Концы пути на каждом участке лежат на высоте <tex>0</tex>.
 
#Высота всех промежуточных точек пути на каждом участке больше нуля.
 
Если отбросить начальный и конечный отрезок такого участка, то мы получим путь, начинающийся и заканчивающийся на высоте <tex>1</tex>.
 
Аналогично,
 
 
 
<tex>F_1(s) = \cfrac{1}{1 - 4s^2F_2(s)}.</tex>
 
 
 
Появление четверки в коэффициенте при <tex>s^2</tex> объясняется тем, что к данному пути, начало и конец которого лежат на высоте <tex>2</tex>, начальный и конечный векторы, превращающие его в путь на высоте <tex>1</tex>, можно добавить четырьмя «различными» способами.
 
Продолжая это рассуждение, мы заключаем, что
 
 
 
<tex>F_k(s) = \cfrac{1}{1 - (k+1)^2s^2F_{k+1}(s)},</tex>
 
 
 
и непрерывная дробь теперь выписывается очевидным образом:
 
 
 
<tex>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}}}}.</tex>
 
 
 
 
}}
 
}}
  
==См. также==
+
==EEEE==
* [[Производящая функция]]
 
* [[Арифметические действия с формальными степенными рядами]]
 
  
== Источники информации ==  
+
==EEEE==
* [https://www.mccme.ru/free-books/lando/lando-genfunc.pdf Лекции о производящих функциях]
 
* [https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%BF%D1%80%D0%B5%D1%80%D1%8B%D0%B2%D0%BD%D0%B0%D1%8F_%D0%B4%D1%80%D0%BE%D0%B1%D1%8C Непрерывная дробь]
 
* Демидович Б. П., Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М.: Физматлит, 1963. — С. 53—73. — 660 с.
 
  
[[Категория: Дискретная математика и алгоритмы]]
+
==EEEE==
[[Категория: Производящая функция]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)