Изменения

Перейти к: навигация, поиск
Нет описания правки
Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t)\,</tex> связаны между собой уравнением Лагранжа <tex>\varphi(s) = s \cdot \psi \cdot (\varphi(s))</tex>. Мы хотим выяснить, как связаны между собой их радиусы сходимости.
 
{{Теорема
|statement=
Пусть две [[Производящая функция#main | производящие функции]] <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t),\, \psi(0) = 1\,</tex> с неотрицательными коэффицентами связаны между собой [[Уравнение Лагранжа и теорема Лагранжа#Уравнение Лагранжа и теорема Лагранжа | уравнением Лагранжа]] <tex>\varphi(s) = s\cdot \psi\cdot (\varphi(s))</tex>. Пусть <tex>r > 0\,</tex> — [[Степенные ряды#Радиус сходимости | радиус сходимости ряда]] <tex>\varphi,</tex> причем числовой ряд <tex>\varphi(r)</tex> сходится. Тогда Пусть радиус сходимости ряда <tex>\psi</tex> не меньше равен <tex>\rho = \varphi(r)</tex>. Если числовой ряд Тогда<tex>1. \ \rho \geqslant \varphi '(r),</tex> также сходится, то радиус сходимости ряда  <tex>2. \ \rho = \psivarphi(r),</tex> равен если числовой ряд <tex>\rho = \varphi'(r)</tex>также сходится
'''Замечание'''
Требование неотрицательности коэффициентов рядов естественно, если мы рассматриваем производящие функции для языков. В этом случае естественно также ожидать, что радиус сходимости производящего ряда для числа неприводимых слов больше радиуса сходимости производящего ряда для числа всех слов в языке (последняя последовательность растет быстрее последовательности чисел неприводимых слов).
|proof=
<tex>1. \ </tex>Докажем, что ряд <tex>\psi(s)</tex> сходится абсолютно в любой точке <tex>s,\,\left\vert s \right\vert = q < \rho</tex>.Поскольку функция <tex>\varphi</tex> монотонна и непрерывна на отрезке <tex>[0, r],\,</tex>существует точка <tex>p \in [0, r]</tex>, такая, что <tex>\varphi(p) = q</tex>. Поэтому для любой частичной суммы <tex> \psi_n(s) = \psi_0 + \psi_1 \cdot s + \ldots + \psi_n \cdot s^n</tex> ряда <tex> \psi(s) </tex><tex> \left\vert \psi_n(s) \right\vert \leqslant \psi_n(q) = \psi_n(\varphi(p)) \leqslant \varphi(p),</tex>где последнее неравенство следует из предыдущего замечания.Первое утверждение теоремы доказано.  <tex>2. \ </tex>Перепишем теперь утверждение Лагранжа <tex> \varphi(s) = s \cdot \psi \cdot (\varphi(s)) </tex> в виде <tex> \psi(\lambda) = \dfrac {\lambda} {\varphi^{-1}(\lambda)}. </tex>Функции <tex>\psi(\lambda) </tex> и <tex> \varphi^{-1}(\lambda)</tex> определены и [https://ru.wikipedia.org/wiki/%D0%93%D0%BE%D0%BB%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 голоморфны]внутри круга радиуса <tex>\rho </tex>. Теорема будет доказана, если мы покажем, что функцию <tex>\varphi^{-1}(\lambda)</tex> нельзя продолжить голоморфно ни в какую окрестность точки <tex>\rho</tex>. Предположим, что такое продолжение существует. Тогда <tex> ({\varphi^{-1}}')(\rho) = \lim_{n \to \rho - 0}({\varphi^{-1}} ')(\lambda) = \dfrac {1} {\lim_{t \to r - 0} {\varphi} ' (t)}. </tex> Последний предел существует и, по условию теоремы, положителен.Поэтому функция <tex>\varphi^{-1}</tex>обратима в окрестности точки <tex>\rho,</tex> что, в свою очередь, противоречит условиям теоремы.
}}
Отметим, что производящий ряд для [[Числа Каталана|чисел Каталана]] <tex>Cat(s)</tex>сходится при <tex>s = r = \dfrac{1}{4},</tex> так как числа Каталана имеют асимптотику <tex>4^n \cdot n^{-3/2},</tex> а ряд <tex>\sum_{} n^{-3/2}</tex> сходится. С другой стороны, коэффиценты производной имеют асимптотику <tex>4^n \cdot n^{-1/2},</tex> и поэтому ряд <tex>Cat ' (\dfrac{1}{4})</tex> расходится. В результате теорема в полном объеме к функции Каталана неприменима, а второе утверждение оказывается неверным.
 
== См. также ==
 
* [[Производящая функция]]
* [[Уравнение Лагранжа и теорема Лагранжа]]
* [[Числа Каталана]]
 
== Источники информации ==
* [https://www.mccme.ru/free-books/lando/lando-genfunc.pdf Ландо С.А., Лекции о производящих функциях, 2007 год]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящая функция]]
344
правки

Навигация