TAOCP 2.3.4.4: Enumeration of Trees
Section 2.3.4.4 exercises: 30/30 solved.
Section 2.3.4.4. Enumeration of Trees
Exercises from TAOCP Volume 1 Section 2.3.4.4: 30/30 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | solved | 33s | |
| 2 | [**] | verified | 4m11s | |
| 3 | [**] | verified | 5m43s | |
| 4 | [**] | verified | 8m09s | |
| 5 | [**] | solved | 31s | |
| 6 | [**] | solved | 49s | |
| 7 | [**] | solved | 34s | |
| 8 | [**] | solved | 6m15s | |
| 9 | [**] | solved | 28s | |
| 10 | [**] | solved | 2m19s | |
| 11 | [**] | solved | 2m41s | |
| 12 | [**] | solved | 30s | |
| 13 | [**] | solved | 1m49s | |
| 14 | [**] | verified | 12m12s | |
| 15 | [**] | verified | 2m05s | |
| 16 | [**] | solved | 1m11s | |
| 17 | [**] | solved | 2m58s | |
| 18 | [**] | solved | 3m17s | |
| 19 | [**] | verified | 3m30s | |
| 20 | [**] | verified | 3m38s | |
| 21 | [**] | verified | 1m10s | |
| 22 | [**] | verified | 2m11s | |
| 23 | [**] | verified | 1m19s | |
| 24 | [**] | verified | 59s | |
| 25 | [**] | verified | 1m46s | |
| 26 | [**] | verified | 1m57s | |
| 27 | [**] | solved | 5m07s | |
| 28 | [**] | verified | 2m40s | |
| 29 | [**] | solved | 3m26s | |
| 30 | [**] | verified | 2m04s |
TAOCP 2.3.4.4 Exercise 1
We start from equation (3) of the section, which states that 1 + A(z) + A(z)^2 + A(z)^3 + \cdots = \prod_{n\ge1} \frac{1}{(1-z^n)^{a_n}}.
TAOCP 2.3.4.4 Exercise 2
From exercise 1, write A(z)=z\,e^{C(z)},\qquad C(z)=\sum_{k\ge1}\frac{A(z^k)}{k}.
TAOCP 2.3.4.4 Exercise 3
The failure occurs at a single decisive point: the sequence $A_n$ was not derived from the correct functional equation for rooted unlabeled trees.
TAOCP 2.3.4.4 Exercise 4
Let A(z)=\sum_{n\ge1}a_n z^n,\qquad a_n\ge 0, and
TAOCP 2.3.4.4 Exercise 5
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.
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.
TAOCP 2.3.4.4 Exercise 7
Let $G(z)=\sum_{n\ge1}g_nz^n$, where $g_n$ is the number of distinct oriented binary trees with $n$ vertices.
TAOCP 2.3.4.4 Exercise 8
The solution fails because it tries to classify the six trees using degree sequences, but degree sequences alone do not enumerate all non-isomorphic trees on six vertices.
TAOCP 2.3.4.4 Exercise 9
Let $T$ be a free tree.
TAOCP 2.3.4.4 Exercise 10
Let $T$ be a free tree with $n$ vertices and two centroids, say $X$ and $Y$.
TAOCP 2.3.4.4 Exercise 11
Let $c_n$ be the number of $t$-ary trees with $n$ nodes.
TAOCP 2.3.4.4 Exercise 12
By exercise 2.
TAOCP 2.3.4.4 Exercise 13
The given canonical sequence is 3,1,4,1,5,9,2,6,5.
TAOCP 2.3.4.4 Exercise 14
**Corrected Solution for Exercise 2.
TAOCP 2.3.4.4 Exercise 15
Let the oriented tree be rooted, with every edge directed toward the root.
TAOCP 2.3.4.4 Exercise 16
The construction described after (16) already yields an efficient method.
TAOCP 2.3.4.4 Exercise 17
**Corrected Solution to Exercise 2.
TAOCP 2.3.4.4 Exercise 18
Let the vertices be labeled $1,\dots,n$, and let every edge be oriented toward the root.
TAOCP 2.3.4.4 Exercise 19
The Prüfer-code framework is correct, but the constraint “exactly $k$ leaves” must be enforced as a surjectivity condition, not as a simple restriction on the alphabet.
TAOCP 2.3.4.4 Exercise 20
Start from the correct expression that survives all prior reductions: Let the prescribed indegree sequence be $x_1,\dots,x_n$, a permutation of a multiset with $k_i$ occurrences of $i$, and $\sum_v x_...
TAOCP 2.3.4.4 Exercise 21
Let $k_i$ denote the number of vertices of in-degree $i$.
TAOCP 2.3.4.4 Exercise 22
**Exercise 2.
TAOCP 2.3.4.4 Exercise 23
Let $\mathcal{T}_n$ be the set of ordered trees with $n$ vertices whose vertices are labeled by ${1,2,\ldots,n}$.
TAOCP 2.3.4.4 Exercise 24
The structure of an ordered tree with $n$ vertices is independent of labels; only the relative left-to-right ordering of subtrees at each node matters.
TAOCP 2.3.4.4 Exercise 25
**Exercise 2.
TAOCP 2.3.4.4 Exercise 26
The flaw in the previous solution is that it treated the semicolon-separated display as a syntactic artifact rather than what it represents in the $((3,2,4),(1,4,2))$-construction.
TAOCP 2.3.4.4 Exercise 27
Let U_1,U_2,\ldots,U_q,\qquad V_1,V_2,\ldots,V_r be vertices of a directed graph.
TAOCP 2.3.4.4 Exercise 28
**Corrected Solution to Exercise 2.