Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 7, 2025

How to Count n-Ary Trees

Posted by John Baez

How do you count rooted planar nn-ary trees with some number of leaves? For n=2n = 2 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 n>2n \gt 2?

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:

Bx+B 2 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

B114x2=x+x 2+2x 3+5x 4+14x 5+ 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 nn-ary trees by a similar equation:

Tx+T n T \cong x + T^n

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

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

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

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

Here’s how it works. Let’s write

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

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

g j= k=1 j1(1) kj k¯B j1,k(f^ 1,f^ 2,,f^ jk) \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

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

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

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

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

B 6,2(x 1,x 2,x 3,x 4,x 5)= B_{6,2}(x_1,x_2,x_3,x_4,x_5)= 6x 5x 1+15x 4x 2+10x 3 26x_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 nn-ary trees. We’re trying to solve

T=x+T n T = x + T^n

or in other words

x=T nT x = T^n - T

for xx. So we make up a function

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

and we seek the inverse power series gg: this will give us TT as a power series in xx.

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

g(z)= k=0 (nkk)z (n1)k+1(n1)k+1 \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 nn-ary trees with (n1)k+1(n-1)k + 1 leaves should be

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

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

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

Posted at July 7, 2025 8:24 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3606

0 Comments & 0 Trackbacks

Post a New Comment