In complex analysis, the Lambert -function is a multi-branched function inverse to the function . 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 . In a neighborhood of , we may develop as a formal power series, and there is a quite remarkable formula:
A proof of this formula is sketched below.
Let be the species of rooted trees. Choosing a structure of rooted tree (on a finite set of vertices) amounts to
Choosing one vertex to serve as the root of ;
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
Let be the formal power series corresponding to the generating function of , so that counts the number of rooted trees on vertices. We may call the cardinality of . One has the analogous decategorified formula
which means, after a short series of algebraic manipulations, that is related to the Lambert function as follows:
The number of possible rooted tree structures on labeled vertices is . We sketch Joyal’s beautiful proof of this fact; it follows that
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 element set. Since this is , and since the number of ordered pairs of vertices is , it follows that the number of tree structures on an -element set is , a result referred to as Cayley’s theorem. Therefore the number of rooted trees is .
For a bipointed tree , let the ordered pair of vertices be where is called a tail and a head. The set of vertices on the unique path from to is endowed with a linear order (namely, the order in which they appear on the path, with first). We call this ordered set the spine of the bipointed tree. At the same time, each vertex along the spine is the root of a rooted tree : a full subgraph where a vertex of belongs to if the unique path from to first meets the spine at .
A choice of bipointed tree structure on a finite set can thus be equivalently described as follows:
Partition into one or more subsets (which are equivalence classes);
Choose a rooted tree structure on each class (if the root is , this tree structure will be );
Choose a way of linearly ordering the equivalence classes (which is really the same as linearly ordering the roots).
If is the species of linearly ordered sets, and is the species of rooted trees, this way of describing bipointed trees establishes an explicit bijection between and the species of bipointed trees.
For an endofunction , let be the intersection of images of iterates . It is immediate that the restriction is a surjection and therefore a bijection (permutation). Picturing an endofunction as a graph (where an edge is drawn between and ), each vertex is the root of a rooted tree : a full subgraph where a vertex belongs to if for some , but does not belong to for .
A choice of endofunction structure on can thus be equivalently described as follows:
Partition into one or more subsets (equivalence classes);
Choose a rooted tree structure on each class (if the root is , this tree structure is );
Choose a permutation on the set of equivalence classes (tantamount to a permutation of the roots ).
If is the species of permutations, and the species of rooted trees, this establishes an explicit bijection between and the species of endofunctions.
Since the species of linear orderings and the species of permutations have the same cardinality, it follows that the species and also have the same cardinality, which is to say that the number of bipointed tree structures on equals the number of endofunctions, as was to be proved.