Обращение Лагранжа

Обращение Лагранжа (англ. 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]. Воспользуемся интегральной формулой Коши : [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