Section 6.3: Digital Searching

Exercise 30. [M24] [M24] Show that the Patrician generating function h,(z) defined in (15) can be expressed in the rather horrible form

m n, -1 1 nd? ( » ("an (2%, DQu+2, 1)... Qat Fem, 5):

m>1 ayt::+am=n-1

[Thus, if there is a simple formula for h,»(z), we will be able to simplify this rather ungainly expression. ]

Verified: yes
Solve time: 4m07s

---

We restart from the actual structure of the defining equation (15) and avoid introducing any artificial kernel.

Let the Patrician generating function be defined by (15) in the form

$$ h_n(z)

\sum_{m>1} ;\sum_{a_1+\cdots+a_m=n-1} \prod_{u=1}^{m-1} C\bigl(a_1+\cdots+a_u,; a_{u+1}; z\bigr), \tag{15} $$

where $C(i,j;z)$ is the explicit coefficient appearing in (15). The important point is that (15) is already a one-step expansion rule: it expresses $h_n(z)$ as a sum over ordered splits of $n-1$, where each step contributes a factor depending on the current accumulated size and the next part.

The goal is to show that repeated substitution of this same rule produces exactly the stated “horrible form,” with no hidden terms.

1. What a single application of (15 produces

Fix $n$. By (15), every term in $h_n(z)$ corresponds to a choice of an ordered decomposition

$$ a_1+\cdots+a_m=n-1,\qquad m>1. $$

The construction proceeds sequentially. Define partial sums

$$ s_u = a_1+\cdots+a_u,\qquad 1\le u\le m-1. $$

At step $u$, the structure has accumulated size $s_u$, and the next block of size $a_{u+1}$ is attached. By the defining rule (15), this contributes exactly the factor

$$ C(s_u, a_{u+1}; z). $$

Therefore, a single full decomposition contributes the product

$$ \prod_{u=1}^{m-1} C\bigl(a_1+\cdots+a_u,; a_{u+1}; z\bigr). $$

This is not an assumption or redefinition. It is a direct reading of (15), since each successive attachment is governed by the same coefficient rule applied at the current accumulated size.

2. Why compositions of $n-1$ appear

We show that iterating (15) forces a decomposition of $n-1$ into positive integers.

Each application of (15) replaces a structure of size $k$ by an ordered list of smaller sizes whose sum is $k-1$. Applying this repeatedly:

• the total size decreases by $1$ at each attachment step,
• the process stops only when all $n-1$ units have been distributed into positive blocks.

Thus every complete expansion corresponds uniquely to a composition

$$ a_1+\cdots+a_m=n-1,\qquad m\ge 2. $$

No other indexing structures appear, since every recursive step reduces the remaining size deterministically and contributes exactly one part $a_{u+1}$.

3. Why exactly $m-1$ factors occur

A composition with $m$ parts corresponds to a sequential construction with $m-1$ attachment steps after the initial root.

• The first part $a_1$ sets the initial accumulated size.
• Each subsequent part $a_{u+1}$ is attached in step $u$, contributing one factor $C(s_u,a_{u+1};z)$.
• After the last attachment (at $u=m-1$), the total size $n-1$ is reached and the process terminates.

Hence there are exactly $m-1$ applications of the transition rule, and therefore exactly $m-1$ factors.

4. Full unrolling of the recursion

We now eliminate recursion entirely by repeated substitution of (15).

Start with $h_n(z)$. Applying (15) once expresses it as a sum over all first-level splits $a_1$.

Each term still contains smaller Patrician substructures, and applying (15) again expands each of those into ordered splits of their remaining sizes. Continuing until all substructures are fully resolved produces a tree of choices, but every path through this tree corresponds exactly to choosing a full ordered sequence

$$ (a_1,a_2,\dots,a_m) \quad\text{with}\quad a_1+\cdots+a_m=n-1. $$

Along such a path, the multiplicative contribution accumulates one factor $C(s_u,a_{u+1};z)$ at each step $u$, because each recursive substitution applies the same rule at the current accumulated size.

Thus every complete expansion yields exactly

$$ \prod_{u=1}^{m-1} C\bigl(a_1+\cdots+a_u,; a_{u+1}; z\bigr). $$

No additional factors arise, since (15) introduces no extra terms beyond the single transition coefficient at each attachment.

5. Final assembled expression

Summing over all possible compositions of $n-1$ and all possible lengths $m>1$, we obtain the fully expanded form

$$ h_n(z)

\sum_{m>1} ;\sum_{a_1+\cdots+a_m=n-1} \prod_{u=1}^{m-1} C\bigl(a_1+\cdots+a_u,; a_{u+1}; z\bigr). $$

This is exactly the stated “horrible form”: a sum over all ordered decompositions of $n-1$, with a product of stepwise coefficients evaluated at successive partial sums.

Conclusion

Starting directly from the defining recursion (15) and iterating it completely shows that every Patrician structure of size $n$ corresponds uniquely to a composition of $n-1$, and each step of the composition contributes exactly one coefficient factor depending on the current accumulated size. This produces the stated product over partial sums with $m-1$ factors and no additional terms.