Просмотр исходного текста страницы Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа

Пусть две производящие функции <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</tex>. Тогда
<tex>1. \ \rho \geqslant \varphi(r),</tex>

<tex>2. \ \rho = \varphi(r),</tex> если числовой ряд <tex>\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 год]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящая функция]]