Lagrangesche Inversionsformel

Grundidee und Aussage

Die Lagrangesche Inversionsformel entwickelt zu einer gegebenen analytischen Funktion die Potenzreihe ihrer Umkehrfunktion. Sie ist besonders nützlich, wenn eine Gleichung z = f(w) nicht direkt nach w aufgelöst werden kann, aber f in einer Umgebung eines Punktes a analytisch ist und f′(a) ≠ 0 gilt.

Unter diesen Voraussetzungen lässt sich die Gleichung formal nach w auflösen. Für die Umkehrfunktion w = g(z) gilt:

g(z) = a + Σₙ₌₁∞ gₙ (z − f(a))ⁿ/n!,

gₙ = lim₍w→a₎ [dⁿ⁻¹/dwⁿ⁻¹ ((w − a)/(f(w) − f(a)))ⁿ].

Die entstehende Potenzreihe besitzt einen von 0 verschiedenen Konvergenzradius. Sie stellt daher in einer Umgebung von z = f(a) eine analytische Funktion dar und invertiert f dort als formale Potenzreihe. Die Formel kann außerdem auf H(g(z)) für eine beliebige formale Potenzreihe H erweitert werden. In vielen Fällen ist auch eine Verallgemeinerung für f′(a) = 0 möglich; dann kann die Umkehrfunktion mehrwertig sein.

Koeffizienten der Umkehrreihe

Sind f und g als formale Potenzreihen mit b₀ = 0 und b₁ ≠ 0 gegeben,

f(w) = Σₖ₌₀∞ bₖ wᵏ/k! und g(z) = Σₖ₌₀∞ cₖ zᵏ/k!,

können die Koeffizienten von g mithilfe von Bell-Polynomen bestimmt werden. Für n ≥ 2 gilt:

cₙ = 1/b₁ⁿ · Σₖ₌₁ⁿ⁻¹ (−1)ᵏ n⁽ᵏ⁾ Bₙ₋₁,ₖ(a₁, a₂, …, aₙ₋ₖ),

wobei aₖ = bₖ₊₁/((k+1)b₁), c₁ = 1/b₁ und n⁽ᵏ⁾ = n(n+1)⋯(n+k−1) die steigende Faktorielle bezeichnet. Die Bell-Polynome bündeln dabei die Kombinationen, die beim formalen Invertieren der Potenzreihe entstehen.

Formale Umkehrung über Ringen

Die explizite Konstruktion gilt allgemeiner als für analytische Funktionen: Sei R ein Ring mit Eins und A(X) = Σₖ₌₁∞ aₖXᵏ eine formale Potenzreihe aus R[[X]]. Eine formale kompositionelle Umkehrfunktion B(X) = Σₙ₌₁∞ bₙXⁿ existiert genau dann, wenn a₁ = A′(0) in R invertierbar, also eine Einheit, ist.

Zur Vereinfachung setzt man C(Y) = A(a₁⁻¹Y) = Y + Σₖ₌₂∞ cₖYᵏ mit cₖ = a₁⁻ᵏaₖ. Die inverse Reihe wird als D(Y) = Y + Σₙ₌₂∞ dₙYⁿ geschrieben. Aus C(D(Y)) = Y folgt

D(Y) = Y − Σₖ₌₂∞ cₖD(Y)ᵏ.

Mit dem Koeffizientenextraktionsoperator [Yⁿ] ergibt sich für n ≥ 2:

dₙ = −[Yⁿ] Σₖ₌₂∞ cₖD(Y)ᵏ.

Diese Rekursion bestimmt dₙ schrittweise, da auf der rechten Seite nur Koeffizienten dⱼ mit j < n vorkommen. Die ersten Koeffizienten lauten:

d₁ = 1, d₂ = −c₂, d₃ = −c₃ + 2c₂², d₄ = −c₄ + 5c₃c₂ − 5c₂³, d₅ = −c₅ + 6c₄c₂ + 3c₃² − 21c₃c₂² + 14c₂⁴.

Eine geschlossene Darstellung erhält man durch Summation über alle nichtnegativen ganzen Zahlen i₂, i₃, … mit Σᵥ₌₂∞(ν−1)iᵥ = n−1:

dₙ = Σ (−1)^(Σᵥ iᵥ) · (n−1+Σᵥ iᵥ)!/(n! · ∏ᵥ iᵥ!) · ∏ᵥ cᵥⁱᵥ.

Da diese Rekursion nur Additionen und Multiplikationen verwendet, sind die dₙ ganzzahlige Polynome in den cₖ. Sie gilt deshalb über kommutativen unitären Ringen unabhängig von deren Charakteristik. Mit D(X) = a₁B(X) folgt B(X) = a₁⁻¹D(X); somit sind bₖ = a₁⁻¹dₖ ganzzahlige Polynome in a₁⁻¹ und den aₙ für n ≥ 2.

Formel von Lagrange-Bürmann

Ein wichtiger Sonderfall entsteht bei f(w) = w/φ(w), wobei φ analytisch ist und φ(0) ≠ 0. Für a = 0 gilt f(0) = 0. Ist g(z) = f⁻¹(z), dann lautet die Koeffizientenformel

[zⁿ]g(z) = 1/n · [wⁿ⁻¹]φ(w)ⁿ.

Der Operator [wʳ] bezeichnet den Koeffizienten des Terms wʳ in der rechtsstehenden formalen Potenzreihe. Die Formel erlaubt damit, die Koeffizienten der Umkehrfunktion durch eine einfache Koeffizientenextraktion aus φ(w)ⁿ zu bestimmen.

Die Verallgemeinerung auf eine beliebige analytische Funktion H lautet:

[zⁿ]H(g(z)) = 1/n · wⁿ⁻¹.

Falls H′(w) schwierig zu berechnen ist, kann die Formel auch in der Form

[zⁿ]H(g(z)) = [wⁿ]H(w)φ(w)ⁿ⁻¹(φ(w) − wφ′(w))

geschrieben werden. Sie verwendet dann φ′(w) anstelle von H′(w).

Anwendungen: W-Funktion und Binärbäume

Die Lambertsche W-Funktion ist durch W(z)e^{W(z)} = z definiert. Sie ist also die Umkehrfunktion von f(w) = we^w. Für die Taylorreihe um z = 0 liefert die Inversionsformel

W(z) = Σₙ₌₁∞ (−n)ⁿ⁻¹ zⁿ/n!

und damit

W(z) = z − z² + 3/2 z³ − 8/3 z⁴ + 125/24 z⁵ − ….

Der Konvergenzradius dieser Reihe ist e⁻¹. Eine Reihe mit größerem Konvergenzradius erhält man, indem man f(z) = W(e^z) − 1 betrachtet. Diese Funktion erfüllt 1 + f(z) + ln(1 + f(z)) = z. Durch Invertieren der Potenzreihe von z + ln(1+z) erhält man:

W(e^{1+z}) = 1 + z/2 + z²/16 − z³/192 − z⁴/3072 + 13z⁵/61440 − 47z⁶/1474560 − 73z⁷/41287680 + 2447z⁸/1321205760 + O(z⁹).

Durch die Substitution z = ln x − 1 kann daraus W(x) gewonnen werden. Für z = −1 folgt beispielsweise W(1) = 0,567143… .

Eine kombinatorische Anwendung betrifft Binärbäume mit NIL-Knoten. Ein solcher Baum ist entweder ein NIL-Knoten oder ein Knoten mit zwei Teilbäumen. Sei Bₙ die Anzahl der Bäume mit n echten Knoten und B(z) = Σₙ₌₀∞ Bₙzⁿ die erzeugende Funktion. Die Zerlegung an der Wurzel führt zu

B(z) = 1 + zB(z)².

Setzt man C(z) = B(z) − 1, erhält man C(z) = z(C(z)+1)². Die Lagrange-Bürmann-Formel mit φ(w) = (w+1)² ergibt für n ≥ 1:

Bₙ = [zⁿ]C(z) = 1/n · wⁿ⁻¹²ⁿ = 1/n · binom(2n,n−1) = 1/(n+1) · binom(2n,n).

Diese Zahlen sind die n-ten Catalan-Zahlen.