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:

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1847194#p1847194

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=422893#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

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 presentation of a set of Dyck lattice paths A125181, 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.

Answer 6

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.'

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. $$