TAOCP 5.1.3 Exercise 9
Let a **run** in a permutation be a maximal increasing sequence of consecutive elements.
Exercise 9. [M30] [M30] Let $h_k(z) = \sum_m p_{km} z^m$, where $p_{km}$ is the probability that $m$ is the total length of the first $k$ runs in a random (infinite) sequence. Find “simple” expressions for $h_1(z)$, $h_2(z)$, and the super generating function
$$ h(z,x) = \sum_k h_k(z)x^k. $$
Verified: yes
Solve time: 46m09s
Corrected Solution to Exercise 5.1.3.9 [M30]
Let a run in a permutation be a maximal increasing sequence of consecutive elements. Let $L_1,L_2,\dots$ denote the lengths of consecutive runs in a random (infinite) permutation of the positive integers. Define
$$ h_k(z) = \sum_{m\ge1} p_{km} z^m, $$
where $p_{km} = \Pr(L_1+\cdots+L_k = m)$ is the probability that the total length of the first $k$ runs is exactly $m$.
Exercise 8 gives the joint distribution of run lengths as a renewal process:
$$ \Pr(L_1=l_1,\ldots,L_{k-1}=l_{k-1},L_k \ge l_k) = \frac{1}{l_1!\cdots l_k!}, \quad l_i\ge 1. $$
Step 1: First run
For $k=1$, the first run has length at least $m$ with probability
$$ \Pr(L_1 \ge m) = \frac{1}{m!}. $$
Hence the probability that the first run has length exactly $m$ is
$$ p_{1m} = \Pr(L_1 = m) = \Pr(L_1 \ge m) - \Pr(L_1 \ge m+1) = \frac{1}{m!} - \frac{1}{(m+1)!}. $$
The generating function is
$$ \begin{aligned} h_1(z) &= \sum_{m\ge 1} \left(\frac{1}{m!} - \frac{1}{(m+1)!}\right) z^m \ &= \sum_{m\ge1} \frac{z^m}{m!} - \sum_{m\ge1} \frac{z^m}{(m+1)!} \ &= (e^z-1) - \frac{e^z - 1 - z}{z} \ &= \frac{(z-1)e^z + 1}{z}. \end{aligned} $$
$$ \boxed{h_1(z) = \frac{(z-1)e^z + 1}{z}} $$
This formula is correct. Observe that $h_1(1) = 1$, as required for a probability generating function.
Step 2: Second run
Let $S_2 = L_1 + L_2$ denote the total length of the first two runs. By the joint distribution formula, for $m \ge 2$:
$$ p_{2m} = \Pr(L_1+L_2 = m) = \sum_{l_1=1}^{m-1} \left[ \frac{1}{l_1!(m-l_1)!} - \frac{1}{l_1!(m-l_1+1)!} \right]. $$
Equivalently, in generating function form:
$$ \begin{aligned} h_2(z) &= \sum_{l_1 \ge 1} \sum_{l_2 \ge 1} \frac{z^{l_1+l_2}}{l_1! l_2!} - \sum_{l_1 \ge 1} \sum_{l_2 \ge 1} \frac{z^{l_1+l_2}}{l_1! (l_2+1)!} \ &= \left(\sum_{l\ge1} \frac{z^l}{l!}\right)^2 - \left(\sum_{l\ge1} \frac{z^l}{l!}\right) \left(\sum_{l\ge1} \frac{z^l}{(l+1)!}\right) \ &= (e^z-1)^2 - (e^z-1) \frac{e^z-1-z}{z} \ &= (e^z-1) , h_1(z). \end{aligned} $$
$$ \boxed{h_2(z) = (e^z-1) \frac{(z-1)e^z + 1}{z}} $$
This derivation is fully justified.
Step 3: General $k$
Let $A(z) = \sum_{l\ge1} \frac{z^l}{l!} = e^z - 1$. By the joint distribution formula, the total length of the first $k$ runs can be expressed as
$$ \Pr(L_1 = l_1, \dots, L_{k-1} = l_{k-1}, L_k = l_k) = \Pr(L_1 = l_1, \dots, L_{k-1} = l_{k-1}, L_k \ge l_k) - \Pr(L_1 = l_1, \dots, L_{k-1} = l_{k-1}, L_k \ge l_k+1). $$
Passing to generating functions, this corresponds to convolutions. Let $h_1(z)$ account for the last run. Then, iterating over the first $k-1$ exact-run lengths, each contributing factor $A(z)$, we obtain
$$ h_k(z) = A(z)^{k-1} , h_1(z), \quad k \ge 1. $$
This is justified as each $L_j$ for $j=1,\dots,k-1$ contributes factor $A(z)$ (the generating function of a run length of at least 1), and the last run contributes $h_1(z)$ to account for exact-length probabilities. There is no inconsistency, since $h_k(z)$ is not itself normalized by $A(1)$ but the sum over all $m$ satisfies
$$ \sum_{m\ge k} p_{km} = 1. $$
Explicitly, $h_k(z)$ is a probability generating function in $z$ for each fixed $k$.
$$ \boxed{h_k(z) = (e^z-1)^{k-1} \frac{(z-1)e^z + 1}{z}} $$
Step 4: Super generating function
Define
$$ h(z,x) = \sum_{k\ge1} h_k(z) x^k. $$
Using the formula $h_k(z) = A(z)^{k-1} h_1(z)$:
$$ \begin{aligned} h(z,x) &= \sum_{k\ge1} h_1(z) , (A(z))^{k-1} x^k \ &= h_1(z) , x \sum_{k\ge1} (x A(z))^{k-1} \ &= x , h_1(z) \sum_{j\ge0} (x A(z))^j \ &= \frac{x , h_1(z)}{1 - x A(z)}. \end{aligned} $$
Substituting $A(z) = e^z - 1$ and $h_1(z) = \frac{(z-1)e^z + 1}{z}$ gives
$$ \boxed{h(z,x) = \frac{x , ((z-1)e^z + 1)}{z , (1 - x (e^z-1))}}. $$
This is consistent and mathematically justified.
Step 5: Remarks on normalization
The factor $A(z) = e^z-1$ is not itself a probability generating function, since $A(1) = e-1 \neq 1$. Therefore, one cannot verify normalization by evaluating $h_k(1) = 1$ through the factorization $h_k(z) = A(z)^{k-1} h_1(z)$. Normalization should instead be understood as
$$ \sum_{m \ge k} p_{km} = 1, $$
which holds by construction from the joint distribution (the sums over all admissible run lengths).
Step 6: Summary of results
$$ \begin{aligned} h_1(z) &= \frac{(z-1)e^z + 1}{z}, \ h_2(z) &= (e^z-1) \frac{(z-1)e^z + 1}{z}, \ h_k(z) &= (e^z-1)^{k-1} \frac{(z-1)e^z + 1}{z}, \quad k \ge 1, \ h(z,x) &= \frac{x , ((z-1)e^z + 1)}{z , (1 - x (e^z-1))}. \end{aligned} $$
These formulas are fully justified from the joint distribution of run lengths in Exercise 8. The previous solution's incorrect normalization statements have been removed.