89
правок
Изменения
Новая страница: «'''Обращение Лагранжа''' (англ. ''Lagrange Inversion'') позволяет получить формулу для коэффициентов…»
'''Обращение Лагранжа''' (англ. ''Lagrange Inversion'') позволяет получить формулу для коэффициентов функции <tex>f(x)</tex>, являющейся решением уравнения <tex>f(x) = xG(f(x))</tex>.
== Формула обращения Лагранжа ==
{{Теорема
| id = thLagrangeInversion
| about = об обращении Лагранжа
| statement = Пусть <tex>f(s) = \sum\limits_{n=1}^{\infty} {f_n s^n}</tex>.
Тогда уравнение <tex>T(z) = z f(T(z))</tex> имеет единственное решение <tex>T(z) = \sum\limits_{n=1}^{\infty} {t_n z^n}</tex>, где <tex>t_n = \dfrac{1}{n} [s ^ {n - 1}] (f(s))^n</tex>.
| proof = Во-первых, заметим, что <tex>T(z)</tex> {{ --- }} аналитическая функция, а значит она является аналитической в точке <tex>0</tex> и конформно отображает окрестность <tex>0</tex> в другую окрестность <tex>0</tex>.
<tex>T'(z) = \sum\limits_{n = 0}^{\infty}{ n t_n z ^ {n - 1} }</tex>, отсюда следует, что <tex>n t_n = [z ^ {n - 1} ]T'(z)</tex>.
Воспользуемся интегральной формулой Коши <ref>[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Wikipedia {{---}} Интегральная формула Коши]</ref>:
<tex>n t_n = \dfrac{1}{2i\pi} \int\limits_{0+} {\dfrac{T'(z)}{z ^ n} dz} = \dfrac{1}{2i\pi} \int\limits_{0+} {\dfrac{ds}{(s / f(s))^n}}= [s^{n-1}](f(s))^n</tex>
Отсюда следует искомое: <tex>t_n= \dfrac{1}{n}[s ^ {n - 1}] (f(s))^n</tex>
}}
== Примеры ==
=== Числа Каталана ===
<tex>C(z) = z\dfrac{1}{1 - C(z)}</tex>, соответствующая функция <tex>f(s)</tex> равна <tex>\dfrac{1}{1 - s}</tex>.
По формуле обращения Лагранжа: <tex>c_n = \dfrac{1}{n} [s ^ {n - 1} ] (\dfrac{1}{1 - s})^n = \dfrac {1}{n} [s^{n - 1}] (1 + \dfrac{-n}{1}(-s) + \dfrac{(-n)(-n-1)} {1 \cdot 2} (-s)^2 + \ldots + \dfrac{(-n)(-n-1)\ldots (-n - (n - 1))}{1 \cdot 2 \cdot \ldots \cdot (n - 1)} (-s)^{n - 1} + \ldots) =</tex>
<tex>= \dfrac{1}{n} \cdot \dfrac{(2n - 2)(2n - 1) \ldots n}{1 \cdot 2 \cdot \ldots \cdot n} = \dfrac{\dbinom{2n - 2}{n - 1}}{n}</tex>
=== Формула Кэли ===
Вычислим число помеченных подвешенных деревьев без порядка на детях с помощью формулы обращения Лагранжа:
<tex>T(z) = z \cdot Set(T) = z \cdot exp(T(z))</tex>, <tex>f(s) = e^s</tex>.
Воспользуемся формулой обращения Лагранжа:
<tex>\dfrac{t_n}{n!} = \dfrac{1}{n} \cdot [s^{n - 1}] e^{ns} = \dfrac{1}{n} \cdot (1 + \dfrac{1}{1!}\cdot ns + \dfrac{1}{2!}\cdot (ns)^2 + \ldots + \dfrac{1}{(n - 1)!}\cdot (ns)^{n-1} + \ldots) = \dfrac{1}{n} \cdot \dfrac{1}{(n - 1)!} \cdot n^{n-1} = \dfrac {n ^ {n - 1}}{n!}</tex>
Из этого следует, что <tex>t_n = n^{n- 1}</tex>
== См. также ==
* [[Производящая функция]]
== Примечания ==
<references/>
== Источники информации ==
* Philippe Flajolet, Robert Sedgewick. «Analytic Combinatorics» {{---}} «Cambridge University Press», 2009 г. {{---}} 732-733 стр. {{---}} ISBN 978-0521898065
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчет числа объектов]]
== Формула обращения Лагранжа ==
{{Теорема
| id = thLagrangeInversion
| about = об обращении Лагранжа
| statement = Пусть <tex>f(s) = \sum\limits_{n=1}^{\infty} {f_n s^n}</tex>.
Тогда уравнение <tex>T(z) = z f(T(z))</tex> имеет единственное решение <tex>T(z) = \sum\limits_{n=1}^{\infty} {t_n z^n}</tex>, где <tex>t_n = \dfrac{1}{n} [s ^ {n - 1}] (f(s))^n</tex>.
| proof = Во-первых, заметим, что <tex>T(z)</tex> {{ --- }} аналитическая функция, а значит она является аналитической в точке <tex>0</tex> и конформно отображает окрестность <tex>0</tex> в другую окрестность <tex>0</tex>.
<tex>T'(z) = \sum\limits_{n = 0}^{\infty}{ n t_n z ^ {n - 1} }</tex>, отсюда следует, что <tex>n t_n = [z ^ {n - 1} ]T'(z)</tex>.
Воспользуемся интегральной формулой Коши <ref>[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 Wikipedia {{---}} Интегральная формула Коши]</ref>:
<tex>n t_n = \dfrac{1}{2i\pi} \int\limits_{0+} {\dfrac{T'(z)}{z ^ n} dz} = \dfrac{1}{2i\pi} \int\limits_{0+} {\dfrac{ds}{(s / f(s))^n}}= [s^{n-1}](f(s))^n</tex>
Отсюда следует искомое: <tex>t_n= \dfrac{1}{n}[s ^ {n - 1}] (f(s))^n</tex>
}}
== Примеры ==
=== Числа Каталана ===
<tex>C(z) = z\dfrac{1}{1 - C(z)}</tex>, соответствующая функция <tex>f(s)</tex> равна <tex>\dfrac{1}{1 - s}</tex>.
По формуле обращения Лагранжа: <tex>c_n = \dfrac{1}{n} [s ^ {n - 1} ] (\dfrac{1}{1 - s})^n = \dfrac {1}{n} [s^{n - 1}] (1 + \dfrac{-n}{1}(-s) + \dfrac{(-n)(-n-1)} {1 \cdot 2} (-s)^2 + \ldots + \dfrac{(-n)(-n-1)\ldots (-n - (n - 1))}{1 \cdot 2 \cdot \ldots \cdot (n - 1)} (-s)^{n - 1} + \ldots) =</tex>
<tex>= \dfrac{1}{n} \cdot \dfrac{(2n - 2)(2n - 1) \ldots n}{1 \cdot 2 \cdot \ldots \cdot n} = \dfrac{\dbinom{2n - 2}{n - 1}}{n}</tex>
=== Формула Кэли ===
Вычислим число помеченных подвешенных деревьев без порядка на детях с помощью формулы обращения Лагранжа:
<tex>T(z) = z \cdot Set(T) = z \cdot exp(T(z))</tex>, <tex>f(s) = e^s</tex>.
Воспользуемся формулой обращения Лагранжа:
<tex>\dfrac{t_n}{n!} = \dfrac{1}{n} \cdot [s^{n - 1}] e^{ns} = \dfrac{1}{n} \cdot (1 + \dfrac{1}{1!}\cdot ns + \dfrac{1}{2!}\cdot (ns)^2 + \ldots + \dfrac{1}{(n - 1)!}\cdot (ns)^{n-1} + \ldots) = \dfrac{1}{n} \cdot \dfrac{1}{(n - 1)!} \cdot n^{n-1} = \dfrac {n ^ {n - 1}}{n!}</tex>
Из этого следует, что <tex>t_n = n^{n- 1}</tex>
== См. также ==
* [[Производящая функция]]
== Примечания ==
<references/>
== Источники информации ==
* Philippe Flajolet, Robert Sedgewick. «Analytic Combinatorics» {{---}} «Cambridge University Press», 2009 г. {{---}} 732-733 стр. {{---}} ISBN 978-0521898065
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчет числа объектов]]
