The n-Category Café

You can define a rooted planar binary tree recursively by this equation:

$$B \cong x + B^2$$

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

$$B \cong \frac{1 - \sqrt{1 - 4x}}{2} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + \cdots$$

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 $n$-ary trees by a similar equation:

$$T \cong x + T^n$$

Bu how do we solve this when $n \gt 2$? Even for $n = 3$ or $n = 4$, 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

$$\displaystyle{ f(z) = \sum_{k=1}^\infty f_k \frac{z^k}{k!} }$$

normalized with $f_1 = 1$ to make things simple, Lagrange inversion tells us a formal power series $g$ that’s the inverse of $f$ with respect to composition:

$$g(f(z)) = z, \qquad f(g(z)) = z$$

Here’s how it works. Let’s write

$$\displaystyle{ g(z) = \sum_{j=1}^\infty g_j \frac{z^j}{j!} }$$

Then $g_1 = 1$, and the Lagrange inversion theorem says that for $j \ge 2$ we have

$$\displaystyle{ g_j = \sum_{k=1}^{j-1} (-1)^k \; j^{\overline{k}} \; B_{j-1,k}(\hat{f}_1,\hat{f}_2,\ldots,\hat{f}_{j-k}) }$$

where

$$\displaystyle{ \hat{f}_k = \frac{f_{k+1}}{(k+1)} }$$

and the rising powers $j^{\overline{k}}$ are defined by

$$\displaystyle{ j^{\overline{k}} = j(j+1)\cdots (j+k-1) }$$

But the main ingredient in this formula is the Bell polynomials $B_{j,k}$. 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. $B_{j,k}$ is a polynomial in $j-1$ variables. It keeps track of all the ways you can partition an $j$-element set into $k$ disjoint nonempty subsets, called blocks. For example:

$$B_{6,2}(x_1,x_2,x_3,x_4,x_5)=$$ $$6x_5x_1+15x_4x_2+10x_3^2$$

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 $n$-ary trees. We’re trying to solve

$$T = x + T^n$$

or in other words

$$x = T^n - T$$

for $x$. So we make up a function

$$f(z) = z^n - z$$

and we seek the inverse power series $g$: this will give us $T$ as a power series in $x$.

The first coefficient of $f$ is $-1$, not $1$, so we’ll need to tweak the formula for Lagrange inversion. Luckily this will just get rid of the sign $(-1)^k$ 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:

$$\displaystyle{ g(z) = \sum_{k=0}^\infty \binom{n k}{k} \frac{z^{(n-1)k+1} }{(n-1)k+1} }$$

So, the number of rooted planar $n$-ary trees with $(n-1)k + 1$ leaves should be

$$\binom{n k}{k} \frac{1}{(n-1)k+1}$$

As a sanity check, note that an $n$-ary tree always has $(n-1)k + 1$ leaves for some natural number $k \ge 0$, because it can either have $1$ leaf (the root), or we can stick a sprout with $n$ leaves on an existing leaf, thus adding $n-1$ new leaves.

Also note that when $n = 2$ 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.