TAOCP 2.3.4.4 Exercise 5

Section 2.3.4.4: Enumeration of Trees

Exercise 5. [**] [M25] (A. Cayley.) Let $c_n$ be the number of (unlabeled) oriented trees having $n$ leaves (namely, vertices with in-degree zero) and having at least two subtrees at every other vertex. Thus $c_3=2$, by virtue of the two trees

Find a formula analogous to (3) for the generating function

$$ C(z)=\sum_n c_nz^n. $$

Verified: no
Solve time: 31s

Let $C(z)$ be the generating function for the numbers $c_n$, where $c_n$ counts oriented trees with $n$ leaves and with every nonleaf vertex having at least two subtrees. Each such tree consists of a root connected to $k\ge2$ subtrees, each of which is itself such a tree. Denoting the generating function by $C(z)$, we have the decomposition

$$ C(z) = z + \sum_{k\ge2} \frac{C(z)^k}{k!}, k! = z + \sum_{k\ge2} C(z)^k = z + C(z)^2 + C(z)^3 + C(z)^4 + \cdots. $$

Summing the geometric series yields

$$ C(z) = z + \frac{C(z)^2}{1-C(z)}, \qquad |C(z)|<1. $$

Equivalently, this can be written as

$$ C(z) = z + C(z)^2 + C(z)^3 + C(z)^4 + \cdots = z + \frac{C(z)^2}{1-C(z)}. $$

This provides a direct formula for the generating function $C(z)$ analogous to equation (3) for ordinary oriented trees. The series begins

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

where the coefficients enumerate trees with the stated properties. This completes the solution. ∎