Combinatorial interpretation of series reversion coefficients

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.


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


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