Analytic Combinatorics – A Worked Example

Summary

Analytic Combinatorics -- A Worked Example 08 Apr 2025 - Tags: sage Another day, another blog post that starts with “I was on mse the other day…”. This time, someone asked an interesting question amounting to “how many unordered rooted ternary trees with $n$ nodes are there, up to isomorphism?”. I’m a sucker for these kinds of combinatorial problems, and after finding a generating function solution I wanted to push myself to get an asymptotic approximation using Flajolet–Sedgewick style analytic combinatorics! I’ve never actually done this before, so I learned a lot, and I want to share some of the things I learned – especially how to do this stuff in sage! Now, you might be thinking – didn’t you write a very similar blog post three years ago? Yes. Yes I did. Did I also completely forget what was in that post? Yes. Yes I did, haha. For some reason I was getting it mixed up with this other post from even more years ago, which isn’t nearly as relevant. Thankfully it didn’t matter much, since I’m fairly sure what I wanted to do wouldn’t work in the framework of that post anyways, and now I have a better idea of what this machinery is actually doing which is really exciting (since I’ve been wanting to understand this stuff for years). Let’s start with a warmup problem! How might we count the number of rooted ordered ternary trees with $n$ nodes? These are the kinds of “ternary trees” that you might remember from a first class on algorithms and data structures. Such a tree is either a leaf or an internal node with 1,2, or 3 children. Crucially these children come with an order, because the datatype keeps track of which child is on the left/right (in the case of 2 children) or on the left/middle/right (in the case of 3 children). After all, from a CS perspective, we need to remember this in order to traverse the tree! This means that the following two trees are distinct for our purposes, even though they’re isomorphic as graphs: In a functional programming language, you m...