LAGRANGE–INVERSION

Josef Hofbauer

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

1. Die Lagrangesche Inversionsformel. Die Lagrangesche Inversionsformel läßt sich beispielsweise in der folgenden Art formulieren: Sei g(x) = \frac{x}{φ(x)} eine (formale) Potenzreihe (f.P.R.) in x mit φ(0) ≠ 0 und f(x) eine f.P.R., die man nach den Potenzen von g(x) entwickelt:

(1.1)  f(x) = f(0) + ∑_{k=1}^{∞} c_{k} g(x)^{k} = f(0) + ∑_{k=1}^{∞} c_{k} \frac{x^{k}}{φ(x)^{k}} .

Dann sind die Koeffizienten c_{k} durch folgende Formeln gegeben:

1. Version der Lagrangeschen Formel:

(I)  c_{n} = \frac{1}{n}f′(x)g(x)^{−n}|_{x^{−1}} = \frac{1}{n}f′(x)φ(x)^{n}|_{x^{n−1}}.

2. Version der Lagrangeschen Formel:

(II)  c_{n} = f(x)g′(x)g(x)^{−n−1}|_{x^{−1}} = f(x)g′(x)φ(x)^{n+1}|_{x^{n}}.

Dabei bedeutet h(x)|_{x^{n}} den Koeffizienten von x^{n} in der formalen Potenz- oder Laurentreihe h(x). Für h(x)|_{x^{−1}} werden wir manchmal auch Res h(x) und später M(h(x)dx) schreiben.

Wählt man in (1.1) f(x) = x, so erhält man die Koeffizienten der zu g(x) (bezüglich Komposition ) inversen Potenzreihe.

Einer der einfachsten Beweise der Lagrangeschen Inversionsformel ist der folgende: Wir zeigen zunächst

Lemma 1. Ist g(x) wie oben eine f.P.R. der Ordnung 1 (wie üblich ist die Ordnung einer formalen Potenzreihe g(x) definitionsgemäß der kleinste Index s, sodaß der Koeffizient von x^{s} in g(x) nicht verschwindet), dann gilt für beliebige ganze Zahlen n

(1.2)  \frac{g′(x)}{g^{n+1}(x)}|_{x^{−1}} = δ_{n0}.

1

Beweis. Ist nämlich n ≠ 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ür n = 0 ist

\frac{g′(x)}{g(x)} = \frac{1}{x} − \frac{φ′(x)}{φ(x)},

und da der zweite Summand wegen φ(0) ≠ 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) = ∑_{k=1}^{∞} c_{k} · k · g(x)^{k−1}g′(x),

dividieren durch g(x)^{n} und nehmen das Residuum:

Res f′(x)g(x)^{−n} = Res ∑_{k=0}^{∞} c_{k} · k · g′(x)g(x)^{−n+k−1} = nc_{n}

wegen Lemma 1.

Für die 2. Version multiplizieren wir (1.1) bloß 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 ∑_{k=1}^{∞} c_{k}g′(x)g(x)^{−n+k−1} = c_{n}.

Damit sind (I) und (II) gezeigt.

Beispiele.

(1) Die zu g(x) = xe^{−ax} inverse Reihe ist

(1.3)  G(z) = ∑_{n=1}^{∞} \frac{(an)^{n−1}}{n!} z^{n},

weil man aus (I) für f(x) = x und φ(x) = e^{ax}

c_{n} = \frac{1}{n}e^{ax}|_{x^{n−1}} = \frac{(an)^{n−1}}{n!}

erhält.

(2) Es gelten die Entwicklungen

(1.4)  e^{xz} = ∑_{k=0}^{∞} \frac{x(x + ak)^{k−1}}{k!} (ze^{−az})^{k}

und

(1.5)  \frac{e^{xz}}{1 − az} = ∑_{k=0}^{∞} \frac{(x + ak)^{k}}{k!} (ze^{−az})^{k}.

Multipliziert man (1.4) mit e^{yz} und vergleicht die Koeffizienten von z^{n}, erhält man Abels Identität:

(1.6)  (x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x(x + ak)^{k−1}(y − ak)^{n−k}.

(3) Es gilt

(1 + z)^{a} = ∑_{k=0}^{∞} 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}|_{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

(1.7)  G_{n}(a + c, b) = ∑_{k=0}^{n} G_{k}(a, b)G_{n−k}(c, b).

2. Anwendungen in der Kombinatorik. Eine der schönsten Anwendungen der Lagrangeschen Formel auf ein kombinatorisches Problem ist die Herleitung von Cayleys Formel für die Anzahl der Wurzelbäume. Ein Wurzelbaum ist ein Baum, dessen Knoten durchnumeriert sind, wobei ein Knoten — die Wurzel — ausgezeichnet ist.

Sei b_{n} die Anzahl der Wurzelbäume über der Knotenmenge {1, 2, …, n} und

s(t) = ∑_{n=1}^{∞} \frac{b_{n}}{n!} t^{n}.

Bezeichnen wir außerdem mit w_{n} die Anzahl der Wurzelwälder (= Graphen, deren Komponenten Wurzelbäume sind) über {1, 2, …, n}. Aus der Exponentialformel folgt dann

1 + ∑_{n=1}^{∞} \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) = ∑_{n=1}^{∞} \frac{n^{n−1}}{n!} t^{n},

und somit b_{n} = n^{n−1}.

Ein anderer Problemkreis, bei dem die Lagrangesche Inversionsformel nützlich, wenn auch nicht notwendig ist, sind die 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ären Bäume mit n Stellen, Anzahl der verschiedenen Klammerungen eines Produktes von n+1 Faktoren, Anzahl der Wege im ℝ^{2}, die (0, 0) mit (2n, 0) verbinden und oberhalb der x-Achse verlaufen, usw., erhält man durch eine einfache Überlegung die Rekursionsformel

(2.1)  C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k}, C_{0} = 1.

Um die C_{n} explizit zu berechnen, betrachtet man die erzeugende Funktion

(2.2)  f(x) = ∑_{n=0}^{∞} C_{n}x^{n}.

Aus (2.1) folgt dann

(2.3)  \frac{f(x) − 1}{x} = f(x)^{2}.

Daraus kann man analog zum vorigen Beispiel die Koeffizienten C_{n} berechnen. Dazu setzen wir z.B. f(x) = 1 + y(x), sodaß (2.3) zu

y = x(1 + y)^{2} oder x = y(1 + y)^{−2}

wird. In (2.2) eingesetzt ergibt das

(2.5)  y = ∑_{n=1}^{∞} C_{n} \frac{y^{n}}{(1 + y)^{2n}} ,

woraus mittels (I)

C_{n} = \frac{1}{n}(1 + y)^{2n}|_{y^{n−1}} = \frac{1}{n}\binom{2n}{n − 1} = \frac{1}{n + 1}\binom{2n}{n} folgt .

Hätten wir z = xf(x) = ∑_{n=1}^{∞} C_{n−1}x^{n} gesetzt, so erhielten wir aus (2.3)

z − x = z^{2} oder x = z(1 − z),

also die zu (2.5) analoge Entwicklung

(2.6)  z = ∑_{n=1}^{∞} C_{n−1}z^{n}(1 − z)^{n},

woraus genauso C_{n} = \frac{1}{n+1} \binom{2n}{n} folgt.

3. Die mehrdimensionale Verallgemeinerung von Jacobi–Good. Wir verwenden die übliche Multiindexschreibweise. Eine f.P.R. in den s Variablen x = (x_{1}, …, x_{s}) ist eine Reihe

f(x) = f(x_{1}, …, x_{s}) = ∑_{k≥0} a_{k}x^{k} = ∑_{k_{1},...,k_{s}≥0} a_{k_{1}...k_{s}} x_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{s}^{k_{s}}.

Eine formale Laurentreihe (f.L.R.) sei eine Reihe der Form

f(x) = ∑_{k≥n} a_{k}x^{k} = ∑_{k_{1}≥n_{1},...,k_{s}≥n_{s}} a_{k_{1}...k_{s}} x_{1}^{k_{1}} ⋯ x_{s}^{k_{s}},

für einen Multiindex n ∈ ℤ^{s}.

Wir betrachten jetzt ein System g = (g_{i})_{1≤i≤s} von f.P.R. in der s-dimensionalen Variablen x, das der Einfachheit halber von der Form

(3.1)  g_{i}(x) = \frac{x_{i}}{φ_{i}(x)}

ist, wobei φ_{i}(x) eine f.P.R. mit φ_{i}(0) ≠ 0 ist. (Es würde genügen, daß die Jacobische von g im Nullpunkt eine Diagonalmatrix ist. Man müßte nur die f.L.R. etwas allgemeiner definieren, damit die folgenden Überlegungen sinnvoll bleiben.) Man kann zu (1.1) analoge Entwicklungen betrachten:

f(x) = f(0) + ∑_{k>0} c_{k}g(x)^{k} = f(0) + ∑ c_{k_{1}...k_{s}}g_{1}(x)^{k_{1}} ⋯ g_{s}(x)^{k_{s}}.

Dann gilt das folgende mehrdimensionale Analogon der zweiten Version der Lagrangeformel (von der 1. Version sind nur äußerst komplizierte Verallgemeinerungen bekannt):

(3.2)  c_{n} = f(x) · det \frac{∂g}{∂x} · g(x)^{−n−e}|_{x^{−e}} = f(x) · det \frac{∂g}{∂x} · φ(x)^{n+e}|_{x^{n}}.

Dabei ist e = (1, 1, …, 1). Im Vergleich mit (II) ist die Ableitung g′(x) durch die Funktionaldeterminante det \frac{∂g}{∂x} des Systems g ersetzt.

Der folgende Beweis stammt von J. Cigler.

Offensichtlich war der entscheidende Schritt im eindimensionalen Fall das Lemma 1. Wir müssen jetzt also zeigen:

Lemma 2. Sei g wie in (3.1). Dann ist

det \frac{∂g}{∂x} · g(x)^{−n−e}|_{x^{−e}} = δ_{n,0}.

Die Relation (1.2) ist äquivalent mit

(3.3)  f(g(x))g′(x)|_{x^{−1}} = f(x)|_{x^{−1}} für beliebige f.L.R. f(x).

Das erinnert an die Substitutionsformel für 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ß im Mehrdimensionalen g′(x) durch die Funktionaldeterminante ersetzt wird. Um diesen Zusammenhang besser hervorzuheben, erweist sich eine neue Notation als zweckmäßig: Statt f(x)|_{x^{−1}} schreiben wir M(f(x)dx). Das lineare Funktional M entspricht also dem Kurvenintegral \frac{1}{2πi} ∮ f(z) dz. Die Integralschreibweise wollen wir aber im Hinblick auf unsere formalen Potenzreihen vermeiden. Wir definieren also

(3.4)  M(f(x)dx) = M(f(x_{1}, …, x_{s}) dx_{1} ∧ dx_{2} ∧ ⋯ ∧ dx_{s}) := f(x)|_{x^{−e}}.

Genaugenommen wählen wir M also als lineares Funktional auf den alternierenden Differentialformen von Dimension und Grad s (die wir hier allerdings als Modul über den f.L.R. statt den C^{∞}-Funktionen auffassen).

Beweis von Lemma 2. Für eine f.L.R. g(x) sei

dg = ∑_{j=1}^{s} \frac{∂g}{∂x_{j}} dx_{j}.

Daraus folgt

(3.5)  dg_{1} ∧ dg_{2} ∧ ⋯ ∧ dg_{s} = ( ∑_{j} \frac{∂g_{1}}{∂x_{j}} dx_{j}) ∧ ⋯ ∧ ( ∑_{j} \frac{∂g_{s}}{∂x_{j}} dx_{j})

= det (\frac{∂g_{i}}{∂x_{j}} ) · dx_{1} ∧ ⋯ ∧ dx_{s}.

Wir zeigen zunächst für beliebige f.L.R. g_{1}, …, g_{s}

(3.6)  M(dg_{1} ∧ ⋯ ∧ dg_{s}) = 0.

Da alles linear ist, brauchen wir nur den Fall

g_{i}(x) = x^{k_{i}} = x_{1}^{k_{i1}}x_{2}^{k_{i2}} ⋯ x_{s}^{k_{is}}

betrachten. Dann ist ∂g_{i}(x)/∂x_{j} = k_{ij}x^{k_{i}}/x_{j} und

det \frac{∂g}{∂x} = x^{k_{1}+···+k_{s}} det (\frac{k_{ij}}{x_{j}} ) = x^{k_{1}+···+k_{s}−e} det(k_{ij}).

Ist k_{1} + ⋯ + k_{s} = 0, dann verschwindet auch det(k_{ij}), weil die Zeilensumme = 0 ist. Damit ist (3.6) gezeigt.

Weiters gilt für beliebige g_{1}, …, g_{s}

(3.7)  M(\frac{dx_{1}}{x_{k}} ∧ ⋯ ∧ \frac{dx_{k}}{x_{k}} ∧ dg_{k+1} ∧ ⋯ ∧ dg_{s}) = 0 für k < s.

Dieser Ausdruck ist nämlich laut Definition gleich

M(\frac{1}{x_{1} ⋯ x_{k}} · D(x) · dx_{1} ∧ ⋯ ∧ dx_{s}) mit D(x) = det(∂g_{i}/∂x_{j})_{k<i,j≤s},

und diese Determinante hat wegen (3.6) keinen \frac{1}{x_{k+1}···x_{s}} -Term.

Sind jetzt g_{1}, …, g_{k} von der speziellen Form (3.1), die weiteren g_{k+1}, …, g_{s} jedoch noch beliebige f.L.R., so gilt auch

(3.8)  M(\frac{dg_{1}}{g_{1}} ∧ ⋯ ∧ \frac{dg_{k}}{g_{k}} ∧ dg_{k+1} ∧ ⋯ ∧ dg_{s}) = 0 für k < s.

Das folgt wegen

(3.9)  \frac{dg_{i}}{g_{i}} = \frac{dx_{i}}{x_{i}} − d(log φ_{i}) für i ≤ k

durch Induktion nach k aus (3.7).

Für k = s gilt jedoch, falls jetzt alle g_{i} (3.1) erfüllen,

(3.10)  M(\frac{dg_{1}}{g_{1}} ∧ ⋯ ∧ \frac{dg_{s}}{g_{s}}) = 1.

Das zeigt man ebenfalls mit (3.9). Damit ist der Fall n = 0 im Lemma 2 erledigt. Sei jetzt n ≠ 0. Für jedes i mit n_{i} ≠ 0 ist dann

g_{i}^{−n_{i}−1}dg_{i} = −\frac{1}{n_{i}} d(g_{i}^{−n_{i}}).

Die Behauptung M(g^{−n−e}dg_{1} ∧ ⋯ ∧ dg_{s}) = 0 reduziert sich daher auf den Typ (3.8). Damit ist das Lemma 2 vollständig gezeigt, und analog zum eindimensionalen Fall folgt die Formel von Lagrange–Good (3.2).

Als typische Anwendung wollen wir daraus das Master–Theorem von MacMahon [29] herleiten:

Master–Theorem. Sei (a_{ij})_{1≤i,j≤s} eine beliebige Matrix und D(x) = det(δ_{ij} − a_{ij}x_{j}).

Dann ist der Koeffizient von x^{n} in \frac{1}{D(x)} gleich dem Koeffizienten von x_{1}^{n_{1}} ⋯ x_{s}^{n_{s}} in (a_{11}x_{1} + ⋯ + a_{1s}x_{s})^{n_{1}} ⋯ (a_{s1}x_{1} + ⋯ + a_{ss}x_{s})^{n_{s}}.

Beweis. Wir wählen φ_{i}(x) = 1 + ∑_{j=1}^{s} a_{ij}x_{j} und f(x) = \frac{1}{D(g(x))}. Dann ist

∂φ_{i}/∂x_{j} = a_{ij} und ∂g_{i}/∂x_{j} = (δ_{ij} − a_{ij}g_{i})φ_{i}^{−1}. Außerdem gilt

det(δ_{ij} −a_{ij}x_{i}) = x_{1} ⋯ x_{s} det (\frac{δ_{ij}}{x_{i}} − a_{ij}) = x_{1} ⋯ x_{s} det(\frac{δ_{ij}}{x_{j}} −a_{ij}) = det(δ_{ij} −a_{ij}x_{j}).

Anwendung von (3.2) ergibt daher, daß der Koeffizient c_{n} von g(x)^{n} in \frac{1}{D(g(x))}

c_{n} = ∏_{i} (1 + ∑_{j} a_{ij}x_{j})^{n_{i}} |_{x^{n}} = ∏_{i} ( ∑_{j} a_{ij}x_{j})^{n_{i}} |_{x^{n}}

ist.

Formel (3.2) wird meistens nach Good [19] benannt. Sie war aber bereits Jacobi [23] bekannt. Weitere Beweise findet man in [5, 20, 24, 34].

4. Inverse Relationen. Das einfachste Paar inverser Relationen ist wohlbekannt:

(4.1)  a_{n} = ∑_{k=0}^{n} \binom{n}{k}b_{k} ⇔ b_{n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}a_{k}.

An die 60 weitere derartige Relationen findet man, in verschiedene Gruppen klassifiziert, bei Riordan [31], der ein Drittel seines Buches diesem Themenkreis widmet. Er gibt aber jedesmal ad hoc–Beweise und entwickelt keine gemeinsam zugrundeliegende Theorie. Offensichtlich besagt ein solches Paar inverser Relationen

(4.2)  a_{n} = ∑_{k=0}^{n} α_{nk}b_{k} ⇔ b_{n} = ∑_{k=0}^{n} β_{nk}a_{k},

daß die beiden unendlichen Dreiecksmatrizen (α_{nk}) und (β_{nk}) zueinander invers sind:

(4.3)  ∑_{k} α_{nk}β_{km} = δ_{nm} = ∑_{k} β_{nk}α_{km}.

Egoritschew [10] hat nun folgenden Ansatz zur Erzeugung inverser Relationen untersucht: Seien g(x), h(x) f.P.R. der Ordnung 1 und f(x) eine f.P.R. der Ordnung 0, also mit f(0) ≠ 0. Dann erhält man ein Paar inverser Relationen auf folgende Weise:

(4.4)  f(x)g(x)^{k} = ∑_{n=k}^{∞} α_{nk}h(x)^{n} ⇔ f(x)^{−1}h(x)^{k} = ∑_{n=k}^{∞} β_{nk}g(x)^{n}.

Die Koeffizienten α_{nk}, β_{nk} dieser Entwicklungen lassen sich natürlich mittels der Lagrangeformel (II) sofort angeben:

(4.5)  α_{nk} = M(\frac{f(x)g(x)^{k}h′(x)}{h(x)^{n+1}}dx) und β_{nk} = M(\frac{h(x)^{k}g′(x)}{f(x)g(x)^{n+1}} dx).

Egoritschew hat dann festgestellt, daß die meisten bekannten inversen Relationen, insbesondere alle in Riordan [31] enthaltenen, unter dieses einfache Schema fallen.

Beispiel.

(1) α_{nk} = \binom{n + k}{k + p} (siehe [31, Tafel 2.1.4]). Es gilt

α_{nk} = \binom{n + p}{k + p} = M(\frac{(1 + x)^{n+p}}{x^{n−k+1}} dx).

Entsprechend (4.5) wählen wir h(x) = \frac{x}{1+x}, g(x) = x, und wegen h′(x) = (1 + x)^{−2} schließlich f(x) = (1 + x)^{p+1}.

⇒ β_{nk} = M(\frac{(1 + x)^{−k−p−1}}{x^{n+1−k}} dx) = \binom{−k − p − 1}{n − k} = (−1)^{n−k}\binom{n + p}{n − k}.

(2) α_{nk} = \binom{p + qk − k}{n − k} ([31, Tafel 2.2.1]). Es gilt

α_{nk} = M(\frac{(1 + x)^{p+qk−k}}{x^{n−k+1}} dx).

Hier wählen wir also g(x) = x(1 + x)^{q−1}, h(x) = x, f(x) = (1 + x)^{p}.

⇒ β_{nk} = M (\frac{(1 + x)^{q−1} + x(q − 1)(1 + x)^{q−2}}{(1 + x)^{p}(1 + x)^{(q−1)(n+1)}x^{n−k+1}} dx)

= M (\frac{(1 + x)^{−n(q−1)−p−1}(1 + qx)}{x^{n−k+1}}dx)

= \binom{−1 − p − n(q − 1)}{n − k} + q\binom{−1 − p − n(q − 1)}{n − k − 1}

= (−1)^{n−k}\binom{p + nq − k}{n − k} + (−1)^{n−k−1}q\binom{p + nq − k − 1}{n − k − 1}

= (−1)^{n−k}\binom{p + nq − k}{n − k}\frac{p + kq − k}{p + nq − k} .

(3) a_{n} = ∑_{k} \binom{n}{k}b_{n−ck} ([31, Tafel 2.4.1]). Hier gilt

α_{n,n−ck} = \binom{n}{k} = M (\frac{(1 + x^{c})^{n}}{x^{ck+1}} dx) .

Wir wählen g(x) = x, h(x) = \frac{x}{1+x^{c}}, h′(x) = \frac{1+x^{c}−cx^{c}}{(1+x^{c})^{2}} , f(x) = \frac{1+x^{c}}{1+x^{c}−cx^{c}}.

⇒ β_{n,n−ck} = M (\frac{g′}{f · g} (\frac{h}{g})^{n} \frac{dx}{h^{ck}} )

= M (\frac{1 + x^{c} − cx^{c}}{(1 + x^{c})^{n+1−ck}} \frac{dx}{x^{1+ck}} )

= \binom{ck − n}{k} − c\binom{ck − n − 1}{k − 1}

= (−1)^{k}\binom{n − ck + k − 1}{k} − c(−1)^{k−1}\binom{n − ck + k − 1}{k − 1}

= (−1)^{k} \frac{n}{k}\binom{n − ck + k − 1}{k − 1}.

Ein Spezialfall, beziehungsweise bloß eine andere Schreibweise für inverse Relationen, ist die umbrale Inversion von Polynomen. Nehmen wir z.B. die Gegenbauerpolynome C_{n}^{λ}(x), die durch die erzeugende Funktion

(4.6)  ∑_{n=0}^{∞} C_{n}^{λ}(x)t^{n} = (1 − 2xt + t^{2})^{−λ}

definiert sind. Daraus lassen sich die C_{n}^{λ} bekanntlich leicht berechnen:

(4.7)  C_{n}^{λ}(x) = ∑_{n=0}^{[n/2]}(−1)^{k} \frac{(λ)^{(n−k)}(2x)^{n−2k}}{k! (n − 2k)!} .

Hier und im Folgenden bedeutet das Symbol (a)^{(n)} die aufsteigenden Faktoriellen, (a)^{(n)} := a(a + 1) ⋯ (a + n − 1).

Wir wollen nun umgekehrt x^{n} nach den C_{k}^{λ}(x) entwickeln. Dazu schreiben wir (4.6) in der Form

(1 + t^{2})^{λ} ∑_{k} C_{k}^{λ}(x)t^{k} = (1 − \frac{2tx}{1 + t^{2}} )^{−λ} = ∑_{n} \frac{(λ)^{(n)}}{n!} (2x)^{n} \frac{t^{n}}{(1 + t^{2})^{n}} .

Diese Gleichung kann man als Entwicklung der Funktion auf der linken Seite nach Potenzen von \frac{t}{1+t^{2}} interpretieren. Für die Koeffizienten muß daher nach (II) gelten:

\frac{(λ)^{(n)}}{n!} (2x)^{n} = (1 + t^{2})^{λ} · ∑_{k} C_{k}^{λ}(x)t^{k} · (1 + t^{2})^{n+1} \frac{1 + t^{2} − 2t^{2}}{(1 + t^{2})^{2}} |_{t^{n}}

= ∑_{k} C_{k}^{λ}(x)t^{k} · (1 + t^{2})^{λ+n−1}(1 − t^{2})|_{t^{n}}

= ∑_{k} C_{n−2k}^{λ}(x) [\binom{n + λ − 1}{k} − \binom{n + λ − 1}{k − 1}]

= ∑_{k} C_{n−2k}^{λ}(x)\binom{n + λ − 1}{k}\frac{n + λ − 2k}{n + λ − k} .

(4.8)  ⇒ x^{n} = 2^{−n}n! ∑_{k} \frac{n + λ − 2k}{k! (λ)^{(n+1−k)}} C_{n−2k}^{λ}(x).

Ein einfacheres Beispiel sind die Laguerrepolynome

(4.9)  L_{n}^{(α)}(x) = ∑_{k=0}^{n} \binom{n + α}{n − k}\frac{n!}{k!}(−x)^{k}

mit der erzeugenden Funktion

(4.10)  ∑_{n=0}^{∞} \frac{L_{n}^{(α)}(x)}{n!}t^{n} = (1 − t)^{−1−α}e^{\frac{tx}{t−1}} .

Man könnte hier analog vorgehen. Diese Rechnung haben wir im Wesentlichen aber schon durchgeführt: Ein Blick auf Beispiel 1 zeigt sofort

(4.11)  x^{n} = ∑_{k=0}^{n}(−1)^{k}\binom{n + α}{n − k}\frac{n!}{k!}L_{k}^{(α)}(x).

Auf dieselbe Weise lassen sich die meisten Inversionen der bekannten speziellen Polynome herleiten.

5. Folgen von Binomialtyp. Betrachten wir für eine f.P.R. g(z) = z/φ(z) mit φ(z) ≠ 0 die Entwicklung

(5.1)  e^{xz} = ∑_{n=0}^{∞} \frac{p_{n}(x)}{n!}g(z)^{n}.

Dann ist offensichtlich p_{n}(x) ein Polynom vom Grad n in x und p_{n}(0) = δ_{n0}. Aus e^{(x+y)z} = e^{xz} · e^{yz} folgt

(5.2)  p_{n}(x + y) = ∑_{k=0}^{n} \binom{n}{k}p_{k}(x)p_{n−k}(y),

d.h. (p_{n}) ist eine Folge von Binomialtyp (siehe [33]).

Bezeichnen wir mit D den Differentiationsoperator nach x und wenden diesen auf (5.1) an, so folgt

ze^{xz} = ∑_{n} \frac{Dp_{n}(x)}{n!}g(z)^{n},

und durch Iteration erhält man

g(z)e^{xz} = ∑_{n} \frac{g(D)p_{n}(x)}{n!}g(z)^{n}.

Nach Division durch g(z) erhält man durch Koeffizientenvergleich mit (5.1)

(5.3)  g(D)p_{n}(x) = np_{n−1}(x).

Außerdem sieht man leicht, daß diese Relation gemeinsam mit den Anfangswerten p_{n}(0) = δ_{n0} die Polynome p_{n}(x) charakterisiert.

Beispiel. Für g(z) = ze^{−az} haben wir in (1.4) als Koeffizienten die Abelpolynome A_{n}^{(a)}(x) = x(x + an)^{n−1} erhalten. Diese erfüllen daher (5.2), und (5.3) besagt

De^{−aD}A_{n}^{(a)}(x) = DA_{n}^{(a)}(x − a) = nA_{n−1}^{(a)}(x).

Aus der Entwicklung (5.1) erhält man durch Anwendung der Lagrangeformel:

(I) ⇒ \frac{p_{n}(x)}{n!} = \frac{1}{n}xe^{xt}φ(t)^{n}|_{t^{n−1}} = \frac{x · φ(D)^{n}x^{n−1}}{n!} ,

da a(D)\frac{x^{n}}{n!} = a(t)e^{xt}|_{t^{n}} für beliebige f.P.R. a(t). Also

(5.4)  p_{n}(x) = x · φ(D)^{n}x^{n−1}.

(II) ⇒ p_{n}(x) = n! e^{xt}g′(t)φ(t)^{n+1}|_{t^{n}}, also

(5.5)  p_{n}(x) = g′(D)φ(D)^{n+1}x^{n}.

Diese beiden wichtigen Formeln (5.4) und (5.5), die ,,closed forms“ aus [33, p. 695], sind also unmittelbare Folgerungen aus der Lagrangeschen Inversionsformel.

Umgekehrt läßt sich aus ihnen (I) und (II) herleiten (siehe [5, 13, 32]): Dazu faßt man die Entwicklung (1.1) als linearen Operator auf dem Raum der Polynome auf:

f(D) = ∑_{k=0}^{∞} c_{k} g(D)^{k}.

Wendet man diesen Operator auf die Polynome p_{n}(x) an, so gilt wegen (5.3)

Lf(D)p_{n} = ∑_{k} c_{k}Lg(D)^{k}p_{n} = c_{n} · n!,

wenn Lp(x) = p(0) die Auswertung im Nullpunkt bezeichnet. Setzt man nun für p_{n}(x) (5.4) und (5.5) ein, erhält man

n! c_{n} = Lf(D) x · φ(D)^{n}x^{n−1} = Lf′(D)φ(D)^{n}x^{n−1} = (n − 1)! f′(z)φ(z)^{n}|_{z^{n−1}}

beziehungsweise

n! c_{n} = Lf(D)g′(D)φ(D)^{n+1}x^{n} = n! f(z)g(z)φ(z)^{n+1}|_{z^{n}}.

Dabei wurden nur die trivialen Formeln

f(D)x − xf(D) = f′(D)  und  Lf(D)x^{n} = n! f(z)|_{z^{n}}

verwendet.

Die Folgen vom Binomialtypen lassen sich natürlich aufs Mehrdimensionale verallgemeinern und das entsprechende Analogon von (5.5) liefert dann die Lagrange– Good-Formel (3.2). Siehe dazu [5, 20, 24] und [2] für den Fall nichtkommutierender Variable.

Weitere Beispiele für Folgen von Binomialtyp sind die oberen und unteren Faktoriellen (x)^{(n)} = x(x + 1) ⋯ (x + n − 1) und (x)_{n} = x(x − 1) ⋯ (x − n + 1), die Laguerrepolynome L_{n}^{(α)}(x) aus (4.9) für α = −1 und die Gouldpolynome G_{n}(x, b) aus (1.7).

Eine geringfügige Verallgemeinerung sind die Shefferpolynome. Sie entstehen als Koeffizienten in einer Entwicklung

(5.6)  f(z)e^{xz} = ∑_{n} \frac{s_{n}(x)}{n!}g(z)^{n}

und haben ganz ähnliche Eigenschaften wie die p_{n}(x). Die wichtigsten Beispiele sind die Hermitepolynome und Laguerrepolynome L_{n}^{(α)}(x) (für jedes α).

Mit der Lagrangeschen Inversionsformel läßt sich (5.6) verallgemeinern zu

(5.7)  ∑_{n=0}^{∞} \frac{s_{n}(x + ny)}{n!} (g(z)e^{−yz})^{n} = f(z)e^{xz} (1 − y \frac{g(z)}{g′(z)})^{−1} .

Zum Beweis braucht man bloß in (II) einsetzen und erhält als Koeffizienten

\frac{e^{(x+yn)z}f(z)g′(z)}{g(z)^{n+1}} |_{z^{n}}.

(II) auf (5.6) angewendet zeigt dann, daß dieser Ausdruck gleich s_{n}(x + nx)/n! ist.

Seien jetzt s_{n}(x) durch (5.6) gegeben und eine Folge p_{n}(x) vom Binomialtyp durch ∑_{n} p_{n}(x)/n! h(z)^{n} = e^{xz}. Wenn wir nun die p_{n}(x) nach den s_{k}(x) entwickeln und

umgekehrt, erhalten wir ein Paar inverser Relationen:

(5.8)  \frac{p_{n}(x)}{n!} = ∑_{k=0}^{n} α_{nk} \frac{s_{k}(x)}{k!} und \frac{s_{n}(x)}{n!} = ∑_{k=0}^{n} β_{nk} \frac{p_{k}(x)}{k!}.

Rota [33] hat mit diesem Ansatz einen eleganteren und einheitlicheren Zugang zu Riordans inversen Relationen von Gould- und Abel-Typ gefunden. Wegen

e^{xz} = ∑_{n} \frac{p_{n}(x)}{n!}h(z)^{n} = ∑_{k} \frac{s_{k}(x)}{k!} ∑_{n} α_{nk}h(z)^{n},

folgt durch Koeffizientenvergleich mit (5.6)

f(z)^{−1}g(z)^{k} = ∑_{n} α_{nk}h(z)^{n},

und analog

f(z)h(z)^{k} = ∑_{n} β_{nk}g(z)^{n}.

Die inversen Relationen (5.8), die als Zusammenhangskoeffizienten zwischen zwei Shefferpolynomen auftreten, sind also dieselben, die man mit Egoritschews Methode erhält. Insbersondere lassen sich daher alle inversen Relationen von Riordan aus dem umbralen Kalkül herleiten (obwohl das in [33, Problem 1] für die Legendre und Tschebischeff-Typen bestritten wird).

6. Garsias q-Analogon. L. Carlitz [3] gab 1973 folgendes schöne q-Analogon der Lagrangeformeln im Spezialfall φ(z) = 1 − z an:

(6.1)  f(z) = ∑_{n} c_{n} \frac{z^{n}}{(1 − z)(1 − qz) ⋯ (1 − q^{n−1}z)}

mit

(6.2)  c_{n} = \frac{1}{[n]}f′(z)(1 − z)(1 − qz) ⋯ (1 − q^{n−1}z)|_{z^{n−1}}
= f(z)(1 − z)(1 − qz) ⋯ (1 − q^{n−2}z)|_{z^{n}}.

(Hier steht [n] für (q^{n}−1)/(q−1) = 1+q+⋯+q^{n−1}, f′(z) bezeichnet die q-Ableitung (f(qz) − f(z))/(q − 1)z. Siehe [8].)

Dieses überaus schöne Beispiel war der Anlaß für eine intensive Suche nach einem q-Analogon der Lagrangeschen Inversionsformel. Heute kennt man zwei verschiedenartige Theorien, die außer Carlitz’s Beispiel wenig Gemeinsames haben. Der naheliegende und zunächst (von Andrews [1], Gessel [16], Garsia und Joni [12, 14]) untersuchte Ansatz in der Form

(6.3)  f(z) = ∑_{k} c_{k}g(z)g(qz) ⋯ g(q^{k−1}z)

ist in formaler Hinsicht äußerst befriedigend, die meisten interessanten Dinge in dieser Theorie haben im klassischen Fall q = 1 aber kein Gegenstück.

Die andere Richtung (siehe [7, 18, 20, 22, 25]) leistet wahrscheinlich eher das, was man sich anfangs erhofft hat: neue q-Analoga für die Dinge zu liefern, die man mit der klassischen Lagrangeformel behandeln kann, etwa q-Analoga der inversen Relationen, Zusammenhänge mit den bekannten q-Analoga der speziellen Polynome, etc.

Wenden wir uns zunächst dem Ansatz (6.3) zu. Diese Form der ,,q-Potenzen“ von g(z) hat folgende erstaunliche Eigenschaft:

Satz. Es gibt zu jeder f.P.R. g(z) (der Ordnung 1) eine f.P.R. G(z), sodaß gilt:

∑_{k} a_{k}z^{k} = ∑_{k} b_{k}g(z)g(qz) ⋯ g(q^{n−1}z) (6.4)

⇔ ∑_{k} a_{k}G(z)G(z/q) ⋯ G(z/q^{k−1}) = ∑_{k} b_{k}z^{k}.

G(z) nennen wir die q-Inverse von g(z). g ist dann die \frac{1}{q}-Inverse von G.

Beweis. Sei

z = ∑_{n≥1} G_{n} g(z)g(qz) ⋯ g(q^{n−1}z) ⇒ G(z) := ∑_{n≥1} G_{n}z^{n}.

⇒ z^{2} = ∑_{k} G_{k} g(z)g(qz) ⋯ g(q^{k−1}z)q^{−k} · q^{k}z

= ∑_{k} q^{−k}G_{k} g(z) ⋯ g(q^{k−1}z) · ∑_{l} G_{l}g(q^{k}z) ⋯ g(q^{k+l−1}z)

= ∑_{n} ( ∑_{k} q^{−k}G_{k}G_{n−k})g(z) ⋯ g(q^{n−1}z)

und

∑_{n} ( ∑_{k} q^{−k}G_{k}G_{n−k})z^{n} = ∑_{k} q^{−k}G_{k}z^{k} · ∑_{l} G_{l}z^{l} = G(z) · G(z/q),

usw.

Um für die Entwicklung (6.3) eine Lagrangeformel zu finden, brauchen wir eine entsprechende Verallgemeinerung von Lemma 1.

Lemma 3. Es gibt (genau) eine f.P.R. g^{0}(z), so daß

(6.5)  M (\frac{g^{0}(z)dz}{g(z)g(z/q) ⋯ g(z/q^{n})}) = δ_{n0}.

Dieses g^{0}(z) muß also ein q-Analogon der Ableitung g′(z) sein, es ist aber nicht die übliche q-Ableitung. Wir werden zwar einige Formeln für dieses g^{0}(z) herleiten, konkret ausrechnen läßt es sich aber anscheinend nur in Carlitz’s Beispiel.

Beweis. Schreiben wir g(z) = z/φ(z), so wird (6.5) zu

(6.6)  g^{0}(z)φ(z)φ(z/q) ⋯ φ(z/q^{n})|_{z^{n}} = δ_{n0}.

Setzt man jetzt g^{0}(z) = γ_{0} + γ_{1}z + γ_{2}z^{2} + ⋯ unbestimmt an, dann kann man daraus sukzessive die γ_{n} berechnen.

Kehren wir jetzt zur Entwicklung (6.3) zurück. Wir dividieren durch g(z) ⋯ g(q^{n}z) und ersetzen z durch z/q^{n}:

⇒ \frac{f(z/q^{n})}{g(z)g(z/q) ⋯ g(z/q^{n})} = \frac{c_{0}}{g(z) ⋯ g(z/q^{n})} + \frac{c_{1}}{g(z) ⋯ g(z/q^{n−1})} + ⋯

+ \frac{c_{n}}{g(z)} + c_{n+1} + c_{n+2} g(qz) + · · · .

Durch Multiplikation mit g^{0}(z) folgt aus Lemma 3

(6.7)  c_{n} = M (\frac{f(z/q^{n})g^{0}(z)dz}{g(z)g(z/q) ⋯ g(z/q^{n})}) = q^{n}M (\frac{f(z)g^{0}(q^{n}z)dz}{g(z)g(qz) ⋯ g(q^{n}z)})

oder

(6.8)  c_{n} = q^{−\binom{n}{2}}f(z)g^{0}(q^{n}z)φ(z) ⋯ φ(q^{n}z)|_{z^{n}}.

Das ist Garsias q-Analogon der 2. Version der Lagrangeschen Inversionsformel. Andrews [1] hat ein q-Analogon der 1. Version angegeben, das allerdings viel komplizierter ist, er stellt c_{n} nämlich als (n + 1) × (n + 1)-Determinante dar.

Wir wollen noch zwei Formeln für g^{0}(z) herleiten: Für q = 1 gilt für die Koeffizien-

ten γ_{n} von g^{0}(z) = ∑_{n} γ_{n}z^{n}

γ_{n} = g′(z)|_{z^{n}} = M (\frac{g′(z)dz}{z^{n+1}} ) = M (\frac{dz}{G(z)^{n+1}} )

15 nach der Substitutionsformel (3.3), wenn G(z) die zu g(z) inverse Potenzreihe ist. Dafür lautet das q-Analogon:

(6.9)  γ_{n} = M (\frac{dz}{G(z)G(z/q) ⋯ G(z/q^{n})}) .

Beweis. Ein Blick auf (6.4) zeigt, daß wir den Koeffizienten b_{n} jetzt auf zwei Arten berechnen können. Das ergibt für beliebige b_{n} die Gleichnung

(6.10)  q^{n}M (\frac{g^{0}(q^{n}z) ∑_{k} a_{k}z^{k}}{g(z) ⋯ g(q^{n}z)} dz) = M (\frac{∑_{k} a_{k}G(z) ⋯ G(z/q^{k−1})}{z^{n+1}}dz) ,

ein q-Analogon der Substitutionsformel (3.3).

Setzen wir jetzt ∑_{k} a_{k}z^{k} = g(z) ⋯ g(q^{n}z)z^{−n−1}, so folgt wegen (6.4)

g(z) ⋯ g(q^{n}z) = ∑_{k} a_{k}z^{k+n+1}

⇒ z^{n+1} = ∑_{k} a_{k}G(z) ⋯ G(z/q^{k+n})

⇒ \frac{z^{n+1}q^{(n+1)^{2}}}{G(qz) ⋯ G(q^{n+1}z)} = ∑_{k} a_{k}G(z)G(z/q) ⋯ G(z/q^{k−1}).

In (6.10) eingesetzt erhalten wir

q^{n}M (\frac{g^{0}(q^{n}z)}{z^{n+1}}dz) = q^{(n+1)^{2}}M (\frac{dz}{G(qz) ⋯ G(q^{n+1}z)})

also

γ_{n} = M (\frac{dz}{G(z)G(z/q) ⋯ G(z/q^{n})}) .

Für die zweite Formel brauchen wir noch etwas Notation, nämlich Garsias ,,roofing“ und ,,starring“: Für f.P.R. f(z) = ∑_{k} a_{k}z^{k} sei

f̂(z) = ∑_{k} a_{k}q^{−\binom{k}{2}}z^{k}

und, falls a_{0} = 1,

f^{∗}(z) = f(z)f(qz)f(q^{2}z) · · · .

Dieses unendliche Produkt konvergiert für |q| < 1 oder formal, wenn man f^{∗}(z) als f.P.R. mit rationalen Funktionen in q als Koeffizienten auffaßt. Dieses f^{∗}(z) ist auch die einzige f.P.R. mit f^{∗}(0) = 1 und

f(z) · f^{∗}(qz) = f^{∗}(z).

Es gilt dann für g(z) = z/φ(z) und φ(0) = 1

(6.11)  g^{0}(z) = φ^{∗}(qz) · (\frac{1}{φ̂^{∗}(z/q)})ˆ .

Beweis. Setzen wir g^{0}(z) = φ^{∗}(qz) · ψ̂(z) an. Dann wird (6.6) zu

φ^{∗}(z/q^{n})ψ̂(z)|_{z^{n}} = δ_{n0}.

Durch Einsetzen von φ^{∗}(z) = ∑_{n} φ_{n}z^{n} und ψ(z) = ∑_{n} ψ_{n}z^{n} sieht man erstaunt ein,

daß diese Gleichung äquivalent ist mit

φ̂^{∗}(z/q) · ψ(z)|_{z^{n}} = δ_{n0},

woraus schließlich φ̂^{∗}(z/q) · ψ(z) = 1 folgt.

In [12] findet man noch eine Fülle solcher eigenartiger Identitäten mit ^{∗} und ˆ , die wahrscheinlich das Reizvollste an dieser Theorie sind, für q = 1 aber ihren Sinn verlieren.

Leider kann man all diese Formeln für g^{0}(z) anscheinend nur in einem Fall konkret verwerten, nämlich für φ(z) = 1 − z, also Carlitz’s Beispiel: Es ist dann

φ^{∗}(z) = ∏_{i=0}^{∞}(1 − q^{i}z) = ∑_{n=0}^{∞} \frac{(−z)^{n}q^{\binom{n}{2}}}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})},

daher

φ̂^{∗}(z) = ∑_{n} \frac{(−z)^{n}}{(1 − q) ⋯ (1 − q^{n})}, \frac{1}{φ̂^{∗}(z)} = ∑_{n} \frac{q^{\binom{n}{2}}z^{n}}{(1 − q) ⋯ (1 − q^{n})}

(\frac{1}{φ̂^{∗}(z)})ˆ = ∑_{n} \frac{q^{\binom{n}{2}}z^{n}}{(1 − q) ⋯ (1 − q^{n})} = ∏_{i=0}^{∞}(1 − q^{i}z)^{−1} = \frac{1}{φ^{∗}(z)},

⇒ g^{0}(z) = φ^{∗}(qz) · φ^{∗}(z/q)^{−1} = \frac{1}{(1 − z)(1 − z/q)},

sodaß (6.8) in diesem Fall wirklich (6.2) liefert.

Man kann auch ein q-Analogon der Folgen von Binomialtyp studieren: Ausgehend von

e^{xz} = ∑_{n} \frac{p_{n}(x)}{n!}g(z)g(qz) ⋯ g(q^{n−1}z)

lassen sich genauso wie in Kap. 5 die folgenden Formeln herleiten:

p_{n}(x + y) = ∑_{k} \binom{n}{k}p_{n}(x)p_{n−k}(y/q^{k})
εg(D)p_{n} = np_{n−1}, wobei D der gewöhnliche Differentiations-

operator und εf(x) = f(qx) ist,

p_{n}(x) = q^{−\binom{n}{2}}g^{0}(q^{n}D)φ(D) ⋯ φ(q^{n}D)x^{n−1}.

7. Ein allgemeiner Ansatz, weitere q-Analoga. Wir wollen uns jetzt mit allgemeineren Entwicklungen

(7.1)  f(z) = ∑_{k} c_{k}g_{k}(z)

beschäftigen, wo g_{k}(z) eine f.L.R. der Ordnung k ist (die Ordnung einer formalen Laurentreihe ist wie bei formalen Potenzreihen definiert, siehe Lemma 1), und versuchen, hier die Koeffizienten c_{k} zu berechnen.

Dazu müßte man f.L.R. G_{n}(z) der Ordnung −n finden, sodaß etwa

(7.2)  L g_{k}(z)G_{n}(z) = δ_{nk}

für alle ganzen Zahlen n, k gilt. Dabei sei L das lineare Funktional

Lf(z) = f(z)|_{z^{0}} = M (\frac{f(z)}{z}dz) .

Dann würde für den Koeffizienten c_{n} aus (7.1) nämlich gelten:

(7.3)  c_{n} = Lf(z) G_{n}(z).

Für g_{k}(z) = g(z)^{k} beispielsweise ist wegen Lemma 1

(7.4)  G_{n}(z) = \frac{zg′(z)}{g(z)^{n+1}} .

Es stellt sich daher das Problem, ob man die G_{n}(z) auch für allgemeinere g_{k}(z) explizit angeben kann. Mit der folgenden Methode gelingt das in einigen wichtigen Fällen.

Nehmen wir an, daß unsere Folge g_{n}(z) die Eigenvektoren eines Operators sind, beziehungsweise seien allgemeiner U, V zwei lineare Operatoren auf dem Raum der f.L.R., und es gelte für irgendwelche reellen Zahlen c_{n}:

(7.5)  Ug_{n} = c_{n}V g_{n}.

⟨a(z), b(z)⟩ = La(z)b(z) ist ein inneres Produkt auf den f.L.R.

Ist V bijektiv, dann gibt es eindeutig bestimmte f.L.R. g̃_{k}(z) der Ordnung −k, die zu den V g_{n}(z) biorthogonal sind:

⟨g̃_{k}, V g_{n}⟩ = δ_{nk} (7.6)

⇒⟨g̃_{k}, Ug_{n}⟩ = c_{n}⟨g̃_{k}, V g_{n}⟩c_{n}δ_{nk} = c_{k}δ_{nk}.
⇒⟨U^{∗}g̃_{k}, g_{n}⟩ = c_{k}⟨V^{∗}g_{k}, g_{n}⟩

also:

(7.7)  U^{∗}g̃_{k} = c_{k}V^{∗}g̃_{k} und
(7.8)  G_{k} = V^{∗}g̃_{k} erfüllt ⟨G_{k}, g_{n}⟩ = δ_{nk}.

Die Methode besteht also darin, zunächst Hilfsfunktionen g̃_{k}(z) zu berechnen, die ein ähnliches Eigenwertsproblem wie die g_{n}(z) (nur für die adjungierten Operatoren) erfüllen, und daraus kann man dann die gesuchten G_{n} konstruieren.

Beispiele für Operatoren.

(1) ε_{q}f(x) = f(qx) ⇒ ε_{q}^{∗}f(x) = f(\frac{x}{q}).

(2) Multiplikationsoperator Uf(x) = a(x)f(x): U = U^{∗}.

(3) Uf(x) = xf′(x) ⇒ U^{∗}f(x) = −xf′(x). Jetzt können wir an Hand der klassischen Lagrangeformel zeigen, daß diese Methode überhaupt funktioniert: Die Potenzen g_{n}(z) = g(z)^{n} erfüllen bekanntlich

g′_{n}(z) = ng_{n}(z) · \frac{g′(z)}{g(z)}.

Das ist eine Gleichung der Form (7.5), wenn wir z.B. U = xD, V = xg′(x)/g(x) und c_{n} = n wählen. Die g̃_{k}(x) erfüllen daher nach (7.7)

g̃′_{k}(x) = −kg̃_{k}(x)\frac{g′}{g} d.h.
g̃_{k}(x) = g(x)^{−k} und
G_{k}(x) = V^{∗}g̃_{k} = x\frac{g′(x)}{g(x)^{k+1}} , also genau (7.4).

Egoritschews Ansatz für inverse Relationen läßt sich natürlich leicht auf diese allgemeine Situation übertragen: Betrachten wir neben (g_{n}) noch eine zweite Folge (h_{n}) mit

Lh_{n}H_{k} = δ_{nk},

dann ist

(7.9)  α_{nk} = Lf(x)g_{k}(x)H_{n}(x)  β_{nk} = Lf(x)^{−1}h_{k}(x)G_{n}(x)

ein Paar inverser Relationen, wie man aus den beiden Entwicklungen

f(x)g_{k}(x) = ∑_{n} α_{nk}h_{n}(x) und

f(x)^{−1}h_{k}(x) = ∑_{n} β_{nk}g_{n}(x)

unmittelbar entnimmt.

Krattenthalers q-Analogon. Seien φ_{n}, ψ_{n} zwei Folgen f.P.R. mit

φ′_{n} = [n]φ_{n}(x)φ(x)  (′ ist jetzt die q-Ableitung )
(7.10)  ψ′_{n} = q^{−n}[n]ψ_{n}(qx)ψ(x),

und sei

(7.11)  g_{n}(x) = \frac{x^{n}}{φ_{n}(x)ψ_{n}(x)}.

19

Für die Entwicklung (7.1) nach solchen ,,q-Potenzen“ g_{n}(x) konnte Krattenthaler [25, 26] folgende q-Lagrangeformel zeigen:

(7.12)  c_{n} = \frac{1}{[n]}f′(x)φ_{n}(x)ψ_{n}(qx)|_{x^{n−1}}

= f(x)φ_{n}(\frac{x}{q})ψ_{n}(qx) (1 − \frac{x}{q}φ (\frac{x}{q}) − xψ(x)) |_{x^{n}}. (7.13)

Zum Beweis schreiben wir (7.10) um in

φ_{n}(qx) = φ_{n}(x)(1 + (q^{n} − 1)xφ(x))
ψ_{n}(x) = ψ_{n}(qx)(1 + (q^{−n} − 1)xψ(x)).
⇒ \frac{g_{n}(qx)}{g_{n}(x)} = \frac{q^{n} + (1 − q^{n})xψ(x)}{1 + (q^{n} − 1)xφ(x)}
(7.14) ⇒ g_{n}(qx)(1 − xφ(x)) − xψ(x)g_{n}(x) = q^{n}[g_{n}(x)(1 − xψ(x)) − xφ(x)g_{n}(qx)].

Diese Gleichung ist genau eine Eigenwertgleichung der Form (7.5). Es folgt daher

g̃_{n} (\frac{x}{q}) (1 − \frac{x}{q}φ (\frac{x}{q}))−xψ(x)g̃_{n}(x) = q^{n} [g̃_{n}(x)(1 − xψ(x)) − \frac{x}{q}φ (\frac{x}{q}) g̃_{n} (\frac{x}{q})] .

Aus dieser q-Differenzgleichung für g̃_{n}(x) ergibt sich

\frac{g̃_{n}(\frac{x}{q})}{g̃_{n}(x)} = \frac{q^{n} + (1 − q^{n})xψ(x)}{1 + (q^{n} − 1)\frac{x}{q}φ(\frac{x}{q})} = q^{n} \frac{ψ_{n}(x)}{ψ_{n}(qx)} \frac{φ_{n}(x/q)}{φ_{n}(x)},

(7.15)  ⇒ g̃_{n}(x) = \frac{φ_{n}(x)ψ_{n}(qx)}{x^{n}}.

Die zu g_{n}(x) orthogonalen G_{n}(x) errechnen sich nach (7.8) zu

G_{n}(x) = (1 − xψ(x))g̃_{n}(x) − \frac{x}{q}φ (\frac{x}{q}) g̃_{n} (\frac{x}{q})

= x^{−n}φ_{n} (\frac{x}{q}) ψ_{n}(qx)\{(1 − xψ(x)) (1 + (q^{n} − 1)\frac{x}{q}φ (\frac{x}{q}))

− \frac{x}{q}φ (\frac{x}{q}) (q^{n} + (1 − q^{n})xψ(x))\}

= x^{−n}φ_{n} (\frac{x}{q}) ψ_{n}(qx) (1 − \frac{x}{q}φ (\frac{x}{q}) − xψ(x)) .

Das liefert wegen c_{n} = Lf(x)G_{n}(x) das q-Analogon der 2. Version (7.13).

Die 1. Version erhält man aus der Beobachtung

g′_{n}(x) = (\frac{x^{n}}{ψ_{n}(x)})′ \frac{1}{φ_{n}(x)} + \frac{(qx)^{n}}{ψ_{n}(qx)} (\frac{1}{φ_{n}(x)})′

= \frac{[n]x^{n−1}}{ψ_{n}(x)} (1 − xψ(x))\frac{1}{φ_{(}x)} − \frac{(qx)^{n}}{ψ_{n}(qx)} \frac{[n]φ(x)}{φ_{n}(qx)}

= \frac{[n]}{x}\{g_{n}(x)(1 − xψ(x)) − xφ(x)g_{n}(qx)\} = \frac{[n]}{x}V g_{n}.

Wegen (7.6) folgt daher

Lg′_{n}(x)\frac{g̃_{k}(x)}{x} = [n]δ_{nk},

und somit

c_{n} = \frac{1}{[n]}f′(x)φ_{n}(x)ψ_{n}(qx)|_{x^{n−1}}.

Der ursprüngliche Beweis von Krattenthaler ist etwas eleganter: Er erhält die Orthogonalitätsrelationen direkt durch Ableiten des Quotienten g_{k}/g_{n}. Für einen weiteren Beweis mit Hilfe von Polynomen (analog zu Kap. 5) siehe [21].

Die Schwierigkeit bei diesem q-Analogon ist es, konkrete Beispiele für Folgen φ_{n} beziehungsweise ψ_{n} mit (7.10) zu finden. Das derzeit allgemeinste bekannte Beispiel ist

φ_{n}(x) = e_{r}((a[n] + b)x^{r})/e_{r}(bx^{r}),

wobei e_{r}(x) die q^{r}-Exponentialfunktion ist (siehe [8, § 1.2]). ψ_{n}(x) erhält man daraus, indem man entweder n durch −n oder q durch \frac{1}{q} ersetzt. Für die Anwendungen reicht das aber vollkommen aus.

Die wichtigsten Spezialfälle von Krattenthalers q-Lagrangeformel sind:

(1) φ_{n}(z) = (1 − az)(1 − qaz) ⋯ (1 − q^{n−1}az), ψ_{n} ≡ 1. Das ist wieder Carlitz’s Beispiel (6.1). Wegen φ′_{n}(z) = −[n]φ_{n}(z)\frac{a}{1−az} folgt aus (7.12) und (7.13) sofort (6.2).

Betrachtet man eine zu (5.1) analoge Entwicklung, erhält man als Koeffizienten die q-Laguerrepolynome (siehe [6, 14]). Außerdem liefert es folgendes q-Analogon der inversen Relation (Kap. 4, Bsp. 1):

α_{nk} = [ \begin{matrix}n + p \\ n + k \end{matrix} ] , β_{nk} = (−1)^{n−k}q^{\binom{n−k}{2}} [ \begin{matrix}n + p \\ n − k \end{matrix} ] .

(2) φ_{n}(z) = e(a[n]z), ψ_{n} ≡ 1 (Jackson [22], Cigler [7]). Damit läßt sich analog zu (Kap. 1, Bsp. 2) Jacksons q-Analogon der Abelidentität herleiten, es liefert die ,,richtigen“ q-Analoga der Abelpolynome [7] und der inversen Relationen von Abeltyp, z.B.

α_{nk} = (−1)^{n−k} [ \begin{matrix}n \\ k \end{matrix} ] [n + p]^{n−k}, β_{nk} = q^{\binom{n−k}{2}} [ \begin{matrix}n \\ k \end{matrix} ] [n + p][k + p]^{n−k−1}.

(3) φ(z) = (1 − az)(1 − qaz) ⋯ (1 − q^{n−1}az), ψ_{n}(z) = (1 − z/q)(1 − z/q^{2}) ⋯ (1 − z/q^{n}). Dieses Beispiel hängt eng mit den q-Jacobi- und q-Gegenbauerpolynomen zusammen. Gessel und Stanton [18] wenden es auf Transformationen hypergeometrischer Reihen an. Krattenthaler [25, 26] konnte damit überzeugende q-Analoga der inversen Relationen von Legendre- und Chebyshevtyp herleiten, etwa (vergleiche Kap. 4, Bsp. 3).

a_{n} = ∑_{k} [ \begin{matrix}n + p \\ k \end{matrix} ] b_{n−2k} ⇔ b_{n} = ∑_{k}(−1)^{k}q^{\binom{k}{2}} [ \begin{matrix}n + p − k \\ k \end{matrix} ] \frac{[n + p]}{[n + p − k]}a_{n−2k}.

Schließlich führt es — ausgehend von (2.5) — zu einem q-Analogon der Catalanzahlen (siehe Kap. 8).

Das q-Analogon von Gessel–Stanton. In [18] geben Gessel und Stanton ein q-Analogon der Lagrangeformel für den Spezialfall g(x) = x(1 + x)^{−b−1} an, das außer in Spezialfällen anscheinend nicht in Krattenthalers Ansatz (7.11) enthalten ist. Im Wesentlichen bringen sie ein q-Analogon der inversen Relation von Gouldtyp (Kap. 4. Bsp. 2). Sie betrachten (in etwas anderer Notation): g_{k}(x) = ∑_{n} α_{nk}x^{n} mit

(7.16)  α_{nk} = q^{−b(n−k)k} \frac{[a + bk − k]^{(n−k)}}{[n − k]_{b}!} .

Dabei sei [a]^{(n)} = [a][a + 1] ⋯ [a + n − 1],

[a]_{b} = \frac{q^{ab} − 1}{q^{b} − 1} = \frac{[ab]}{[b]}.

Man rechnet leicht nach, daß

g_{k}(x)(1 − q^{−kb}[b] x) = q^{−kb}g_{k}(q^{b}x) − xq^{a} [b] g_{k}(qx)

gilt, was wieder als Eigenwertgleichung

(7.17)  g_{k}(q^{b}x) + [b] x g_{k}(x) = q^{bk}(g_{k}(x) + xq^{a} [b] g_{k}(qx))

geschrieben werden kann.

⇒ g̃_{n}(q^{−b}x) + [b] xg̃_{n}(x) = q^{bn} (g̃_{n}(x) + \frac{x}{q}q^{a} [b] g̃_{n} (\frac{x}{q})) .

Setzt man g̃_{n}(x) = ∑_{k≤n} γ_{nk}x^{−k}, erhält man durch Koeffizientenvergleich

q^{bk}γ_{nk} + [b] γ_{n,k+1} = q^{bn}(γ_{nk} + q^{a−1} [b] q^{k+1}γ_{n,k+1})

⇒ \frac{γ_{nk}}{γ_{n,k+1}} = [b]\frac{q^{a+bn+k} − 1}{q^{bk} − q^{bn}} = −q^{−kb} \frac{[a + bn + k]}{[n − k]_{b}}

⇒ γ_{nk} = γ_{nn} q^{b\binom{k}{2}−b\binom{n}{2}} \frac{[a + bn + k]^{(n−k)}}{[n − k]_{b}!} (−1)^{n−k}.

Schließlich ist

G_{n}(x) = g̃_{n}(x) + xq^{a−1} [b] g̃_{n}(x/q).

Setzt man G_{n}(x) = ∑_{k≤n} β_{nk}x^{−k}, so ist (β_{nk}) wegen

δ_{nk} = Lg_{k}(x)G_{n}(x) = L ∑_{j,i} α_{jk}x^{j}β_{ni}x^{−i} = ∑_{i} β_{ni}α_{ik}

genau die zu (α_{nk}) inverse Matrix.

Man erhält

β_{nk} = γ_{nk} + q^{a+k} [b] γ_{n,k+1}

= q^{b\binom{k}{2}−b\binom{n}{2}}(−1)^{n−k} \frac{[a + bn + k + 1]^{(n−k−1)}}{[n − k]_{b}!}

× ([a + bn + k] − [n − k]_{b} [b] q^{a+k+bk})

= \frac{[a + bn + k + 1]^{(n−k−1)}[a + bk + k]}{[n − k]_{b}!}q^{b\binom{k}{2}−b\binom{n}{2}}(−1)^{n−k}. (7.18)

Wir haben somit zwei zueinander inverse Relationen (7.16) und (7.18). Man kann das Ergebnis aber auch als Lagrangeformel für die g_{k}(x) = ∑_{n} α_{nk}x^{n} auffassen: Für

den Koeffizienten c_{n} in der Entwicklung (7.1) einer Funktion f(x) = ∑_{k} f_{k}x^{k} gilt

c_{n} = Lf(x)G_{n}(x) = ∑_{k} β_{nk}f_{k}.

8. q-Catalanzahlen. Ausgehend von den Entwicklungen (2.5) und (2.6) für die Catalanzahlen, wollen wir jetzt zwei verschiedene q-Analoga der Catalanzahlen studieren, die den beiden q-Lagrangeformeln von Garsia und Krattenthaler entsprechen.

Carlitz’s q-Catalanzahlen. Wir definieren analog zu (2.6) q-Catalanzahlen C_{n} = C_{n}(q) durch (siehe [1]):

(8.1)  z = ∑_{n=1}^{∞} C_{n−1}z^{n}(1 − z)(1 − qz) ⋯ (1 − q^{n−1}z).

Aus (6.4) beziehungsweise dessen Beweis folgt dann

z^{2} = ∑_{n=2}^{∞} ( ∑_{k+l=n} C_{k−1}C_{l−1}q^{k(l−1)}) z^{n}(1 − z) ⋯ (1 − q^{n−1}z).

Andererseits folgt aus (8.1)

z = C_{0}z(1 − z) + ∑_{n=2}^{∞} C_{n−1} z^{n}(1 − z) ⋯ (1 − q^{n−1}z),

C_{0} = 1 und eine andere Entwicklung von z^{2}, sodaß man durch Koeffizientenvergleich

C_{n−1} = ∑_{k+l=n−2} C_{k}C_{l} q^{(k+1)l}

oder

(8.2)  C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k} q^{(k+1)(n−k)}

erhält. Mit C_{n} = q^{\binom{n}{2}}C̃_{n} wird das zu

C̃_{n+1} = ∑_{k=0}^{n} q^{−k}C̃_{k}C̃_{n−k}.

Diese q-Catalanzahlen erfüllen im Wesentlichen also das einfachste q-Analogon der klassischen Rekursion (2.1) der Catalanzahlen. Für die ersten Werte erhält man:

C_{0} = C_{1} = 1, C_{2} = 1+q, C_{3} = 1+q+2q^{2}+q^{3}, C_{4} = 1+q+2q^{2}+3q^{3}+3q^{4}+3q^{5}+q^{6}, …

Das Analogon von (2.5) führt, wie man sich leicht überlegt, zu denselben q-Cata-lanzahlen:

(8.3)  z = ∑_{n=1}^{∞} q^{\binom{n−1}{2}}C_{n} \frac{z^{n}}{(1 + z)(1 + qz) ⋯ (1 + q^{2n−1}z)}.

Eine explizite Formel für die C_{n} ist allerdings nicht bekannt. Dafür gibt es noch eine schöne kombinatorische Interpretation: Sei C_{n} die Menge aller Wörter mit n Nullen und n Einsern, wo jeder Anfangsabschnitt mindestens so viele 0 wie 1 enthält. Diesen Wörtern entsprechen Wege von (0, 0) nach (2n, 0), die nicht unter die x-Achse gehen, wenn man jeder 0 ein ansteigendes, jeder 1 ein absteigendes Wegstück zuordnet. Bekanntlich ist |C_{n}| = C_{n}. Für das q-Analogon gilt jetzt:

(8.4)  C_{n} = ∑_{w∈C_{n}} q^{inv w}.

Zum Beweis zerlegt man ein Wort w ∈ C_{n+1} in der üblichen Weise in

w = 0w_{1}1w_{2} mit w_{1} ∈ C_{k}, w_{2} ∈ C_{n−k}.

Für die Anzahl der Inversionen von w gilt dann

inv w = inv w_{1} + inv w_{2} + (k + 1)(n − k).

Daher erfüllt ∑_{w∈C_{n}} q^{inv w} dieselbe Rekursion (8.2) wie die C_{n}.

Die q-Catalanzahlen c_{n}(λ). Der 3. Spezialfall von Krattenthalers q-Analogon der Lagrangeformel legt es nahe, die Entwicklung (2.5) auch auf folgende Weise zu verallgemeinern:

(8.5)  z = ∑_{n} \frac{c_{n}(λ)}{q^{\binom{n}{2}}} \frac{z^{n}}{(1 + z/q^{n}) ⋯ (1 + z/q)(1 + q^{λ}z) ⋯ (1 + q^{λ+n−1}z)}.

Aus (7.12) folgt dann

q^{−\binom{n}{2}}c_{n}(λ) = \frac{1}{[n]}(1 + z/q^{n−1}) ⋯ (1 + z)(1 + q^{λ}z) ⋯ (1 + q^{λ+n−1}z)|_{z^{n−1}}

= \frac{1}{[n]} ∑_{k} [ \begin{matrix}n \\ k \end{matrix} ] q^{\binom{k}{2}}(q^{−n+1}z)^{k} ∑_{l} [ \begin{matrix}n \\ l \end{matrix} ] q^{\binom{l}{2}}(q^{λ}z)^{l}|_{z^{n−1}}

= \frac{1}{[n]} ∑_{k} [ \begin{matrix}n \\ k \end{matrix} ] q^{\binom{k}{2}−k(n−1)+λ(n−1−k)+\binom{n−1−k}{2}}\binom{n}{n − 1 − k}, (8.6)

und schließlich

(8.7)  c_{n}(λ) = \frac{1}{[n]} ∑_{k} [ \begin{matrix}n \\ k \end{matrix} ] [ \begin{matrix}n \\ k + 1 \end{matrix} ] q^{k^{2}+λk}.

Die Summanden sind q-Analoga der Runyonzahlen r_{nk} = \frac{1}{n} \binom{n}{k}\binom{n}{k+1} aus [31, p. 17], sie zählen die Wege von (0,0) bis (2n,0) über der x-Achse mit k ,,Tälern“.

Für gewisse λ läßt sich (8.6) einfacher berechnen: Für λ = 1 etwa gilt

c_{n}(1) = q^{\binom{n}{2}} \frac{1}{[n]}(1 + z/q^{n−1}) ⋯ (1 + q^{n}z)|_{z^{n−1}}

= q^{\binom{n}{2}} \frac{1}{[n]} [ \begin{matrix}2n \\ n − 1 \end{matrix} ] q^{(−n+1)(n−1)+\binom{n−1}{2}}

= \frac{1}{[n + 1]} [ \begin{matrix}2n \\ n \end{matrix} ] , (8.8)

also das naheliegendste q-Analogon der Catalanzahlen überhaupt. Für λ = 0 erhält man auf ähnliche Weise

(8.9)  c_{n}(0) = \frac{1}{[n + 1]} [ \begin{matrix}2n \\ n \end{matrix} ] \frac{1 + q}{1 + q^{n}} .

Für die ersten Werte gilt

c_{0}(λ) = c_{1}(λ) = 1, c_{2}(λ) = 1 + q^{1+λ}, c_{3}(λ) = 1 + [3]q^{1+λ} + q^{4+2λ}, …

Nun zur kombinatorischen Interpretation. Es gilt:

(8.10)  c_{n}(λ) = ∑_{w∈C_{n}} = q^{maj w+(λ−1) des w}.

Dabei bezeichnet maj w den major (oder greater) index von w und des w die Anzahl der Abstiege (= … 10 …) in w.

Für den Fall λ = 1 hat J. Fürlinger den folgenden eleganten Beweis gefunden: Betrachten wir alle Wege von (0, 0) nach (2n, 0) kodiert durch 0–1-Wörter w, so

gilt bekanntlich (siehe etwa [29]):

∑_{w} q^{maj w} = [ \begin{matrix}2n \\ n \end{matrix} ] .

Wir ordnen jetzt jedem Weg w, der unter die x-Achse geht, bijektiv einen Weg w′ von (0, 0) nach (2n, 2) zu: Dazu bestimmen wir den Punkt P auf dem Weg, der am ,,tiefsten“ liegt, und falls es mehrere solche gleichtiefe gibt, dann den ersten davon. P′ sei der Punkt vor P. Indem wir das unmittelbar vor P gelegene absteigende Wegstück P′P in ein aufsteigendes hinaufklappen und den Rest des Weges (um zwei Einheiten nach oben verschoben) daran anhängen, erhalten wir den Weg w′. Aus w′ kann man w wieder zurückgewinnen: Der kritische Punkt P′, an dem das darauffolgende Wegstück wieder hinuntergeklappt werden muß, ist der am weitesten rechts liegende unter den ,,tiefsten“ Punkten von w′. Offensichtlich ist maj w′ = maj w − 1. Daher gilt:

∑_{w∈C_{n}} q^{maj w} = [ \begin{matrix}2n \\ n \end{matrix} ] − ∑_{w∉C_{n}} q^{maj w} = [ \begin{matrix}2n \\ n \end{matrix} ] − q ∑_{w′} q^{maj w′}

= [ \begin{matrix}2n \\ n \end{matrix} ] − q [ \begin{matrix}2n \\ n − 1 \end{matrix} ] = \frac{1}{[n + 1]} [ \begin{matrix}2n \\ n \end{matrix} ] .

Für den allgemeinen Fall (λ beliebig) und weitere Eigenschaften der q-Catalanzah-len verweise ich auf [11].

9. Abschließende Bemerkungen. Wie aus dem Unmfang des Skriptums ersichtlich, erweist sich das Thema ,,Lagrange-Inversion“ als unerwartet ergiebig. Die Stoffauswahl ist natürlich sehr subjektiv, die kombinatorische Seite wurde zu Gunsten der analytischen vernachlässigt, die q-Analoga sind sicher nicht zu kurz gekommen. Auf einige wesentliche Aspekte, etwa kombinatorische Beweise, wurde überhaupt nicht eingegangen. Ich verweise hier auf die Literatur, z.B. [4, 27, 30, 34].

Als Quelle habe ich neben der zitierten Literatur in erster Linie eine Vorlesung über ,,Kombinatorische Identitäten“ benutzt, die Prof. Cigler im WS 1981/82 gehalten hat. Ich hoffe, die Darstellung dadurch insofern bereichert zu haben, daß sie für jeden den einen oder anderen neuen Aspekt enthält.

Literatur

[1] G.E. ANDREWS, Identities in combinatories II: A q-analog of the Lagrange inversion theorem, Proc. Amer. Math. Soc. 53 (1975), 240–245.

[2] G. BARON und P. KIRSCHENHOFER, Operatorenkalkül über freien Monoiden III: Lagrangeinversion und Sheffersysteme, Monatsh. Math. 92 (1981), 83–103.

[3] L. CARITZ, Some q-expansion formulas, Glasnik Mat. 8 (1973), 205–214.

[4] L CHOTTIN, Énumération d’arbres et formules d’inversion de séries formelles, J. Combin. Theory Ser. B 31 (1981), 23–45.

[5] J. CIGLER, Sequences of polynomials of binomial type and the Lagrange–Good formula, Univ. Wien, 1977.

[6] J. CIGLER, Operatormethoden für q-Identitäten II: q-Laguerre-Polynome, Monatsh. Math. 91 (1981), 105–117.

[7] J. CIGLER, Operatormethoden für q-Identitäten III: Umbrale Inversionen und die Lagrange’sche Formel, Arch. Math. 35 (1980), 533–543.

[8] J. CIGLER, Elementare q-Identitäten, Actes de la 5ème session du Séminaire Lotharingien de Combinatoire, publication de l’I.R.M.A. no 182/S–04, Strasbourg, 1982, pp. 23–58.

[9] L. COMTET, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

[10] G. P. EGORITSCHEW, Integral representation and the computation of combinatorial sums, “Nauka” Sibirsk. Otdel., Novosibirsk, 1977, translated from the Russian: Translations of Mathematical Monographs, 59, Amer. Math. Soc., Providence, R. I., 1984.

[11] J. FÜRLINGER and J. HOFBAUER, q-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), 248—264.

[12] A. M. GARSIA, A q-analogue of the Lagrange inversion formula,, Houston J. Math. 7 (1981), 205–237.

[13] A. M. GARSIA and S. A. JONI, A new expression for umbral operators and power series inversion, Proc. Amer. Math. Soc. 64 (1977), 179–185.

[14] A. M. GARSIA and S. A. JONI, Composition sequences, Comm. Algebra 8 (1980), 1195–1266.

[15] I. M. GESSEL, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A 28 (1980), 321–337.

[16] I. GESSEL, A noncommutative generalization and a q-analog of the Lagrange inversion formula, Trans. Amer. Math. Soc. 257 (1980), 455–482.

[17] I. GESSEL and D. STANTON, Strange evaluations of hypergeometric series, SIAM J. Math. Anal. 13 (1982), 295–308.

[18] I. GESSEL and D. STANTON, Application of q-Lagrange inversion to basic hypergeometric series, Trans. Amer. Math. Soc. 277 (1983), 173–203.

[19] I. J. GOOD, Generalization to several variables of Lagrange’s expansion, with application to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367–380.

[20] J. HOFBAUER, A short proof of the Lagrange–Good formula, Discrete Math. 25 (1979), 135– 139.

[21] J. HOFBAUER, A q-analog of the Lagrange expansion, Arch. Math. 42 (1984), 536–544.

[22] F. H. JACKSON, A q-generalization of Abel’s series, Rendiconti Palermo 29 (1910), 340–346.

[23] C. JACOBI, De resolutione aequationum per series infinitas, J. Reine Angew. Math. 6 (1830), 257–286.

[24] S. A. JONI, Lagrange inversion in higher dimensions and umbral operators, Linear and Multilinear Algebra 6 (1978), 111–122.

[25] Ch. KRATTENTHALER, A new q-Lagrange formula and some applications, Proc. Amer. Math. Soc. 90 (1984), 338–344.

[26] Ch. Krattenthaler, Lagrangeformel und inverse Relationen, Ph. Doct. Thesis, University of Vienna, 1983.

[27] G. LABELLE, Une nouvelle demonstration combinatoire des formules inversion de Lagrange, Advances in Math. 42 (1981), 217–247.

[28] J. L. LAGRANGE, Nouvelles méthodes pour résoudre les équations littérales par le moyens de séries, (1770) Oeuvres, vol. 3, Gauthier–Villars, Paris, 1869, pp. 1–73.

[29] P. A. MAC MAHON, Collected Papers: Combinatorics, Vol. I, MIT Press, Cambridge, Massachusetts.

[30] G. N. RANEY, Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451.

[31] J. RIORDAN, J. Wiley, New York, 1968.

[32] St. ROMAN and G. C. ROTA, The umbral calculus, Advances in Math. 27 (1978), 95–188.

[33] G. C. ROTA, D. KAHANER and A. ODLYZKO, Finite operator calculus, J. Math. Anal. Appl. 42 (1973), 685–760.

[34] W. T. TUTTE, On elementary calculus and the Good formula, J. Combin. Theory Ser. B 18 (1975), 97–137.