nLab
Lambert W-function

The Lambert WW function

Idea

In complex analysis, the Lambert WW-function is a multi-branched function inverse to the function f(z)=ze zf(z) = z e^z. Among other things, it is important in the enumeration of tree-like structures, for instance rooted trees, and in the combinatorial study of the Lagrange inversion formula.

We have W(z)e W(z)=zW(z) e^{W(z)} = z. In a neighborhood of z=0z = 0, we may develop W(z)W(z) as a formal power series, and there is a quite remarkable formula:

W(z)= n=1 (n) n1z nn!. W(z) = \sum_{n = 1}^{\infty} \frac{(-n)^{n-1} z^n}{n!} .

A proof of this formula is sketched below.

Lambert WW and rooted trees

Let R(X)R(X) be the species of rooted trees. Choosing a structure of rooted tree TT (on a finite set of vertices) amounts to

  • Choosing one vertex to serve as the root of TT;

  • Choosing a structure of “rooted forest” (a disjoint collection of rooted trees) on the complement of the root.

The idea is that given a rooted forest, we get a rooted tree by adding in a new vertex (which serves as root) and drawing an edge from each root of the forest to the new vertex.

This observation leads to the structural isomorphism

R(X)=Xexp(R(X)) R(X) = X \otimes \exp(R(X))

Let R(x)= n0a nx nn!R(x) = \sum_{n \geq 0} \frac{a_n x^n}{n!} be the formal power series corresponding to the generating function of R(X)R(X), so that a na_n counts the number of rooted trees on nn vertices. We may call R(x)R(x) the cardinality of R(X)R(X). One has the analogous decategorified formula

R(x)=xe R(x)R(x) = x e^{R(x)}

or

R(x)e R(x)=xR(x) e^{-R(x)} = x

which means, after a short series of algebraic manipulations, that R(x)R(x) is related to the Lambert WW function as follows:

R(x)=W(x).R(x) = - W(-x).

Counting rooted trees

The number of possible rooted tree structures on nn labeled vertices is n n1n^{n-1}. We sketch Joyal’s beautiful proof of this fact; it follows that

W(x) = R(x) = n1n n1(x) nn! = n1(n) n1x nn!\array{ W(x) & = & - R(-x) \\ & = & - \sum_{n \geq 1} \frac{n^{n-1} (-x)^n}{n!} \\ & = & \sum_{n \geq 1} \frac{(-n)^{n-1} x^n}{n!} }

as claimed earlier.

In fact, Joyal counts the number of bipointed trees (trees equipped with an ordered pair of vertices, possibly the same one), and shows this is the same as the number of endofunctions on an nn element set. Since this is n nn^n, and since the number of ordered pairs of vertices is n 2n^2, it follows that the number of tree structures on an nn-element set is n n2n^{n-2}, a result referred to as Cayley’s theorem. Therefore the number of rooted trees is nn n2=n n1n \cdot n^{n-2} = n^{n-1}.

For a bipointed tree TT, let the ordered pair of vertices be (t,h)(t, h) where tt is called a tail and hh a head. The set of vertices on the unique path from tt to hh is endowed with a linear order (namely, the order in which they appear on the path, with tt first). We call this ordered set the spine of the bipointed tree. At the same time, each vertex vv along the spine is the root of a rooted tree T vT_v: a full subgraph where a vertex ww of TT belongs to T vT_v if the unique path from ww to hh first meets the spine at vv.

A choice of bipointed tree structure on a finite set SS can thus be equivalently described as follows:

  • Partition SS into one or more subsets (which are equivalence classes);

  • Choose a rooted tree structure on each class (if the root is vv, this tree structure will be T vT_v);

  • Choose a way of linearly ordering the equivalence classes (which is really the same as linearly ordering the roots).

If LL is the species of linearly ordered sets, and RR is the species of rooted trees, this way of describing bipointed trees establishes an explicit bijection between LRL \circ R and the species of bipointed trees.

For an endofunction f:SSf \colon S \to S, let KK be the intersection of images of iterates f (n)(S)f^{(n)}(S). It is immediate that the restriction f:KKf\colon K \to K is a surjection and therefore a bijection (permutation). Picturing an endofunction as a graph (where an edge is drawn between ss and f(s)f(s)), each vertex vKv \in K is the root of a rooted tree T vT_v: a full subgraph where a vertex ww belongs to T vT_v if f (n)(w)=vf^{(n)}(w) = v for some nn, but f (k)(w)f^{(k)}(w) does not belong to KK for k<nk \lt n.

A choice of endofunction structure on SS can thus be equivalently described as follows:

  • Partition SS into one or more subsets (equivalence classes);

  • Choose a rooted tree structure on each class (if the root is vv, this tree structure is T vT_v);

  • Choose a permutation on the set of equivalence classes (tantamount to a permutation of the roots vv).

If PP is the species of permutations, and RR the species of rooted trees, this establishes an explicit bijection between PRP \circ R and the species of endofunctions.

Since the species LL of linear orderings and the species PP of permutations have the same cardinality, it follows that the species LRL \circ R and PRP \circ R also have the same cardinality, which is to say that the number of bipointed tree structures on SS equals the number of endofunctions, as was to be proved.

Revised on August 2, 2012 10:23:37 by Toby Bartels (98.16.162.107)