Lagrangian inversion formula

The Lagrangian inversion formula in mathematics develops the power series of the inverse function for a given analytical function .

The theorem

Given an equation

${\displaystyle z=f(w)}$

with a function analytic at the point and . Then it is possible to invert, i.e. to solve the equation in the form of a formal power series : ${\displaystyle a}$ ${\displaystyle f}$ ${\displaystyle f^{\prime }(a)\neq 0}$ ${\displaystyle f}$ ${\displaystyle w}$ ${\displaystyle w=g(z)}$

${\displaystyle g(z)=a+\sum _{n=1}^{\infty }g_{n}{\frac {(z-f(a))^{n}}{n!}}}$

With

${\displaystyle g_{n}=\lim _{w\to a}\left[{\frac {d^{n-1}}{dw^{n-1}}}\left({\frac {w-a}{f(w)-f(a)}}\right)^{n}\right].}$

The power series has a radius of convergence other than 0 , i.e. H. it is an analytic function in a neighborhood of the point . The formula inverts as a formal power series in . It can be extended to a formula for with any formal power series and generalized for the case (then a "multi-valued" function). ${\displaystyle g(z)}$ ${\displaystyle z=f(a)}$ ${\displaystyle f(w)}$ ${\displaystyle z}$ ${\displaystyle H(g(z))}$ ${\displaystyle H}$ ${\displaystyle f^{\prime }(a)=0}$

The theorem was proven by Lagrange and generalized by Hans Heinrich Bürmann , both in the late 18th century. There are further developments in the direction of complex analysis and curve integrals .

Taylor series

The above formula does not directly give the coefficients of the formal inverse function expressed in the coefficients of for a formal power series . Can one use the functions and as a formal power series ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle g}$

${\displaystyle f(w)=\sum _{k=0}^{\infty }b_{k}{\frac {w^{k}}{k!}}\qquad \mathrm {und} \qquad g(z)=\sum _{k=0}^{\infty }c_{k}{\frac {z^{k}}{k!}}}$

with and , then the coefficients of the inverses can be given using Bell polynomials : ${\displaystyle b_{0}=0}$ ${\displaystyle b_{1}\neq 0}$ ${\displaystyle g}$

${\displaystyle c_{n}={\frac {1}{b_{1}^{n}}}\sum _{k=1}^{n-1}(-1)^{k}n^{(k)}B_{n-1,k}(a_{1},a_{2},\ldots ,a_{n-k})\qquad (n\geq 2)}$ ,

with   and     as an increasing factorial . ${\displaystyle a_{k}={\frac {b_{k+1}}{(k+1)b_{1}}},}$    ${\displaystyle c_{1}={\frac {1}{b_{1}}}}$ ${\displaystyle n^{(k)}=n(n+1)\cdots (n+k-1)}$

Explicit formula

The following explicit formula is valid not only for analytic functions (over or ), but for all formal power series over a ring with 1. Is namely ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} }$ ${\displaystyle R}$

${\displaystyle A(X)=\sum _{k=1}^{\infty }a_{k}X^{k}\in R[[X]]}$

a formal power series, then and only then has a (formal) inverse function (a formal compositional inverse) ${\displaystyle A}$

${\displaystyle B(X)=\sum _{n=1}^{\infty }b_{n}X^{n}\in R[[X]]}$ ,

if invertible (a unit ) is in . ${\displaystyle a_{1}}$ ${\displaystyle R}$

The simpler accounting matters, we substitute through and write ${\displaystyle X}$ ${\displaystyle a_{1}^{-1}Y}$

${\displaystyle C(Y):=A(a_{1}^{-1}Y)=:Y+\sum _{k=2}^{\infty }c_{k}Y^{k}}$

with for . ${\displaystyle c_{k}:=a_{1}^{-k}a_{k}}$ ${\displaystyle k\geq 2}$

The corresponding formal inverse function is assumed

${\displaystyle D(Y):=Y+\sum _{n=2}^{\infty }d_{n}Y^{n}}$,

so that is. The coefficients of can be determined by comparing the coefficients in the equation ${\displaystyle C{\bigl (}D(Y){\bigr )}=D(Y)+\sum _{k=2}^{\infty }c_{k}{\bigl (}D(Y){\bigr )}^{k}=Y}$ ${\displaystyle D}$

${\displaystyle D(Y)=Y-\sum _{k=2}^{\infty }c_{k}{\bigl (}D(Y){\bigr )}^{k}}$

for immediately too ${\displaystyle n\geq 2}$

${\displaystyle {\begin{array}{llll}d_{n}\!\!\!\!&=-\left[Y^{n}\right]&\displaystyle \sum _{k=2}^{\infty }c_{k}{\bigl (}D(Y){\bigr )}^{k}\end{array}}}$

${\displaystyle \left.{\begin{array}{llllrr}\;&=-\left[Y^{n}\right]&{\Bigl (}&c_{2}(1\;Y^{1}&+\,d_{2}Y^{2}&+\dotsb +&d_{n-1}Y^{n-1})^{2}\\&&+&c_{3}&(1\;Y^{1}&+\dotsb +&d_{n-2}Y^{n-2})^{3}\\&&\,\vdots \\&&+&c_{n-1}&&(1\;Y^{1}+&d_{2}\,Y^{2})^{n-1}\\&&+&c_{n}&&&(1\;Y^{1})^{n}\;\;\;\\&&{\Bigr )}\end{array}}\qquad \qquad \right\rbrace {\text{ (RF)}}}$

calculate with the operator for coefficient extraction . Since the formula only contains coefficients with indices on its right-hand side , it represents a recursive specification of the . ${\displaystyle \left[Y^{n}\right]}$ ${\displaystyle {\text{(RF)}}}$ ${\displaystyle d_{j}}$ ${\displaystyle j<n}$ ${\displaystyle d_{n}(n\geq 2)}$

comment

Since the formula only contains ring operations (only additions and multiplications and no division), the coefficients are integer polynomials in the - with the result that over all commutative unitary rings regardless of the characteristic - and thus to a certain extent universally - is valid. ${\displaystyle {\text{(RF)}}}$ ${\displaystyle d_{n}}$ ${\displaystyle c_{k}}$ ${\displaystyle {\text{(RF)}}}$

A derivation of the explicit resolution

${\displaystyle d_{n}}$	${\displaystyle =}$	${\displaystyle \sum (-1)^{i_{2}+i_{3}+\cdots }}$	${\displaystyle {\frac {(n-1+i_{2}+i_{3}+\cdots )!}{n!\;\;i_{2}!\,i_{3}!\,\cdots }}}$	${\displaystyle c_{2}^{\,i_{2}}c_{3}^{\,i_{3}}\cdots }$
	${\displaystyle =}$	${\displaystyle \sum (-1)^{\sum _{\nu =2}^{\infty }i_{\nu }}}$	${\displaystyle {\frac {(n-1+\sum _{\nu =2}^{\infty }i_{\nu })!}{\;n!\quad \prod _{\nu =2}^{\infty }i_{\nu }!}}}$	${\displaystyle \prod _{\nu =2}^{\infty }c_{\nu }^{\,i_{\nu }}}$ ,

in which all combinations have to     be added up can be found in Morse and Feshbach. ${\displaystyle i_{2},i_{3},\ldots \in \mathbb {N} }$ ${\displaystyle 1\,i_{2}+2\,i_{3}+\cdots =\textstyle \sum _{\nu =2}^{\infty }(\nu -1)\,i_{\nu }=n-1}$

The first 7 coefficients of are: ${\displaystyle D}$

${\displaystyle d_{1}}$	${\displaystyle =\;1}$
${\displaystyle d_{2}}$	${\displaystyle =\,-c_{2}}$
${\displaystyle d_{3}}$	${\displaystyle =\,-c_{3}}$	${\displaystyle +2\,c_{2}^{\,2}}$
${\displaystyle d_{4}}$	${\displaystyle =\,-c_{4}}$	${\displaystyle +5\,c_{3}c_{2}}$	${\displaystyle -5\,c_{2}^{\,3}}$
${\displaystyle d_{5}}$	${\displaystyle =\,-c_{5}}$	${\displaystyle +6\,c_{4}c_{2}}$	${\displaystyle +3\,c_{3}^{\,2}}$	${\displaystyle -21\,c_{3}c_{2}^{\,2}}$	${\displaystyle +14\,c_{2}^{\,4}}$
${\displaystyle d_{6}}$	${\displaystyle =\,-c_{6}}$	${\displaystyle +7\,c_{5}c_{2}}$	${\displaystyle +7\,c_{4}c_{3}}$	${\displaystyle -28\,c_{4}c_{2}^{\,2}}$	${\displaystyle -28\,c_{3}^{\,2}c_{2}}$	${\displaystyle +84\,c_{3}c_{2}^{\,3}}$	${\displaystyle -42\,c_{2}^{\,5}}$
${\displaystyle d_{7}}$	${\displaystyle =\,-c_{7}}$	${\displaystyle +8\,c_{6}c_{2}}$	${\displaystyle +8\,c_{5}c_{3}}$	${\displaystyle -36\,c_{5}c_{2}^{\,2}}$	${\displaystyle +4\,c_{4}^{\,2}}$	${\displaystyle -72\,c_{4}c_{3}c_{2}}$	${\displaystyle +120\,c_{4}c_{2}^{\,3}}$	${\displaystyle -12\,c_{3}^{\,3}}$	${\displaystyle +180\,c_{3}^{\,2}c_{2}^{\,2}}$	${\displaystyle -330\,c_{3}c_{2}^{\,4}}$	${\displaystyle +132\,c_{2}^{\,6}}$

The monomials are lexicographically arranged in descending order in the lines , i.e. H. occurs occurs occurs occurs . The (integer) coefficients of these polynomials are compiled in this arrangement in the sequence A304462 in OEIS . The sequence A000041 in OEIS contains the number of monomials in the -th line (= number of partitions in a -element set). ${\displaystyle c_{3}^{\,2}=c_{3}c_{3}}$ ${\displaystyle c_{3}c_{2}}$ ${\displaystyle c_{3}}$ ${\displaystyle c_{2}^{\,2}}$ ${\displaystyle n}$ ${\displaystyle n}$

With the substitution results ${\displaystyle D(X):=a_{1}\,B(X)}$

${\displaystyle X=C{\bigl (}D(X){\bigr )}=A{\bigl (}a_{1}^{-1}D(X){\bigr )}=A{\bigl (}B(X){\bigr )}}$ ,

so that the inverse function of is sought . She has the coefficients ${\displaystyle B(X)=a_{1}^{-1}D(X)}$ ${\displaystyle A(X)}$

${\displaystyle b_{k}=a_{1}^{-1}d_{k}}$ ,

which are all integer polynomials in and den . ${\displaystyle a_{1}^{-1}}$ ${\displaystyle a_{n}(n\geq 2)}$

Formula by Lagrange-Bürmann

A special case of the Lagrangian inversion formula, which is used in combinatorics , is valid for with analytical and by setting then becomes is for the inverse ${\displaystyle f(w)=w/\phi (w)}$ ${\displaystyle \phi (w)}$ ${\displaystyle \phi (0)\neq 0.}$ ${\displaystyle a=0}$ ${\displaystyle f(a)=f(0)=0.}$ ${\displaystyle g(z):=f^{-1}(z)}$

${\displaystyle {\begin{aligned}g(z)&=\sum _{n=1}^{\infty }\left(\lim _{w\to 0}\left({\frac {\operatorname {d} ^{n-1}}{\operatorname {d} w^{n-1}}}\left({\frac {w}{w/\phi (w)}}\right)^{n}\right){\frac {z^{n}}{n!}}\right)\\&=\sum _{n=1}^{\infty }{\frac {1}{n}}\left({\frac {1}{(n-1)!}}\lim _{w\to 0}\left({\frac {\operatorname {d} ^{n-1}}{\operatorname {d} w^{n-1}}}\phi (w)^{n}\right)\right)z^{n},\end{aligned}}}$

which also as

${\displaystyle [z^{n}]g(z)={\frac {1}{n}}[w^{n-1}]\phi (w)^{n}}$

can be written with the operator that extracts the coefficient of the term in the formal power series to the right of it . ${\displaystyle [w^{r}]}$ ${\displaystyle w^{r}}$ ${\displaystyle w}$

A useful generalization is known as the Lagrange-Bürmann formula :

${\displaystyle [z^{n}]H(g(z))={\frac {1}{n}}[w^{n-1}]{\bigl (}H^{\prime }(w)\phi (w)^{n}{\bigr )}}$

with any analytic function . ${\displaystyle H}$

The derivation can take a very complicated form when it can be replaced by order ${\displaystyle H^{\prime }(w)}$ ${\displaystyle H(w)(1-\phi ^{\prime }(w)/\phi (w))}$

${\displaystyle [z^{n}]H(g(z))=[w^{n}]H(w)\phi (w)^{n-1}{\bigl (}\phi (w)-w\phi ^{\prime }(w){\bigr )}}$

to get which refers to instead of . ${\displaystyle \phi ^{\prime }(w)}$ ${\displaystyle H^{\prime }(w)}$

Applications

The Lambert W function

→ Main article : Lambert W function

The Lambertian W function is that given by the implicit equation

${\displaystyle W(z)e^{W(z)}=z}$

defined function . ${\displaystyle W(z)}$

Using the Lagrange inversion formula is calculated for the Taylor series of the point due and first ${\displaystyle W(z)}$ ${\displaystyle z=0}$ ${\displaystyle f(w)=w\mathrm {e} ^{w}}$ ${\displaystyle a=b=0}$

${\displaystyle {\frac {\operatorname {d} ^{n}}{\operatorname {d} x^{n}}}\ \mathrm {e} ^{\alpha \,x}\,=\,\alpha ^{n}\,\mathrm {e} ^{\alpha \,x}}$ ,

from what

${\displaystyle W(z)=\sum _{n=1}^{\infty }\lim _{w\to 0}\left({\frac {\operatorname {d} ^{\,n-1}}{\operatorname {d} w^{\,n-1}}}\ \mathrm {e} ^{-nw}\right){\frac {z^{n}}{n!}}\,=\,\sum _{n=1}^{\infty }(-n)^{n-1}\,{\frac {z^{n}}{n!}}=x-x^{2}+{\frac {3}{2}}x^{3}-{\frac {8}{3}}x^{4}+{\frac {125}{24}}x^{5}-\dotsb .}$

The radius of convergence of this series is . ${\displaystyle \mathrm {e} ^{-1}}$

A larger radius of convergence is obtained in a similar way:
The function satisfies the equation ${\displaystyle f(z)=W(e^{z})-1\,}$

${\displaystyle 1+f(z)+\ln(1+f(z))=z}$ .

If one expands into a power series and inverts it, one obtains for  : ${\displaystyle z+\ln(1+z)\,}$ ${\displaystyle f(z+1)=W(e^{z+1})-1}$

${\displaystyle W(e^{1+z})=1+{\frac {z}{2}}+{\frac {z^{2}}{16}}-{\frac {z^{3}}{192}}-{\frac {z^{4}}{3072}}+{\frac {13z^{5}}{61440}}-{\frac {47z^{6}}{1474560}}-{\frac {73z^{7}}{41287680}}+{\frac {2447z^{8}}{1321205760}}+{\mathcal {O}}(x^{9}).}$

One can deduce from this by substituting with in this series. E.g. can be found at . ${\displaystyle W(x)}$ ${\displaystyle \ln x-1}$ ${\displaystyle z}$ ${\displaystyle W(1)=0{,}567143\dotsc }$ ${\displaystyle z=-1}$

Binary trees

Let be the set of binary trees with NIL nodes . A tree from is either a NIL node or a node with two subtrees. ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}}$

The number of such binary trees with (real) nodes is denoted by. ${\displaystyle n}$ ${\displaystyle B_{n}}$

Removing the root splits the binary tree into two smaller subtrees. From this it follows for the generating function : ${\displaystyle B(z)=\sum _{n=0}^{\infty }B_{n}z^{n}}$

${\displaystyle B(z)=1+zB(z)^{2}.}$

Well be , and with it . ${\displaystyle C(z)=B(z)-1}$ ${\displaystyle C(z)=z(C(z)+1)^{2}}$

Applying the Lagrangian inversion formula with gives: ${\displaystyle \phi (w)=(w+1)^{2}}$

${\displaystyle B_{n}=[z^{n}]C(z)={\frac {1}{n}}[w^{n-1}](w+1)^{2n}={\frac {1}{n}}{\binom {2n}{n-1}}={\frac {1}{n+1}}{\binom {2n}{n}}.}$

and that is the -th Catalan number . ${\displaystyle n}$

Individual evidence

1. ↑ M. Abramowitz, IA Stegun (Ed.): Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables . Dover, New York 1972, 3.6.6. Lagrange's Expansion, p. 14 ( sfu.ca ).
2. ^ Lagrange, Joseph-Louis: Nouvelle méthode pour résoudre les equations littérales par le moyen des séries . In: Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin . 24, 1770, pp. 251-326.  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.   (Note: Although Lagrange submitted the article in 1768, it was not published before 1770.)
3. ↑ Bürmann, Hans Heinrich, "Essai de calcul fonctionnaire aux constant a ad-libitum," filed in 1796 at the Institut National de France. For a summary of this article see: Hindenburg, Carl Friedrich (Ed.): Archive of pure and applied mathematics . tape 2 . Schäferischen Buchhandlung, Leipzig 1798, attempt of a simplified analysis; an excerpt from an excerpt from Mr. Bürmann, p. 495-499 ( google.com ).
4. ↑ Bürmann, Hans Heinrich, "Formules du développement, de retour et d'integration," submitted to the Institute National de France. Bürmann's manuscript survives in the archives of the École Nationale des Ponts et Chaussées in Paris. (See ms. 1715.)
5. ↑ A report by Joseph-Louis Lagrange and Adrien-Marie Legendre on Bürmann's theorem appears in: "Rapport sur deux mémoires d'analysis du professeur Burmann," Mémoires de l'Institut National des Sciences et Arts: Sciences Mathématiques et Physiques , vol. 2, pp. 13-17 (1799).
6. ↑ Edmund Taylor Whittaker and George Neville Watson . A Course of Modern Analysis . Cambridge University Press; 4th edition (January 2, 1927), pp. 129-130
7. ↑ Eqn (11.43), p. 437, CA Charalambides, Enumerative Combinatorics, Chapman & Hall / CRC, 2002
8. ↑ They converge in the ring of formal power series under the Krull topology there . If or or is another complete ring , then the analytical convergence leads to the formal one, but not the other way around. ${\displaystyle R[[X]]}$
   ${\displaystyle R=\mathbb {R} }$ ${\displaystyle R=\mathbb {C} }$
9. ↑ This condition forces the disappearance of almost all , so it is limited to a finite number of effective summands or to a finite number of effective factors. ${\displaystyle i_{\nu }}$ ${\displaystyle \textstyle \sum _{\nu =2}^{\infty }}$ ${\displaystyle \textstyle \prod _{\nu =2}^{\infty }}$
10. ↑ Morse, PM and Feshbach, H. Methods of Theoretical Physics, Part I . New York: McGraw-Hill, pp. 411-413, 1953 (English). Quoted from Eric W. Weisstein : Series Reversion . In: MathWorld (English).

See also

Formula by Faà di Bruno

Web links

• Eric W. Weisstein : Lagrangian inversion formula . In: MathWorld (English).
• Eric W. Weisstein : Bürmann's Theorem . In: MathWorld (English).
• Eric W. Weisstein : Series Reversion . In: MathWorld (English).
• en: Kepler's equation # Inverse Kepler equation Inversion of the Kepler equation using the Lagrangian inversion formula