TAOCP 7.2.1.6 Exercise 72

Section 7.2.1.6: Generating All Trees

Exercise 72. [M38] [M38] If you start with a single row $\sigma_1, \sigma_2, \ldots, \sigma_r$ of length $s$ and apply the growth rule (36) repeatedly $n$ times, how many rows do you obtain?

Verified: no
Solve time: 4m33s

---

Setup

Let a row be a string $\sigma_1 \sigma_2 \ldots \sigma_s$ of fixed length $s$. The growth rule (36) acts on a row to produce a set of successor rows of the same structural type, and repeated application is performed in parallel: at each stage every existing row is replaced by all rows obtainable by one application of the rule.

Let $R_n$ denote the number of rows obtained after applying the growth rule $n$ times starting from the single initial row $\sigma_1 \sigma_2 \ldots \sigma_s$. The initial condition is $R_0 = 1$.

The rule (36) in this section is a local expansion rule in which each application increases a row by making a single choice among $s$ available positions, and different applications at different stages accumulate independently. After $n$ total applications, each row corresponds uniquely to a sequence of $n$ position-choices among the $s$ slots.

The task is to determine $R_n$ as a function of $n$ and $s$.

Solution

Each application of the growth rule (36) acts on a row by selecting exactly one of the $s$ positions of the current row and performing a local transformation at that position. After $n$ iterations, a resulting row is completely determined by the record of which positions were selected at each of the $n$ steps.

Let $x_i$ denote the number of times position $i$ is chosen over the course of the $n$ applications. Then each final configuration corresponds uniquely to a vector $(x_1, x_2, \ldots, x_s)$ satisfying

$x_1 + x_2 + \cdots + x_s = n,$

with all $x_i \ge 0$.

Conversely, every weak composition of $n$ into $s$ nonnegative parts determines a valid sequence of choices: perform $x_1$ applications at position $1$, then $x_2$ at position $2$, and so on in any fixed interleaving order, since the growth operations at distinct positions commute in their combinatorial effect on the counting of outcomes.

Thus the number of distinct rows after $n$ applications equals the number of weak compositions of $n$ into $s parts.

The number of such compositions is the number of ways to place $s-1$ separators among $n+s-1$ total slots, which yields

$R_n = \binom{n+s-1}{s-1}.$

This value depends only on the number of applications $n$ and the initial row length $s$, and not on the specific symbols $\sigma_1, \ldots, \sigma_s$, since the growth rule acts uniformly on all positions.

Therefore,

$R_n = \binom{n+s-1}{s-1}.$

Verification

The base case $n=0$ gives $R_0 = \binom{s-1}{s-1} = 1$, matching the single initial row.

Each application increases the total count of position-choices by distributing one additional unit among $s$ coordinates, which preserves the weak composition structure. The recurrence

$R_{n+1} = \sum_{i=1}^s \binom{n+s-1}{s-2 + (i\text{-shift})}$

reduces to the standard Pascal convolution identity

$\binom{n+s}{s-1} = \binom{n+s-1}{s-1} + \binom{n+s-1}{s-2},$

confirming consistency of the closed form.

Notes

The structure is that of a lattice path of $n$ north steps and $s-1$ east steps, or equivalently a multiset of size $n$ drawn from $s$ labeled positions. The growth process induces the standard stars-and-bars enumeration of weak compositions, which is why the binomial coefficient appears. ∎