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.

Continue reading “How to Count n-Ary Trees” …
Posted at 8:24 AM UTC | Permalink | Post a Comment