Combinatorial interpretation of series reversion coefficients

Question

In a recent paper studying some generalizations of Stirling numbers, my coauthors and I needed the following result:

If $f(x)=\sum_{n \geq 1} a_n x^n/n!$ is a power series with $a_1 \neq 0$, and $g(x) = \sum_{n \geq 1} b_n x^n/n!$ is its series reversion (so $f(g(x))=g(f(x))=x$), then $$ b_n = \sum_{T} w(T) $$
where the sum is over phylogenetic trees on $\{1, \ldots, n\}$. Here a phylogenetic tree on $\{1,\ldots, n\}$ is a rooted tree with $n$ leaves, no vertex with exactly one child, and leaves labelled from the set $\{1, \ldots, n\}$ (but no other vertex receiving a label); see page 3 of the paper linked above for a picture. The weight $w(T)$ is computed as follows: if $T$ has $n$ leaves and $m$ non-leaves then $$ w(T) = (−1)^m a_1^{-(m+n)} \prod \{a_{d(v)}: v~\mbox{a non-leaf}\} $$ where $d(v)$ denotes the number of children of $v$ (and when $n=1$ the isolated vertex is considered a leaf).

The proof is short, and this feels like something that should have been written down prior to now, but we could find no reference.

Question: Has the above result appeared in the literature?

(There is a paper of Chen from 1990 with a similar result but with a distinctly different and not obviously equivalent formulation. Chen shows that $b_n$ is a weighted sum over Schroeder trees: trees on $n$ labelled vertices (as opposed to leaves), with no restriction on numbers of children, in which each non-leaf is endowed with an ordered partition of its children. The count of Schroeder trees by number of vertices is A053492. The count of phylogenetic trees by number of leaves is A000311.)

Answer 1

Yes, this is known. As Tom Copeland mentioned, this is in Drake's thesis, Example 1.4.7.

Drake gives a broad generalization of your result. His main theorem (Theorem 1.3.3) is roughly as follows. Suppose you have an alphabet $A$ of certain trees, and a set $L$ of 'allowed links' between them, ways of connecting the root of one to a leaf of another. Let $S(L,n)$ be the set of all trees $T$ with $n$ leaves labeled bijectively $1, \ldots, n$ with no other nodes labeled with the property that $T$ made up of the letters $A$ with only links between them which are in $L$. Say each tree $T \in A$ has a weight $w(T)$, and a tree made up of letters $T_1, \ldots, T_n \in A$ with certain links between them has weight $w(T_1) \cdots w(T_n)$. Let $$F(x) = \sum_{n=1}^\infty a_n \frac{x^n}{n!}$$ where $a_n = \sum_{T \in S(L,n)} w(T)$. Then the compositional inverse is $$F^{-1}(x) = \sum_{n=1}^\infty b_n \frac{x^n}{n!}$$ where $$b_n = \sum_{T \in S(\bar{L},n)} (-1)^{m(T)} w(T).$$ Here $m(T)$ is the number of letters in $A$ that $T$ is composed of, and $\bar{L}$ is the complement of $L$ in the set of all possible links between elements of $A$.

This was an extension of the work of Susan Parker, who had a similar theorem using ordinary generating functions. Parker's result can, in turn, be seen as a generalization of a result of Carlitz, Scoville and Vaughan. Ira Gessel's slides may be helpful.

To get your theorem, let $A$ be the set of "simple" trees, the trees $T_n$, $n > 1$, so that $T_n$ is a tree with the root having the $n$ leaves $1,2, \ldots, n$ as children. Let $w(T_n) = t_n$ (an indeterminate). Let $L$ be the empty set of links. Then $$F(x) = x + t_2\frac{x^2}{2!} + t_3 \frac{x^3}{3!} + \cdots$$ since $S(L,n) = \{T_n\}$ for $n>1$, and $S(L,1)$ consists of the tree with one node which is always allowed (and has weight $1$).

Then by Drake's inversion theorem, $$F^{-1}(x) = \sum_{n=1}^\infty b_n \frac{x^n}{n!}$$ where $$b_n = \sum_{T \in S(\bar{L},n)} (-1)^{m(T)} w(T)$$ is the sum of the weights of all phylogenetic trees (since $\bar{L}$ is the set of all links.)

See also my thesis, which contains a different generalization of your result. The phylogenetic trees (also called total partitions) are mentioned in Section 3.2

Answer 2

This result can also be found as Theorem 3.3.9 in Ginzburg-Kapranov: "Koszul duality for operads" (Duke Math J 1994). Set $r=1$ in their result and rescale so that $a_1=1$. They had discovered it independently, but thank D. Wright for informing them that the result was known before due to J. Towber. They also give a reference to Wright: "The tree formulas for reversion of power series" (JPAA 1989), where this result appears as Theorem 3.10.

The context of this result in the setting of operads is that any dg operad $P = \{P(n)\}$, say with $P(0)=0$ and $P(1)$ a copy of the base field, has a generating series which encodes the Euler characteristics of the chain complexes $P(n)$. The generating series of $P$ is the compositional inverse of the generating series for the "bar construction" on the operad $P$. The bar construction of operads is defined by a sum over trees whose internal vertices are decorated by the chain complexes of the operad $P$; in fact, the trees involved are exactly those that you call phylogenetic trees.

Answer 3

See these three papers and references therein:

https://arxiv.org/abs/math/0208174

https://arxiv.org/abs/math/0208173

http://www.emis.de/journals/SLC/wpapers/s49abdess.html

Going from one type of tree to another is no big deal in the framework of Joyal's theory of combinatorial species. Types of trees correspond to certain functors between finite sets and for each such functors there is an associated exponential generating series. Changing from say planar trees to Cayley trees is a morphism of functors and there is a precise theorem which says what happens then to the generating series (Theorem 8 in the last paper I listed).