TAOCP 7.2.1.6 Exercise 91

Let $T_n$ denote the set of rooted ordered trees with $n$ internal nodes in the sense of Algorithm B of Section 7.

taocpmathematicsalgorithmsvolume-4math-project

Section 7.2.1.6: Generating All Trees

Exercise 91. [M37] (Nijenhuis and Wilf.) Show that a random oriented tree can be generated with a procedure analogous to the random partition algorithm of exercise 7.2.1.4–47.

Verified: yes
Solve time: 1m56s

Setup

Let $T_n$ denote the set of rooted ordered trees with $n$ internal nodes in the sense of Algorithm B of Section 7.2.1.6, represented by left and right links $(l_1,\dots,l_n)$ and $(r_1,\dots,r_n)$ with nodes labeled in preorder. Via the natural correspondence described in Section 7.2.1.6, these structures are in bijection with binary trees with $n$ internal nodes and with properly nested parenthesis strings of length $2n$. Let $C_n = |T_n|$ be their cardinality.

A random oriented tree in the sense of the exercise means a tree chosen uniformly from $T_n$. The task is to construct a sampling procedure that produces each element of $T_n$ with probability $1/C_n$, using a recursive decomposition analogous to the random partition method of exercise 7.2.1.4–47.

The known decomposition for binary trees is that a tree with $n$ internal nodes is uniquely determined by the size $k$ of the left subtree of the root, where $0 \le k \le n-1$, together with an arbitrary left subtree in $T_k$ and right subtree in $T_{n-1-k}$. This yields the recurrence

$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}.$

Solution

Fix $n \ge 1$. A uniform random element of $T_n$ is generated by choosing the decomposition at the root in a way consistent with the counting recurrence.

For each admissible split $k$, the number of trees with left subtree size $k$ is $C_k C_{n-1-k}$. Since all trees in $T_n$ are equally likely, the probability that the root has split size $k$ must be

$\mathbb{P}(K = k) = \frac{C_k C_{n-1-k}}{C_n}.$

Once $k$ is chosen, the left subtree must be chosen uniformly from $T_k$ and the right subtree independently uniformly from $T_{n-1-k}$. This yields a recursive construction.

Define the sampling procedure $\mathcal{R}(n)$ as follows. For $n=0$, return the empty tree. For $n \ge 1$, compute $C_0,\dots,C_{n-1}$ and $C_n$, choose an integer $K$ in ${0,\dots,n-1}$ with probability proportional to $C_K C_{n-1-K}$, construct independently a tree $L \sim \mathcal{R}(K)$ and a tree $R \sim \mathcal{R}(n-1-K)$, and attach $L$ and $R$ as the left and right subtrees of a new root node.

This construction mirrors the random partition algorithm for combinatorial classes defined by a convolution recurrence: the decomposition of a size-$n$ object into two independent subobjects whose sizes sum to $n-1$, weighted by their combinatorial counts.

The same procedure transfers to the parent-pointer representation $p_1,\dots,p_n$ by converting the generated binary tree via preorder labeling, since Section 7.2.1.6 establishes a bijection between these representations.

Verification

Correctness reduces to showing that the induced probability distribution on $T_n$ is uniform.

Let $t \in T_n$ be fixed, and let its root decomposition correspond to a split size $k$, left subtree $t_L \in T_k$, and right subtree $t_R \in T_{n-1-k}$. The procedure generates $t$ exactly when it selects $K=k$ and then recursively generates $t_L$ and $t_R$.

The probability of selecting $K=k$ equals $C_k C_{n-1-k}/C_n$. By induction on $n$, the recursive calls generate $t_L$ and $t_R$ with probabilities $1/C_k$ and $1/C_{n-1-k}$ respectively. The independence of the two recursive constructions multiplies these probabilities, so the probability of generating $t$ equals

$\frac{C_k C_{n-1-k}}{C_n} \cdot \frac{1}{C_k} \cdot \frac{1}{C_{n-1-k}} = \frac{1}{C_n}.$

This expression is independent of the choice of $t$, hence every element of $T_n$ is produced with equal probability.

The probabilities used for selecting $K$ sum to $1$ because

$\sum_{k=0}^{n-1} \frac{C_k C_{n-1-k}}{C_n} = \frac{1}{C_n} \sum_{k=0}^{n-1} C_k C_{n-1-k} = \frac{C_n}{C_n} = 1,$

where the convolution identity defining $C_n$ is used.

This completes the proof. ∎

Notes

The construction is structurally identical to the random partition method for recursively defined combinatorial classes, where a global uniform distribution is achieved by weighting each recursive choice proportionally to the number of completions consistent with that choice. In this setting, the Catalan convolution plays the same role as the partition recurrence in exercise 7.2.1.4–47, and the binary-tree decomposition provides the exact analogue of splitting a partition into independent subproblems.