\input amstex \documentstyle{amsppt} \nologo \NoRunningHeads \magnification1200 \hsize15.6truecm \vsize22.8truecm %\comment \catcode`\@=11 \def\proclaimfont{\sl} \def\remarkheadfont@{\smc} \let\varindent@\indent \def\definition{\let\savedef@\definition \let\definition\relax \add@missing\endproclaim \add@missing\endroster \add@missing\enddefinition \envir@stack\enddefinition \def\definition##1{\restoredef@\definition \penaltyandskip@{-100}\medskipamount {\def\usualspace{{\remarkheadfont@\enspace}}% \varindent@\remarkheadfont@\ignorespaces##1\unskip \frills@{.\remarkheadfont@\enspace}}% \rm \ignorespaces}% \nofrillscheck\definition} \catcode`\@=13 %\endcomment \font\Bf=cmbx12 \font\Rm=cmr12 \def\LL{\leavevmode\setbox0=\hbox{L}\hbox to\wd0{\hss\char'40L}} \def\al{\alpha} \def\be{\beta} \def\ga{\gamma} \def\de{\delta} \def\ep{\varepsilon} \def\ze{\zeta} \def\et{\eta} \def\th{\theta} \def\vt{\vartheta} \def\io{\iota} \def\ka{\kappa} \def\la{\lambda} \def\rh{\rho} \def\si{\sigma} \def\ta{\tau} \def\ph{\varphi} \def\ch{\chi} \def\ps{\psi} \def\om{\omega} \def\Ga{\Gamma} \def\De{\Delta} \def\Th{\Theta} \def\La{\Lambda} \def\Si{\Sigma} \def\Ph{\Phi} \def\Ps{\Psi} \def\Om{\Omega} \def\row#1#2#3{#1_{#2},\ldots,#1_{#3}} \def\rowup#1#2#3{#1^{#2},\ldots,#1^{#3}} \def\x{\times} \def\crf{} %used for crossreferencing, Tex should ignore. \def\rf{} %used for refencing (section-numbers) \def\rfnew{} %used for new-section numbers \def\P{{\Bbb P}} \def\R{{\Bbb R}} \def\X{{\Cal X}} \def\C{{\Bbb C}} \def\Mf{{\Cal Mf}} \def\FM{{\Cal F\Cal M}} \def\F{{\Cal F}} \def\G{{\Cal G}} \def\V{{\Cal V}} \def\T{{\Cal T}} \def\A{{\Cal A}} \def\N{{\Bbb N}} \def\Z{{\Bbb Z}} \def\Q{{\Bbb Q}} \def\ddt{\left.\tfrac \partial{\partial t}\right\vert_0} \def\dd#1{\tfrac \partial{\partial #1}} \def\today{\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\day, \number\year} \def\nmb#1#2{#2} %zum Nummerieren \def\dfrac#1#2{{\displaystyle{#1\over#2}}} \def\tfrac#1#2{{\textstyle{#1\over#2}}} \def\iprod#1#2{\langle#1,#2\rangle} \def\pder#1#2{\frac{\partial #1}{\partial #2}} \def\iint{\int\!\!\int} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\supp{\operatorname{supp}} \def\Df{\operatorname{Df}} \def\dom{\operatorname{dom}} \def\Ker{\operatorname{Ker}} \def\Tr{\operatorname{Tr}} \def\Res{\operatorname{Res}} \def\Aut{\operatorname{Aut}} \def\kgV{\operatorname{kgV}} \def\ggT{\operatorname{ggT}} \def\diam{\operatorname{diam}} \def\Im{\operatorname{Im}} \def\Re{\operatorname{Re}} \def\ord{\operatorname{ord}} \def\rang{\operatorname{rang}} \def\rng{\operatorname{rng}} \def\grd{\operatorname{grd}} \def\inv{\operatorname{inv}} \def\maj{\operatorname{maj}} \def\des{\operatorname{des}} \def\varmaj{\operatorname{\overline{maj}}} \def\vardes{\operatorname{\overline{des}}} \def\pvarmaj{\operatorname{\overline{maj}'}} \def\pmaj{\operatorname{maj'}} \def\ln{\operatorname{ln}} \def\der{\operatorname{der}} \def\Hom{\operatorname{Hom}} \def\tr{\operatorname{tr}} \def\Span{\operatorname{Span}} \def\grad{\operatorname{grad}} \def\div{\operatorname{div}} \def\rot{\operatorname{rot}} \def\Sp{\operatorname{Sp}} \def\sgn{\operatorname{sgn}} \def\liml{\lim\limits} \def\supl{\sup\limits} \def\bigcupl{\bigcup\limits} \def\bigcapl{\bigcap\limits} \def\limsupl{\limsup\limits} \def\liminfl{\liminf\limits} \def\intl{\int\limits} \def\suml{\sum\limits} \def\maxl{\max\limits} \def\minl{\min\limits} \def\prodl{\prod\limits} \def\tg{\operatorname{tan}} \def\ctg{\operatorname{cot}} \def\arctg{\operatorname{arctan}} \def\arccot{\operatorname{arccot}} \def\arcctg{\operatorname{arccot}} \def\tgh{\operatorname{tanh}} \def\ctgh{\operatorname{coth}} \def\arcsinh{\operatorname{arcsinh}} \def\arccosh{\operatorname{arccosh}} \def\arctgh{\operatorname{arctanh}} \def\arcctgh{\operatorname{arccoth}} \def\3{\ss} \def\bx{{\bold x}} \def\bO{{\boldkey 0}} \def\bk{{\bold k}} \def\bn{{\bold n}} \def\e{{\bold e}} \font\BTIT=cmbx10 scaled\magstep3 \font\btit=cmbx10 scaled\magstep2 \font\BMATH=cmmi10 scaled\magstep3 \topmatter \title \BTIT L\btit AGRANGE--\BTIT I\btit NVERSION\endtitle \author Josef Hofbauer \endauthor \affil Institut f\"ur Mathematik der Universit\"at Wien,\\ Strudlhofgasse 4, A-1090 Wien, Austria.\\ \endaffil \endtopmatter \rightheadtext{Lagrange Inversion} \document \subhead 1. Die Lagrangesche Inversionsformel \endsubhead Die Lagrangesche Inversionsformel l\"a\3t sich beispielsweise in der folgenden Art formulieren:\newline Sei $g(x)= \frac {x} {\varphi (x)}$ eine (formale) Potenzreihe (f.P.R.) in $x$ mit $\varphi (0)\neq 0$ und $f(x)$ eine f.P.R., die man nach den Potenzen von $g(x)$ entwickelt: $$f(x)=f(0)+\suml _{k=1} ^{\infty} c_k\, g(x)^k = f(0)+\suml _{k=1} ^{\infty} c_k \frac {x^k} {\varphi (x)^k }. \tag 1.1 $$ Dann sind die Koeffizienten $c_k$ durch folgende Formeln gegeben: \noindent {\it 1. Version der Lagrangeschen Formel}: $$c_n = \frac {1} {n} f'(x) g(x)^{-n}\big\vert_{x^{-1}}=\frac {1} {n}f'(x)\varphi (x)^n\big\vert_{x^{n-1}} .\tag I $$ \noindent {\it 2. Version der Lagrangeschen Formel}: $$c_n= f(x)g'(x)g(x)^{-n-1}\big\vert_{x^{-1}}= f(x)g'(x)\varphi (x)^{n+1}\big\vert_{x^n} .\tag II $$ Dabei bedeutet $h(x)\vert_{x^n}$ den Koeffizienten von $x^n$ in der formalen Potenz- oder Laurentreihe $h(x)$. F\"ur $h(x)\vert_{x^{-1}}$ werden wir manchmal auch Res $h(x)$ und sp\"ater $M(h(x)dx)$ schreiben. W\"ahlt man in (1.1) $f(x)=x$, so erh\"alt man die Koeffizienten der zu $g(x)$ (bez\"uglich Komposition ) inversen Potenzreihe. Einer der einfachsten Beweise der Lagrangeschen Inversionsformel ist der folgende: Wir zeigen zun\"achst \proclaim{Lemma 1} Ist $g(x)$ wie oben eine f.P.R. der Ordnung 1 (wie \"ublich ist die {\it Ordnung\/} einer formalen Potenzreihe $g(x)$ definitionsgem\"a\3 der kleinste Index $s$, soda\3 der Koeffizient von $x^s$ in $g(x)$ nicht verschwindet), dann gilt f\"ur beliebige ganze Zahlen $n$ $$\frac {g'(x)} {g^{n+1}(x)}\Big\vert_{ x^{-1}}= \de_{n0}.\tag1.2$$ \endproclaim \demo{Beweis} Ist n\"amlich $n\neq 0$, dann ist $g(x)g(x)^{-n+1}=-\frac {1} {n}(g(x)^{-n})'$ und hat daher als Ableitung einer formalen Laurentreihe das Residuum $0$. F\"ur $n=0$ ist $$\frac {g'(x)} {g(x)}=\frac {1} {x}-\frac {\varphi'(x)} {\varphi (x)},$$ und da der zweite Summand wegen $\varphi (0)\neq 0$ eine f.P.R. ist, ist das Residuum $=1$. Um jetzt die 1.~Version zu beweisen, leiten wir die Entwicklung (1.1) ab: $$f'(x)=\suml _{k=1} ^{\infty}c_k\cdot k\cdot g(x)^{k-1}g'(x),$$ dividieren durch $g(x)^n$ und nehmen das Residuum: $$\Res f'(x)g(x)^{-n}=\Res \suml _{k=0} ^{\infty} c_k\cdot k\cdot g'(x)g(x)^{-n+k-1}=nc_n$$ wegen Lemma~1. F\"ur die 2.~Version multiplizieren wir (1.1) blo\3 mit $g'(x)g(x)^{-n-1}$, bestimmen das Residuum und wenden wieder Lemma~1 an: $$\Res f(x)g'(x)g(x)^{-n-1}=\Res \suml _{k=1} ^{\infty} c_k g'(x)g(x)^{-n+k-1}= c_n.$$ Damit sind (I) und (II) gezeigt. \enddemo \example{Beispiele} (1) Die zu $g(x)=xe^{-ax}$ inverse Reihe ist $$G(z)=\suml _{n=1} ^{\infty} \frac {(an)^{n-1}} {n!}z^n, \tag 1.3 $$ weil man aus (I) f\"ur $f(x)=x$ und $\varphi (x)=e^{ax}$ $$c_n=\frac {1} {n}e^{ax}\big\vert_{x^{n-1}}=\frac {(an)^{n-1}} {n!}$$ erh\"alt. (2) Es gelten die Entwicklungen $$e^{xz}=\suml _{k=0} ^{\infty}\frac {x(x+ak)^{k-1}} {k!}(ze^{-az})^k \tag 1.4$$ und $$\frac {e^{xz}} {1-az}=\suml _{k=0} ^{\infty}\frac {(x+ak)^k} {k!}(ze^{-az})^k .\tag 1.5$$ Multipliziert man (1.4) mit $e^{yz}$ und vergleicht die Koeffizienten von $z^n$, erh\"alt man {\it Abels Identit\"at}: $$(x+y)^n=\suml _{k=0} ^{n}\binom n k x (x+ak)^{k-1}(y-ak)^{n-k} .\tag 1.6 $$ (3) Es gilt $$(1+z)^a=\suml _{k=0} ^{\infty}G_k (a,b)(z(1+z)^b)^k $$ mit $$G_n (a,b)=\frac {1} {n}a(1+z)^{a-1}(1+z)^{-nb}\big\vert_{z^{n-1}}=\frac {a} {n}\binom {a-1-nb} {n-1}=\frac {a} {a-bn}\binom {a-bn} n$$ Aus $(1+z)^{a+c}=(1+z)^a(1+z)^c$ folgt dann $$G_n(a+c,b)=\suml _{k=0} ^{n}G_k (a,b)G_{n-k}(c,b) .\tag 1.7$$ \endexample \subhead 2. Anwendungen in der Kombinatorik\endsubhead Eine der sch\"onsten Anwendungen der Lagrangeschen Formel auf ein kombinatorisches Problem ist die Herleitung von Cayleys Formel f\"ur die Anzahl der Wurzelb\"aume. Ein {\it Wurzelbaum\/} ist ein Baum, dessen Knoten durchnumeriert sind, wobei ein Knoten --- die Wurzel --- ausgezeichnet ist. Sei $b_n$ die Anzahl der Wurzelb\"aume \"uber der Knotenmenge $\{1,2,\dots,n\}$ und $$s(t)=\suml _{n=1} ^{\infty}\frac {b_n} {n!}t^n.$$ Bezeichnen wir au\3erdem mit $w_n$ die Anzahl der {\it Wurzelw\"alder\/} (= Graphen, deren Komponenten Wurzelb\"aume sind) \"uber $\{1,2,\dots,n\}$. Aus der Exponentialformel folgt dann $$1+\suml _{n=1} ^{\infty}\frac {w_n} {n!}t^n =e^{s(t)}.$$ Nun gilt aber $(n+1)w_n = s_{n+1}$: Denn aus jedem Wurzelbaum mit $n+1$ Knoten entsteht durch Weglassen der Wurzel ein Wurzelwalds mit $n$ Knoten. Korrigiert man jetzt noch die Numerierung, indem man dem $(n+1)$-ten Knoten die Nummer der weggelassenen Wurzel gibt, so wird aus der $1:1$ Abbildung eine $(n+1):1$-Abbildung. Daher ist $s(t)=te^{s(t)}$ oder $t=se^{-s}$. Aus (1.3) folgt also $$s(t)=\suml _{n=1} ^{\infty}\frac {n^{n-1}} {n!}t^n,$$ und somit $b_n=n^{n-1}$. Ein anderer Problemkreis, bei dem die Lagrangesche Inversionsformel n\"utzlich, wenn auch nicht notwendig ist, sind die {\it Catalanzahlen\/}. Bei den meisten kombinatorischen Fragestellungen, bei denen die Catalanzahlen $C_n$ auftauchen, z.B. Anzahl der Triangulierungen eines $(n+2)$-Ecks, Anzahl der bin\"aren B\"aume mit $n$ Stellen, Anzahl der verschiedenen Klammerungen eines Produktes von $n+1$ Faktoren, Anzahl der Wege im $\R^2$, die $(0,0)$ mit $(2n,0)$ verbinden und oberhalb der $x$-Achse verlaufen, usw\., erh\"alt man durch eine einfache \"Uberlegung die Rekursionsformel $$C_{n+1}= \suml _{k=0} ^{n} C_k C_{n-k}, \quad C_0=1 .\tag 2.1$$ Um die $C_n$ explizit zu berechnen, betrachtet man die erzeugende Funktion $$f(x)=\suml _{n=0} ^{\infty}C_n x^n .\tag 2.2$$ Aus (2.1) folgt dann $$\frac {f(x)-1} {x}=f(x)^2 .\tag 2.3 $$ Daraus kann man analog zum vorigen Beispiel die Koeffizienten $C_n$ berechnen. Dazu setzen wir z.B\. $f(x)=1+y(x)$, soda\3 (2.3) zu $$y=x(1+y)^2 \text {\quad oder\quad } x=y (1+y)^{-2}$$ wird. In (2.2) eingesetzt ergibt das $$y=\suml _{n=1} ^{\infty}C_n \frac {y^n} {(1+y)^{2n}},\tag 2.5$$ woraus mittels (I) $$C_n=\frac {1} {n}(1+y)^{2n}\big\vert_{y^{n-1}}=\frac {1} {n}\binom {2n}{n-1}=\frac {1} {n+1}\binom {2n} n \text { folgt }.$$ H\"atten wir $z=xf(x)=\suml _{n=1} ^{\infty}C_{n-1}x^n$ gesetzt, so erhielten wir aus (2.3) $$z-x=z^2 \text { oder } x=z(1-z),$$ also die zu (2.5) analoge Entwicklung $$z=\suml _{n=1} ^{\infty}C_{n-1}z^n (1-z)^n, \tag 2.6 $$ woraus genauso $C_n=\frac {1} {n+1} \binom {2n} n $ folgt. \subhead 3. Die mehrdimensionale Verallgemeinerung von Jacobi--Good\endsubhead Wir verwenden die \"ubliche Multiindexschreibweise. Eine f.P.R. in den $s$ Variablen $\bx=(x_1,\dots, x_s)$ ist eine Reihe $$f(\bx)=f(x_1,\dots, x_s)=\suml _{\bk\geq \bO} a_\bk \bx^\bk = \suml _{k_{1},\dots,k_s\geq 0 } a_{k_{1}\dots k_s} \, x_{1}^{k_{1}} x_{2}^{k_{2}}\cdots x_{s}^{k_{s}} .$$ Eine {\it formale Laurentreihe\/} (f.L.R.) sei eine Reihe der Form $$f(\bx)=\suml _{\bk\geq \bn} a_\bk \bx^\bk = \suml _{k_1\geq n_1,\dots,k_s\geq n_s} a_{k_{1}\dots k_s}\, x_{1}^{k_{1}}\cdots x_{s}^{k_{s}} ,$$ f\"ur einen Multiindex $\bn\in \Z^s$. Wir betrachten jetzt ein System $g=(g_{i})_{1\leq i\leq s}$ von f.P.R. in der $s$-dimensionalen Variablen $\bx$, das der Einfachheit halber von der Form $$g_i(\bx)=\frac {x_i} {\varphi_i (\bx)} \tag 3.1 $$ ist, wobei $\varphi_i (\bx)$ eine f.P.R. mit $\varphi_i (\bO) \neq 0$ ist. (Es w\"urde gen\"ugen, da\3 die Jacobische von $g$ im Nullpunkt eine Diagonalmatrix ist. Man m\"u\3te nur die f.L.R. etwas allgemeiner definieren, damit die folgenden \"Uberlegungen sinnvoll bleiben.) Man kann zu (1.1) analoge Entwicklungen betrachten: $$f(\bx)=f(\bO)+\suml _{\bk>\bO} c_\bk g(\bx)^\bk = f(\bO)+ \suml c_{k_{1}\dots k_{s}} g_1 (\bx)^{k_{1}}\cdots g_s(\bx)^{k_{s}}.$$ Dann gilt das folgende mehrdimensionale Analogon der zweiten Version der Lagrangeformel (von der 1.~Version sind nur \"au\3erst komplizierte Verallgemeinerungen bekannt): $$c_\bn=f(\bx) \cdot \det \frac {\partial g} {\partial \bx} \cdot g(\bx)^{-\bn-\bold {e}}\big\vert_{\bx^{- \bold {e}}}=f(\bx)\cdot \det \frac {\partial g} {\partial \bx}\cdot \varphi (\bx)^{\bn+ \bold {e}}\big\vert_{\bx^{\bn}}.\tag 3.2$$ Dabei ist $\e=(1,1,\dots, 1)$. Im Vergleich mit (II) ist die Ableitung $g'(x)$ durch die Funktionaldeterminante $\det\frac {\partial g} {\partial\bx}$ des Systems $g$ ersetzt. Der folgende Beweis stammt von J.~Cigler. Offensichtlich war der entscheidende Schritt im eindimensionalen Fall das Lemma~1. Wir m\"ussen jetzt also zeigen: \proclaim{Lemma 2} Sei $g$ wie in {\rm(3.1)}. Dann ist $$\det \frac {\partial g} {\partial \bx}\cdot g(\bx)^{-\bn-{\bold e}}\big\vert_{\bx^{-{\bold e}}}=\de_{\bn,\bO} .$$ \endproclaim Die Relation (1.2) ist \"aquivalent mit $$f(g(x))g'(x)\big\vert_{x^{-1}}=f(x)\big\vert_{x^{-1}} \text { f\"ur beliebige f.L.R. } f(x) .\tag 3.3 $$ Das erinnert an die Substitutionsformel f\"ur Integrale. Der Zusammenhang damit wird klar, wenn man den Koeffizienten von $x^{-1}$ also das Residuum, durch das bekannte Kurvenintegral darstellt. Das legt auch nahe, da\3 im Mehrdimensionalen $g'(x)$ durch die Funktionaldeterminante ersetzt wird. Um diesen Zusammenhang besser hervorzuheben, erweist sich eine neue Notation als zweckm\"a\3ig: Statt $f(x)\vert_{x^{-1}}$ schreiben wir $M(f(x)dx)$. Das lineare Funktional $M$ entspricht also dem Kurvenintegral\linebreak $\frac {1} {2\pi i}\oint f(z)\,dz $. Die Integralschreibweise wollen wir aber im Hinblick auf unsere formalen Potenzreihen vermeiden. Wir definieren also $$M(f(\bx)d\bx)=M(f(x_1,\dots,x_s)\,dx_1 \wedge dx_2 \wedge \cdots \wedge dx_s):=f(\bx)\big\vert_{\bx^{-\e}}.\tag 3.4$$ Genaugenommen w\"ahlen wir $M$ also als lineares Funktional auf den alternierenden Differentialformen von Dimension und Grad $s$ (die wir hier allerdings als Modul \"uber den f.L.R. statt den $C^{\infty}$-Funktionen auffassen). \demo{Beweis von Lemma 2} F\"ur eine f.L.R. $g(\bx)$ sei $$dg=\suml _{j=1} ^{s} \frac {\partial g} {\partial x_j} \,dx_j.$$ Daraus folgt $$\align dg_1\wedge dg_2 \wedge \cdots \wedge dg_s &= \Big(\suml _{j} \frac {\partial g_1} {\partial x_j} dx_j\Big)\wedge \cdots \wedge \Big(\suml _{j} \frac {\partial g_s} {\partial x_j}dx_j\Big)\tag 3.5\\ & = \det \(\frac {\partial g_i} {\partial x_j}\) \cdot dx_1 \wedge\cdots \wedge dx_s. \endalign$$ Wir zeigen zun\"achst f\"ur beliebige f.L.R. $g_1,\dots ,g_s$ $$M(dg_1 \wedge \cdots \wedge dg_s)= 0. \tag 3.6$$ Da alles linear ist, brauchen wir nur den Fall $$g_i (\bx)= \bx^{\bk_{i}}=x_{1}^{k_{i1}}x_{2}^{k_{i2}}\cdots x_{s}^{k_{is}}$$ betrachten. Dann ist $\partial g_i (\bx)/\partial x_j = k_{ij} \bx^{\bk_{i}}/x_j$ und $$\det \frac {\partial g} {\partial \bx}= \bx^{\bk_{1}+\cdots + \bk_{s}} \det \(\frac {k_{ij}} {x_j}\)=\bx^{\bk_{1}+ \cdots + \bk_{s}-\bold {e}}\det (k_{ij}).$$ Ist $\bk_1 +\cdots + \bk_s = 0$, dann verschwindet auch $\det (k_{ij})$, weil die Zeilensumme $=0$ ist. Damit ist (3.6) gezeigt. Weiters gilt f\"ur beliebige $g_1,\dots ,g_s$ $$M (\frac {dx_1} {x_k}\wedge \cdots \wedge \frac {dx_k} {x_k}\wedge dg_{k+1}\wedge \cdots \wedge dg_s)=0 \text { f\"ur }k