Counting Binary Trees (The Hard Way)

In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with nodes.

Suppose I have a binary tree of internal nodes, we can count all possible such configurations by looking at the tree like

where each internal subtree with nodes is a vertex plus two trees whose node-sum is , or

This is pretty fucking hard to solve. Here’s a way where we do not need to appeal to generating functions.

Let’s begin with a reasonable hypothesis: is a first order recurrence. After groping around for a while, we find that this is actually a nonlinear homogeneous recurrence:

Here’s the first couple of terms:

No obvious pattern yet, but if we look at the sequence , we see that it looks like

Notice how the primes in the denominator are exactly the right amount of spacing apart ( is 2 away from , 4 away from , etc). Furthermore, for the nonprime denominators, they are always a divisor of what the expected value there is supposed to be (for example, the in the number right before the ), this seems to suggest that there’s always an inverse affine factor between two elements of the sequence. Since the denominator of is , let’s conjecture that

In fact, the sequence looks really nice!

why, this is just the sequence , so we can pretty accurately guess that

Warning: This is a really tedious proof; the point is to construct a series that cancels out the on the denominator of at each step of the induction.

Proof: By strong induction, for some , suppose that we have already shown that .
Consider the series

In the case, this looks like

notice that we can flip the order of this series and add with itself to get

By appealing to the induction hypothesis on , we also have

So, above, we’ve derived the following:

Substituting the left into the right, we get

which concludes the proof.

This recurrence allows us to write

Notice that this is the same as

Phew.

Posted By Lee

Woosh

• Anderson Torres

What if you have put some interesting restriction on the binary tree? Example: what about AVL trees?