TAOCP 2.3.4.4 Exercise 11

Let $c_n$ be the number of $t$-ary trees with $n$ nodes.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.4: Enumeration of Trees

Exercise 11. [**] [M28] The text derives the number of different binary trees with $n$ nodes (14). Generalize this to find the number of different $t$-ary trees with $n$ nodes. (See exercise 2.3.1-35; a $t$-ary tree is either empty or consists of a root and $t$ disjoint $t$-ary trees.) Hint: Use Eq. (21) of Section 1.2.9.

Verified: no
Solve time: 2m41s

Let $c_n$ be the number of $t$-ary trees with $n$ nodes. Since a $t$-ary tree is either empty or consists of a root together with $t$ independent $t$-ary subtrees, the generating function

$$ C(z)=\sum_{n\ge0} c_n z^n $$

satisfies

$$ C(z)=1+z,C(z)^t. $$

This is the direct analogue of Eq. (12). Applying Eq. (21) of Section 1.2.9 (Lagrange's inversion formula) to

$$ C(z)-1=z,C(z)^t, $$

gives

$$ c_n=\frac1n u^{,n-1}^{tn} =\frac1n\binom{tn}{n-1}. $$

Using

$$ \binom{tn}{n-1} =\frac{n}{(t-1)n+1}\binom{tn}{n}, $$

we obtain

$$ c_n=\frac{1}{(t-1)n+1}\binom{tn}{n}. $$

Hence the number of different $t$-ary trees with $n$ nodes is

$$ \boxed{\frac{1}{(t-1)n+1}\binom{tn}{n}}. $$

For $t=2$ this reduces to

$$ \frac1{n+1}\binom{2n}{n}, $$

which is Eq. (14). ∎