Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа — различия между версиями
Senya (обсуждение | вклад) (Новая страница: «{{Теорема |statement= Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t),\, \psi(0) = 1</tex>…») (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 34 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t)\,</tex> связаны между собой уравнением Лагранжа <tex>\varphi(s) = s \cdot \psi \cdot (\varphi(s))</tex>. Мы хотим выяснить, как связаны между собой их радиусы сходимости. | ||
+ | |||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t),\, \psi(0) = 1</tex> | + | Пусть две [[Производящая функция#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>\varphi(s) = s\psi(\varphi(s))</tex>. Пусть <tex>r > 0</tex> — радиус сходимости ряда <tex>\varphi,</tex> причем числовой ряд <tex>\varphi(r)</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 год] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Производящая функция]] |
Текущая версия на 19:19, 4 сентября 2022
Пусть две производящие функции
и связаны между собой уравнением Лагранжа . Мы хотим выяснить, как связаны между собой их радиусы сходимости.Теорема: |
Пусть две производящие функции и с неотрицательными коэффицентами связаны между собой уравнением Лагранжа . Пусть — радиус сходимости ряда причем числовой ряд сходится. Пусть радиус сходимости ряда равен . Тогда
если числовой ряд также сходится. Замечание Требование неотрицательности коэффициентов рядов естественно, если мы рассматриваем производящие функции для языков. В этом случае естественно также ожидать, что радиус сходимости производящего ряда для числа неприводимых слов больше радиуса сходимости производящего ряда для числа всех слов в языке (последняя последовательность растет быстрее последовательности чисел неприводимых слов). |
Доказательство: |
Докажем, что ряд сходится абсолютно в любой точке . Поскольку функция монотонна и непрерывна на отрезке существует точка , такая, что . Поэтому для любой частичной суммы ряда где последнее неравенство следует из предыдущего замечания. Первое утверждение теоремы доказано.
Последний предел существует и, по условию теоремы, положителен. Поэтому функция обратима в окрестности точки что, в свою очередь, противоречит условиям теоремы. |
Отметим, что производящий ряд для чисел Каталана сходится при так как числа Каталана имеют асимптотику а ряд сходится. С другой стороны, коэффиценты производной имеют асимптотику и поэтому ряд расходится. В результате теорема в полном объеме к функции Каталана неприменима, а второе утверждение оказывается неверным.