How to Count n-Ary Trees
Posted by John Baez
How do you count rooted planar -ary trees with some number of leaves? For this puzzle leads to the Catalan numbers. These are so fascinating that the combinatorist Richard Stanley wrote a whole book about them. But what about ?
I’ll sketch one way to solve this puzzle using generating functions. This will give me an excuse to talk a bit about something called ‘Lagrange inversion’.
By the way, a mentally ill person may post lots of strange comments here under various names — perhaps even under my name. Please don’t engage with him, or even discuss this issue here, since it will only worsen his illness. Just ignore him and talk about the math.
You can define a rooted planar binary tree recursively by this equation:
This means “to make a set into the leaves of a binary tree, it should either be the one-element set or the leaves of a pair of binary trees”. You can then solve this using the quadratic formula and get
where the numbers here are the Catalan numbers. For example, there are 5 binary trees with 4 vertices. For more details and more rigor go here.
We can define rooted planar -ary trees by a similar equation:
Bu how do we solve this when ? Even for or , where we could use the cubic or quartic equation, we don’t really want to.
The trick is to use Lagrange inversion. Given a formal power series
normalized with to make things simple, Lagrange inversion tells us a formal power series that’s the inverse of with respect to composition:
Here’s how it works. Let’s write
Then , and the Lagrange inversion theorem says that for we have
where
and the rising powers are defined by
But the main ingredient in this formula is the Bell polynomials . These are named after Eric Temple Bell, author of a science fiction series about a planet where mathematics is done only by men.
It seems easiest to explain the Bell polynomials with an example. is a polynomial in variables. It keeps track of all the ways you can partition an -element set into disjoint nonempty subsets, called blocks. For example:
This says that if we partition a 6-element set into 2 blocks there are:
- 6 ways to partition it into a block of size 5 and a block of size 1
- 15 ways to partition it into a block of size 4 and a block of size 2
- 10 ways to partition it into two blocks of size 3.
and those are all the ways!
So, if you know all the Bell polynomials, you know how many ways there are to partition any finite set into some chosen number of blocks of some chosen sizes.
The formula for Lagrange inversion is intimidating yet intriguing, and that’s what I really want to understand. But for now let’s just apply it to count -ary trees. We’re trying to solve
or in other words
for . So we make up a function
and we seek the inverse power series : this will give us as a power series in .
The first coefficient of is , not , so we’ll need to tweak the formula for Lagrange inversion. Luckily this will just get rid of the sign that appeared in that formula.
Actually I’ll skip the detailed calculation, which is much less fun to read than to do yourself. The main point is that Lagrange inversion does the job. I’ll just give you the answer:
So, the number of rooted planar -ary trees with leaves should be
As a sanity check, note that an -ary tree always has leaves for some natural number , because it can either have leaf (the root), or we can stick a sprout with leaves on an existing leaf, thus adding new leaves.
Also note that when we get our friends the Catalan numbers!
So this is pretty cool, and it raises tons of interesting questions, mostly about the deep inner meaning of Lagrange inversion. Richard Stanley wrote about this in Section 5.4 of the second volume of Enumerative Combinatorics, André Joyal wrote about it in Theorem 2 of Une théorie combinatoire des séries formelles (with a partially finished English translation here), and Flajolet and Sedgewick wrote about it in Appendix A.6 of Analytic Combinatorics. So there’s a lot of material to read! But I find all these discussions puzzling, so I’m trying to dig deeper and find an explanation that’s easier to grasp. Luckily Todd Trimble knows a lot about this subject, and it’s very beautiful! So stay tuned.
Re: How to Count n-Ary Trees
Three OEIS hubs for notes/refs on compositional inversion of analytic functions and formal power series that are related to variants of Lagrange inversion formulas are OEIS A145271, A133437 (an e.g.f. variant of the o.g.f. A111785), and A134264. There are numerous combinatorial models (see, e.g., Guises of the Stasheff polytopes, associahedra for the Coxeter A_n root system?) for A111785 and Guises of the noncrossing partitions (NCPs) / refined Narayana polynomials) for A134264). The tree model dates back to Arthur Cayley (1857, see simple core cases in my pdf Mathemagical Forests) based on observations of a relation between compositional inversion and iterated derivatives by Charles Graves (1853, see two of my Math Overflow answers here and here.). The degenerate case of inverting with any integer is sketched in my answer to the MO-Q A combinatorial interpretation for n-ary-trees for-negative n.