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

  • $\begingroup$ How does this compare with oeis.org/A134685 and the reduced array oeis.org/A134991? $\endgroup$ – Tom Copeland Jan 11 '17 at 21:06
  • 1
    $\begingroup$ The rows of OEIS A134991 count the number of phylogenetic trees with a particular number of leaves by number of non-leaf vertices. A000311 gives the row sums, so the total number of phylogenetic trees with a particular number of leaves. I'm not sure about A134685. $\endgroup$ – David Galvin Jan 11 '17 at 21:16
  • $\begingroup$ Where does the connection with $a_n$ appear on the RHS of your result for $b_n$? $\endgroup$ – T. Amdeberhan Jan 11 '17 at 22:36
  • $\begingroup$ Possibly relevant: people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf. $\endgroup$ – Tom Copeland Jan 11 '17 at 22:48

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

  • $\begingroup$ Nice. Welcome to MO. (I would really like to see a paper on the connections among your conclusions, Dan Petersen's, and the combinatorics of Whitehouse simplicial complexes and associahedra (and dg Hopf algebras)--all related to trees. Btw, your expansion 9.3 is oeis.org/A145271.) $\endgroup$ – Tom Copeland Jan 16 '17 at 0:40
  • $\begingroup$ @TomCopeland Thanks for the link. I would like to see that as well - I confess I don't know about Whitehouse complexes or Dan Petersen's work. I would be interested to know if you had any thoughts on my Conjecture A on p. 65. $\endgroup$ – Jair Taylor Jan 16 '17 at 21:21
  • $\begingroup$ Have you nomalized your expansions of 9.4 by dividing out the common factors (1/n), or not, and then searching for the results in the OEIS? Partition polynomials are a little difficult to locate. Try entering the numbers with spaces only, not commas, and scan any hits. $\endgroup$ – Tom Copeland Jan 17 '17 at 3:33
  • $\begingroup$ I believe I've tried searching OEIS for 9.4 in various ways and I didn't come up with anything. However, this was a while ago so I should try again following your advice. Thanks! $\endgroup$ – Jair Taylor Jan 17 '17 at 4:41

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.

  • $\begingroup$ Dan, can you recommend any other articles on the relations in your last paragraph other than the ones I listed in my related MO-Q on comp. Inversion in alg. geom. that you answered? $\endgroup$ – Tom Copeland Jan 18 '17 at 19:30
  • $\begingroup$ Well, there are lots! This fact about generating series of operads and bar constructions gets used all the time. If you search google/google scholar for "ginzburg kapranov functional equation koszul dual" and start digging you'll find plenty of references using this fact. Can you say something more specific about what kind of references you'd like to find? $\endgroup$ – Dan Petersen Jan 20 '17 at 2:55
  • $\begingroup$ Sure. The easiest to read for pedestrians. $\endgroup$ – Tom Copeland Jan 20 '17 at 3:03
  • $\begingroup$ OK - but what is your goal? Do you want to learn about operads? $\endgroup$ – Dan Petersen Jan 20 '17 at 9:49
  • $\begingroup$ Something in the flavor of the youtube video Graded Algebras and the Lagrange Inversion Formula by Dotsenko. $\endgroup$ – Tom Copeland Jan 23 '17 at 13:20

See these three papers and references therein:




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

  • $\begingroup$ Thanks for the references. They establish a broad theory connecting all the different possible interpretations of the series reversion coefficients. But our specific question, does the interpretation in terms of phylogenetic tree appear in the literature, remains unanswered. I don't see anything in the papers you directed us to, or the references, that could serve as a suitable citation to replace a proof of our claim. The claim is not the main point of our paper, just a quite specific auxiliary result that we need. We would like to cite correctly, hence the post. $\endgroup$ – David Galvin Jan 12 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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