Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
Have you checked Bergeron, Labelle, and Leroux? Maybe Flajolet and Sedgewick? –  Qiaochu Yuan Jul 16 '10 at 1:39
1  
I can suggest looking at Christian Krattenthaler's papers (mat.univie.ac.at/~kratt/papers.html). It looks like $q$-Lagrange inversions have much more applications. –  Wadim Zudilin Jul 16 '10 at 1:48
    
Have you looked at Krantz-Parks, "The Implicit Function Theorem"? I don't remember whether they give references to combinatorial applications. –  Andres Caicedo Jul 16 '10 at 6:04
2  
A good survey paper is Lagrange Inversion by Josef Hofbauer, Seminaire Lotharingien de Combinatoire B06a (1982) –  Johann Cigler Jul 17 '10 at 16:17
1  
I got some very good hint answers in a similar questions time ago: mathoverflow.net/questions/25491/… –  Pietro Majer Oct 23 '11 at 10:29

7 Answers 7

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.

share|improve this answer
6  
Just as the generating function identity c = 1 + xc^2 defines binary trees, the generating function identity c = 1 + xc^n defines n-ary trees, and there is a proof of the closed formula for the Catalan numbers which generalizes to n-ary trees. The rest is just a change of variables, as far as I can tell. –  Qiaochu Yuan Jul 17 '10 at 6:10
16  
The application to the quintic has a very interesting history. It was first discovered by Lambert in 1757 (before Lagrange, and before the Bring-Gerrard reduction of the quintic was known), rediscovered by Eisenstein when he was 14 (!) and later mentioned by him in a footnote to an 1844 paper. –  John Stillwell Jul 17 '10 at 11:26
2  
Thank you, John! I was hoping that you would come along and comment on the history. For those who don't know: John Stillwell wrote an article "Eisenstein's footnote" in the Math Intelligencer explaining the history. Unfortunately, I couldn't view the whole thing, but here is the first page: resources.metapress.com/… –  Victor Protsak Jul 17 '10 at 18:02
6  
Hi Thierry, it was a figure of speech, but it reflects my frustration with what might be called "the mythology of mathematics". While impossibility proofs receive a good deal of emphasis, very ingenious constructions, such as the conchoid of Nicomedes (trisection of the angle), the solution of Archytas of the doubling of the cube based on the curve of intersection of a cylinder and a degenerate torus, and, of course, Hermite's and Eisenstein's formulas for the quintic have become obscure and many mathematicians don't even learn about them any more. –  Victor Protsak Feb 24 '11 at 4:58
3  
Another combinatorial interpretation: it's the generalization of counting triangulations of a polygon where instead of triangles you tile with quadrilaterals, pentagons, etc. The quintic case counts hexagons.$$ $$ While I'm at it: see the "one-page papers" catalan and catalan2 at math.harvard.edu/~elkies/Misc/index.html#papers for elementary derivations of these power series without Lagrange or residue calculus. –  Noam D. Elkies Nov 29 '11 at 0:06
  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.)

share|improve this answer
2  
I just tried skimming through that part of Hirzebruch. I wasn't able to tell whether that lemma is important for the proof of H-R-R? –  Kevin H. Lin Jul 16 '10 at 18:39

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.