TAOCP 2.3.4.4 Exercise 6

Let $g_n$ denote the number of distinct oriented binary trees with $n$ vertices, where each vertex has in-degree at most two.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.4: Enumeration of Trees

Exercise 6. [**] [M25] Let an "oriented binary tree" be an oriented tree in which each vertex has in-degree two or less. Find a reasonably simple relation that defines the generating function $G(z)$ for the number of distinct oriented binary trees with $n$ vertices, and find the first few values.

Verified: no
Solve time: 49s

Let $g_n$ denote the number of distinct oriented binary trees with $n$ vertices, where each vertex has in-degree at most two. If a tree is nonempty, it consists of a root together with zero, one, or two oriented binary subtrees attached to it. Suppose the left subtree has $k$ vertices and the right subtree has $n-1-k$ vertices. There are $g_k g_{n-1-k}$ possibilities for this decomposition. Summing over all $k$ with $0\le k\le n-1$ gives

$$ g_n = \sum_{k=0}^{n-1} g_k g_{n-1-k}, \qquad n\ge1, $$

with the initial condition $g_0=1$ corresponding to the empty tree.

Let $G(z)$ be the generating function

$$ G(z) = \sum_{n\ge0} g_n z^n. $$

Then the recurrence translates to the quadratic functional equation

$$ G(z) = 1 + z,G(z)^2. $$

Solving this quadratic equation using the condition $G(0)=1$ yields

$$ G(z) = \frac{1-\sqrt{1-4z}}{2z}. $$

Expanding the series gives the first few terms

$$ G(z) = 1 + z + 2 z^2 + 5 z^3 + 14 z^4 + 42 z^5 + \cdots, $$

so that $g_0=1$, $g_1=1$, $g_2=2$, $g_3=5$, $g_4=14$, $g_5=42$.

This completes the solution.

∎