Обращение Лагранжа (англ. Lagrange Inversion) позволяет получить формулу для коэффициентов функции [math]f(x)[/math], являющейся решением уравнения [math]f(x) = xG(f(x))[/math].
Формула обращения Лагранжа
| Теорема (об обращении Лагранжа): |
Пусть [math]f(s) = \sum\limits_{n=1}^{\infty} {f_n s^n}[/math].
Тогда уравнение [math]T(z) = z f(T(z))[/math] имеет единственное решение [math]T(z) = \sum\limits_{n=1}^{\infty} {t_n z^n}[/math], где [math]t_n = \dfrac{1}{n} [s ^ {n - 1}] (f(s))^n[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Во-первых, заметим, что [math]T(z)[/math] — аналитическая функция, а значит она является аналитической в точке [math]0[/math] и конформно отображает окрестность [math]0[/math] в другую окрестность [math]0[/math].
[math]T'(z) = \sum\limits_{n = 0}^{\infty}{ n t_n z ^ {n - 1} }[/math], отсюда следует, что [math]n t_n = [z ^ {n - 1} ]T'(z)[/math].
Воспользуемся интегральной формулой Коши [1]:
[math]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[/math]
Отсюда следует искомое: [math]t_n= \dfrac{1}{n}[s ^ {n - 1}] (f(s))^n[/math] |
| [math]\triangleleft[/math] |
Примеры
Числа Каталана
[math]C(z) = z\dfrac{1}{1 - C(z)}[/math], соответствующая функция [math]f(s)[/math] равна [math]\dfrac{1}{1 - s}[/math].
По формуле обращения Лагранжа: [math]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) =[/math]
[math]= \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}[/math]
Формула Кэли
Вычислим число помеченных подвешенных деревьев без порядка на детях с помощью формулы обращения Лагранжа:
[math]T(z) = z \cdot Set(T) = z \cdot exp(T(z))[/math], [math]f(s) = e^s[/math].
Воспользуемся формулой обращения Лагранжа:
[math]\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!}[/math]
Из этого следует, что [math]t_n = n^{n- 1}[/math]
См. также
Примечания
Источники информации
- Philippe Flajolet, Robert Sedgewick. «Analytic Combinatorics» — «Cambridge University Press», 2009 г. — 732-733 стр. — ISBN 978-0521898065
