What is Lagrange Inversion good for?

Question

I am planning an introductory combinatorics course (mixed grad-undergrad) and am trying to decide whether it is worth budgeting a day for Lagrange inversion. The reason I hesitate is that I know of very few applications for it -- basically just enumeration of trees and some slight variants on this. I checked van Lint and Wilson, Enumerative Combinatorics II (but not the exercises) and Concrete Mathematics, and they all only present this application.

So, besides counting trees, where can we use Lagrange inversion?

Answer 1

You can use Lagrange inversion to explicitly solve

$$x^5-x-a=0\qquad (*)$$

(yes, a fifth degree equation, gasp). More precisely, it yields an infinite series expansion

$$x=-\sum_{k\geq 0}\binom{5k}{k}\frac{a^{4k+1}}{4k+1}$$

for the root of $(*)$ which is $0$ at $a=0.$ Although this isn't combinatorics, I'd gladly devote a class in any subject I teach to be able to derive it, because by Bring–Jerrard, any quintic equation can be reduced to this form, and you get a solution of something that many people believe, albeit for differing reasons, to be unsolvable.

Answer 2

1. The Lagrange inversion theorem is the essential tool needed to prove results like the following: Let $F(x)$ be the unique power series with rational coefficients such that for all $n\geq 0$, the coefficient of $x^n$ in $F(x)^{n+1}$ is 1. Then $F(x)=x/(1-e^{-x})$. For an application to algebraic geometry, see Lemma 1.7.1 of F. Hirzebruch, Topological Methods in Algebraic Geometry.

2. An alternating tree is a tree on the vertex set $\{1,\dots,n\}$ such that every vertex is either greater than all its neighbors or less than all its neighbors. Alternating trees arise in such contexts as the general hypergeometric systems of Gelfand and his collaborators, and in the combinatorics of the Linial hyperplane arrangement. Let $f(n-1)$ be the number of alternating trees on the vertex set $\{1,\dots,n\}$. Then $$ f(n) =\frac{1}{2^n}\sum_{k=0}^n {n\choose k}(k+1)^{n-1}. $$ So far as I know, the only known proof uses Lagrange inversion. (While this is a tree enumeration result, it is of a different nature than the standard applications of Lagrange inversion to tree enumeration.)

Answer 3

In combinatorics, applications are more general than just counting trees. In general context, Lagrange inversion is used to obtain a generating function $\sum c_n t^n$ for the numbers $c_n$ of the form $$c_n = [x^n] f(x) g(x)^n.$$

Perhaps, the simplest example is a generating function for $c_n = \binom{2n}{n}$ treated as the coefficient of $x^n$ in $(1+x)^{2n}$ (i.e., $f(x)=1$ and $g(x)=(1+x)^2$). However, in this case it is not hard to get the anticipated generating function $(1-4t)^{-1/2}$ by other means.

More sophisticated examples:

• https://artofproblemsolving.com/community/p1847194

• https://artofproblemsolving.com/community/p422893

Answer 4

Looking for a reference to this question I have realized that there are important applications of Lagrange's inversion formula in asymptotical analysis (although its role in the implicit function theorems is already noted by Andres Caicedo). N.G. de Bruijn's Asymptotic Methods in Analysis, Section 2.3, gives some explicit examples: for instance, one can use the Lagrange inversion for computing the asymptotics of the positive root of the equation $xe^x=1/t$ as $t\to\infty$.

Answer 5

An elementary proof of Rodrigues' formula for Legendre polynomials (which is usually done via the orthogonality properties of the polynomials). If we define the polynomials by the classical generating function,

$$ \frac{1}{\sqrt{1-2z_{0}w+w^{2}}}=\sum_{n=0}^{\infty}P_{n}\left(z_{0}\right)w^{n} $$

and consider the solution $z(w)$ of $$w=f(z)=2\frac{z-z_{0}}{z^{2}-1}$$ fixed by $z(0)=z_0$, then the direct application of the Lagrange's formula (formulated for the solution $z(w)$ of the equation $w=f(z)$ with $w_0=f(z_0)$) $$\frac{\Phi\left(z\left(w\right)\right)}{1-\left(w-w_{0}\right)\left.\frac{\mathrm{d}}{\mathrm{d}z}\left(\frac{z-z_{0}}{f(z)-w_{0}}\right)\right|_{z=z(w)}}=\sum_{n=0}^{\infty}c_{n}\left(w-w_{0}\right)^{n},\quad c_{n}=\frac{1}{n!}\left.\frac{\mathrm{d}^{n}}{\mathrm{d}z^{n}}\left[\Phi\left(z\right)\left(\frac{z-z_{0}}{f(z)-w_{0}}\right)^{n}\right]\right|_{z=z_{0}}$$ to $f(z)$, $w_0=f(z_0)=0$ and $\Phi(z)\equiv 1$ gives $$P_{n}(z)=\frac{1}{2^{n}n!}\frac{\mathrm{d}^{n}}{\mathrm{d}z^{n}}\left[\left(z^{2}-1\right)^{n}\right].$$

Answer 6

The reps of the Lagrange inversion formula (LIF) in different “coordinate systems” are intrinsically interesting.

Consider a compositional inverse pair of functions, $h$ and $h^{-1}$, analytic at the origin with $h(0)=0=h^{-1}(0)$.

Then with $\omega=h(z)$ and $g(z)=1/[dh(z)/dz]$,

$$\exp \left[ {t \cdot g(z)\frac{d}{{dz}}} \right]f(z) = \exp \left[ {t\frac{d}{{d\omega }}} \right]f[{h^{ - 1}}(\omega )] = f[{h^{ - 1}}[t + \omega]] = f[{h^{ - 1}}[t + h(z)]],$$ so $$\exp \left[ {t \cdot g(z)\frac{d}{{dz}}} \right]z |_{z=0}=h^{-1}(t)$$

(see OEIS A145271 and A139605 for more relations).

With the power series rep $h(z)= c_1z + c_2z^2 + c_3z^3 + ... ,$

$$\frac{1}{5!}[g(z)\frac{d}{{dz}}]^{5}z|_{z=0} = \frac{1}{c_1^{9}} [14 c_2^{4} - 21 c_1 c_2^2 c_3 + c_1^2[6 c_2 c_4+ 3 c_3^2] - 1 c_1^3 c_5],$$

which is the coefficient of the fifth order term of the power series for $h^{-1}(t)$. This is related to a refined f-vector (face-vector) for the 3-D Stasheff polytope, or 3-D associahedron, with 14 vertices (0-D faces), 21 edges (1-D faces), 6 pentagons (2-D faces), 3 rectangles (2-D faces), 1 3-D polytope (3-D faces).

This correspondence between the refined f-vectors of the n-Dim Stasheff polytope, or associahedron, and the coefficients of the (n+2) term of the compositional inverse holds in general, (see A133437, inversion for power series, and compare with A033282, coarse f-vectors for associahedra, and with MO-6373). These refined partition polynomials are also a refined presentation of the number of diagonal dissections of a convex n-gon (A033282) or, equivalently, the refined numbers for a set of Schroeder lattice paths (A126216), which sum to the little Schroeder numbers (A001003).

If $h(z)$ is presented as a Taylor series, the LIF A134685 is obtained, which is related to the tropical Grassmannian G(2,n) and phylogenetic trees (A134991) and to the partitioning of 2n elements into n groups.

When the invertible function $h(t)$ is represented as a power series of its own reciprocal, $t/h(t)$, the refined Narayana numbers are obtained (A134264), which are the refined h-polynomials of the simplicial complexes (A001263) dual to the Stasheff associahedra and also a refined enumeration of a set of Dyck lattice paths A125181 and noncrossing partitions, which sum to the Catalan numbers A000108.

Also, the "infinitesimal generators" A145271 for these reps have very interesting associations (e.g., to permutahedra, surjections, and multiplicative reciprocals A019538/A049019, for the LIF A134685) and allow reps of the partition polynomials for A133437 as colored umbral binary trees related to refined Lah polynomials.

To illustrate an important application, you might look at OEIS-A074060 "Graded dimension of the cohomology ring of the moduli space of n-pointed curves of genus 0 satisfying the associativity equations of physics (also known as the WDVV equations)," as well as links in the LIF entries, to relate Lagrange inversion (or, equivalently, the Legendre transform) of series to the cohomology of moduli spaces.

For a less fancy application, the LIFs can sometimes be used, just as other transforms, such as the Fourier transform, to jump between "reciprocal" domains to simplify expressions to solve a problem, e.g., in conjunction with the OEIS to suggest generating functions for integer arrays by looking at their compositional inverses numerically.

Update 7/23/2021:

First, a comment on the quintic equation:

Newton developed a formula for 'Lagrange inversion' of power series, writing down the first few inversion polynomials of A133437, related, as I note above, to the faces of the associahedra, so he had already an expression to solve $0 = a - (x -t \; x^n)$, i.e., to find the inverse of $f(x) = x-t\;x^n$. Certainly, he would have tested his formula on such simple polynomials, but not being aware of the combinatorial / geometric import of the coefficients (the Fuss-Catalan number sequences) and having bigger fish to fry, he had little motivation to publish such results.

On the inversion of the equation, the F-C numbers, and combinatorial interpretations of the Lagrange inversion polynomials:

The families of LIFs above, derived from different series reps of the source, infinitesimal generator, and target, can be used to give diverse combinatorial interpretations of the coefficients of the compositional inverse about the origin of

$$ y = f(z) = z - tz^n.$$

As I mentioned above, the sequences of inversion coefficients, varying with $n$, are the Fuss-Catalan families. The first few are the Catalan numbers A000108 for $n-2$; A001764; and A002293 for $n=3$.

The associated infinigen is

$$g(z)\partial_z= \frac{1}{f'(z)} \; \partial_z =\frac{1}{1-n\;t \;z^{n-1}} \; \partial_z. $$

The Fuss-Catalan families themselves are the nonvanishing coefficients of the inversion polynomials of A133437 when appied to $f(x)$ for the inverse o.g.f. of an o.g.f. (formal power series). The only nonzero indeterminate in the partition polynomials other than $c_1 = 1$ is $c_n = -t$. The polynomials are refined versions of the face polynomials of the associahedra with each term in bijection with a distinct face type (vertex, edge, pentagon, square, etc.) and can be regarded as refined Euler characteristic polynomials. A plethora of other combinatorial models are related to these coefficients (see this MO-Q for more guises of the associahedra).

For the inversion polynomials of A134685 for the inverse e.g.f. (formal Taylor series) of an e.g.f. (polynomials used by Theremin in 1855 and Schroeder in 1870 to find zeros of functions), the only nonzero indeterminate in the polynomials other than $c_1 = 1$ is $c_n = -n!\;t$. The $m$-th partition polynomial encodes the number of ways to partition $2(m-1)$ labeled items into $(m-1)$ groups in which the order of the items doesn't matter, so they can be associated with a combinatorial urn problem. However, when these LIF coefficients are weighted by powers of $n!$, the interpretation changes. When $n=2$, the inversion polynomials evaluate to A001813 for $(2k)!/k!$, and for $n=3$, aerated A064350 for $(3k)!/k!$, giving the number of ways of placing $3k$ labelled items into $k$ boxes each containing 3 bins in which the linear order of the items in the bins matters (see Critzer's comment in the entry).

For A134264 for the inverse o.g.f. in terms of the coefficients of the shifted reciprocal

$\frac{x}{f(x)} = h_0 + h_1 x + h_2 x^2 + \ldots$,

the indeterminates are determined by

$$\frac{1}{1-t \;x^{n-1}}= 1 + t \; x^{n-1} + t^2 \;x^{2(n-1)} + t^3 \;x^{3(n-1)}+ \dots,$$

so $h_{m(n-1)} = t^m$ for $m=0,1,2,\ldots$ are the only nonvanishing indeterminates. The partition polynomials then evaluate to a refinement of each number in the Fuss-Catalan families and have interpretations in terms of Dyck lattice paths and ordered trees (see A125181), noncrossing partitions, polygon dissections, and primitive parking functions, among other combinatorial constructs (see this MO-Q). In addition, these polynomials, sometimes dubbed the Voiculescu polynomials, play an integral role in free probability theory and allied subjects, such as integration over families of random matrices.

Each LIF polynomial has probably more than one representation as a forest of trees. See "The combinatorics of functional composition and inversion" by Parker, "An inversion theorem for labeled trees and some limits of areas under lattice paths" by Drake, "Formal group laws and hypergraphs" by Jair, and "Inversion of integral series enumerating planar trees" by Loday for related discussions.

As noted above the inversion polynomials provide the series for a flow function

$F(t,z) = \exp[\;t \; g(z) D_z \;] z= f_{a \; branch}^{(-1)}(t + f(z))$

associated with the classic flow ODE

$\frac{df^{(-1)}(x)}{dx} = g(f^{(-1)}(x))$

with $F(t,F(u,z)) =F(t+u,z)$ and $g(z) = 1/f'(z)$,

and so are related to algebraic and geometric Lie theory and integration, e.g., Butcher series. Theremin and Schroeder implicitly (or almost explicitly--they don't discuss flow equations per se, only the series rep) use these connections to give the zeros of quadratics and higher order polynomials by setting $t = -f(z)$.

These inversion polynomials weasel their way into classical and quantum physics and higher algebra via various paths. They are the antipodes, or Zimmerman forest formulas, in combinatorial Faa di Bruno type Hopf algebras characterizing composition, so are related to summation of Feynman diagrams and the renormalization group of quantum field theory and statistical physics. The polynomials also weasel their way into classical and quantum dynamics via the connection between compositional inversion and the Legendre transform (in fact, convolutional properties of the polynomials, the inviscid Burgers-Hopf equation, and the Legendre transform are intertwined) and into abstract algebra through the theory of quadratic operads via dualities connected to compositional inversion, and more niches.

Answer 7

Look at I2.24 (an exercise!) in the book I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd Ed., Clarendon Press, Oxford, 1995.

Let $\lambda$ be a partition. Then for sufficiently large $n$ there is a corresponding conjugacy class $K_\lambda(n)$ of $S_n$ (got by ignoring $1$'s in $\lambda$). Use $+$ to denote the sum of the elements in the group algebra ${\mathbb Q}S_n$, we may write $$ K_\lambda(n)^+K_\mu(n)^+=\sum_\nu c_{\lambda,\mu}^\nu(n)K_\nu(n)^+, $$ where the $c_{\lambda,\mu}^\nu(n)$ are non-negative integers that depend on all $3$ partitions and on $n$. Say that each element of $K(\lambda)$ can be written as a product of $\ell(\lambda)$ transpositions, but no fewer. Throw away the $\nu$ for which $\ell(\nu)<\ell(\lambda)+\ell(\mu)$. Then the resulting $c_{\lambda,\mu}^\nu(n)=c_{\lambda,\mu}^\nu$ are independent of $n$ (H. K. Farahat, G. Higman, The centres of symmetric group rings, Proc. Royal Soc. London A 250 (1959) 212-221.).

Now let $H(t)=\prod_{i=1}^\infty(1-tx_i)^{-1}$ be the generating function for the complete symmetric functions. Suppose that $H(t)$ has Lagrange inverse $H^*(t)=\sum_{n=0}^\infty h_n^*t^n$. Then the corresponding symmetric functions $h_n^* $ are algebraically independent. Set $h_\lambda^*=\prod h_{\lambda_i}^*$.

Denote the dual (w.r.t. the usual symmetric bilinear form on symmetric functions) of $h_\lambda$ by $K_\lambda$, for each partition $\lambda$. Then Macdonald shows that the $K_\lambda$ form a basis for symmetric functions whose multiplication constants are: $$ K_\lambda^+K_\mu^+=\sum_\nu c_{\lambda,\mu}^\nu K_\nu. $$

Answer 8

Because it lies squarely at the crossroads of analysis, algebra, combinatorics, geometry / topology, and physics, I would whet the appetite of the students with the generalized Lagrange inversion formula, which gives the compositional inverse about the origin in $z$ or about the point at infinity, for $m = \pm 1, \pm 2 , \pm 3,...$, i.e., $m$ any integer but $0$, of

(I)

$$f(z) = z + z^{m+1}$$

and, more generally, for the power series ($m > 1$) or Laurent series ($m <1$)--the generalized Lagrange inversion formula doesn't care--

(II)

$$f(z) = z \;(1 + u_1 z^{1m}+ u_2 z^{2m} + u_3 z^{3m} + \cdots) $$

for an infinite set of commuting indeterminates $u_n$.

The solutions to (I) generate the aerated signed $(m)$-Fuss-Catalan sequences of number with associated combinatorial models whereas the solutions to (II) generate the $(m)$-associahedra partition polynomials rife with combinatorial models, whose diagonal coefficients are the signed $(m)$-Fuss-Catalan numbers. A change in signs of this generalized Lagrange inversion formula then generates the $(m)$-noncrossing partitions polynomials / $(m)$-Narayana polynomials, with all the associated combinatorial models of the noncrossing partitions for $m >0$ and other combinatorial models for the inverse noncrossing partitions for $m < 1$. For $m=0$, the set $[A^{(0)}]=[R]$, the refined binomial, or refined Pascal, partition polynomials are generated, which are the partition polynomials for multiplicative inversion of power series or ordinary generating function. Ardila has given a combinatorial model of $[R]$ as sprigs. The change in sign of $m$ manifests itself in the analytics and combinatorics as an iconic reciprocity involving the falling and rising factorial polynomials via the binomial expansion of the generalized LIF.

The generalized LIF (a special Lagrange-Schur-Jabotinsky identity) is

$$P^{(m,\pm 1)}_{n}(u_1,...,u_n) = \frac{\partial_{x=0}^{n|m|}}{(n|m|)!}\frac{[1+ u_1x^{1|m|} +u_2 x^{2|m|} + u_3 x^{3|m|} + \cdots + u_n z^{n|m|}]^{\pm(mn+1)}}{mn+1},$$

with

$P^{(m,-1)}_{n}(u_1,,..,u_n) = A^{(m)}_n(u_1,...,u_n)$,

the $(m)$-associahedra polynomials

and

$P^{(m,1)}_{n}(u_1,,..,u_n) = N^{(m)}_n(u_1,...,u_n)$,

the $(m)$-noncrossing partitions / Narayana polynomials.

A generalized face-h polynomial identity / raising-lowering identity is manifested as the substitution identity, underlying some of the combinatorics,

$$ [A^{(m)}] = [N^{(m)}][A^{(0)}]=[N]^m[R] = [N][A^{(m-1)}]$$

or

$$[N]^{-1} [A^{(m)}] = [A^{(m-1)}]$$

and, conversely,

$$ [A^{(m)}][R] = [N]^m.$$

One implication is the the absolute values of the sums of the coefficients of the polynomials $[P^{(m,\pm1)}]$ are the absolutes of the diagonals, i.e., coefficients of the top order monomials, of $[P^{(m,\mp1)}]$, connecting the $(m)$-Fuss-Catalan and the $(m)$-Fuss-Narayana numbers.

More on the combinatorics in the refs in this MO-Q.

Switch to e.g.f.s for a parallel story with the refined $(m)$-Eulerian polynomials, $[E^{(m)}]$, and the $(m)$-Lagrange polynomials, $[L^{(m)}]$, playing the roles of $[N^{(m)}]$ and $[A^{(m)}]$, respectively, with $[L^{(0)}] = [P]$ being the set of permutahdra polynomials for multiplicative inversion of e.g.f.s. The combinatorics now involve among other constructs the hypersimplices, the permutahedra, and the tropical Grassmannians $G(2,n)$.

If you wish, you could introduce the symmetric functions a la Macdonald and the free $\lambda$ ring in one variable. His involutions include $[A^{(-1)}]$, $[A^{(0)}]$, and $[A^{(1)}] = [A]$.

(This goes back to the beginnings of analysis with Isaac Newton; he presented the first few polynomials for $[A]$ and $[A^{(2)}]$ in a letter to Oldenburg in 1676, and in other correspondence, of course, the Newton identities, the binomial expansion, and Stirling polynomials of the first kind, a.k.a. the falling factorial polynomials, ... .)

Answer 9

There are plenty of uses of the Lagrange inversion formula in the following paper in statistics 'Letac, G. and Mora, M. (1990) 'Natural exponential families with cubic variances.' Ann. Statist. 1-37.'