TAOCP 1.2.10 Exercise 18
The critical issue in the proposed solution is the hidden assumption that “first element of a reduced problem” corresponds to the first element of the original permutation.
Section 1.2.10: Analysis of an Algorithm
Exercise 18. [M28] Suppose that the values taken on by $X[1],X[2],\ldots,X[n]$ in Algorithm M include exactly $k_1$ ones, $k_2$ twos, $\ldots$, $k_n$ $n$'s, arranged in random order, where
$$ k_1+k_2+\cdots+k_n = n. $$
Show that in this generalized situation, the generating function (8) becomes
$$ \left(\frac{k_n z}{k_n}\right) \left(\frac{k_{n-1}z+k_n}{k_{n-1}+k_n}\right) \left(\frac{k_{n-2}z+k_{n-1}+k_n}{k_{n-2}+k_{n-1}+k_n}\right)\cdots \left(\frac{k_1z+k_2+\cdots+k_n}{k_1+k_2+\cdots+k_n}\right)z, $$
using the convention $0/0=1$.
Verified: yes
Solve time: 2m32s
The critical issue in the proposed solution is the hidden assumption that “first element of a reduced problem” corresponds to the first element of the original permutation. It does not. The recursion is built on a different exposure process: the leftmost element among a restricted set of values, not the leftmost element of the whole sequence. Once that is corrected, the standard product form follows cleanly.
Correct model
Let the multiset contain $k_i$ copies of value $i$, $1\le i\le n$, arranged uniformly at random.
Let $A$ be the number of record maxima (running maxima) when scanning the permutation from left to right, and let
$$ G(z)=\mathbb{E}[z^A]. $$
Define
$$ S_i = k_i + k_{i+1} + \cdots + k_n. $$
We expose the permutation in stages from large values downward, but in a way that respects positions.
At stage $i$, we look only at elements whose values lie in ${i,i+1,\dots,n}$. Among these $S_i$ elements, consider their leftmost occurrence in the full permutation.
A key symmetry fact is:
In a uniformly random permutation of a multiset, the leftmost element among any specified subset of elements is uniformly distributed over that subset.
Hence, among the $S_i$ elements with values $\ge i$, the leftmost one is equally likely to belong to any of the $S_i$ items.
When does stage $i$ create a new record?
Process values from large to small.
At the moment we consider level $i$, all values $>i$ are “already active” in determining whether something is a record.
A new record at level $i$ occurs exactly when:
- the first (leftmost) element among all values $\ge i$ has value exactly $i$.
Reason: if the leftmost among ${i,\dots,n}$ has value $j>i$, then a larger value appears before any $i$, so no $i$-element can become a record at its first appearance relative to higher values. If it has value $i$, then at that moment no larger value has appeared earlier in the full permutation, so this is a record.
Therefore:
$$ \mathbb{P}(\text{new record at level } i)=\frac{k_i}{S_i}. $$
Correct recursion
Condition on the identity of the leftmost element among the $S_i$ elements.
- With probability $k_i/S_i$, this element has value $i$, contributes one record, hence multiplies the generating function by $z$.
- With probability $S_{i+1}/S_i$, it has value $>i$, contributes no new record at this stage.
In both cases, after removing this leftmost element, the remaining multiset is still uniformly random, and the same structure applies to the next stage. This is the crucial symmetry: removing a uniformly chosen element from a random multiset permutation preserves uniform randomness of the remainder.
Thus,
$$ G_i(z) = \left(\frac{k_i}{S_i}z + \frac{S_{i+1}}{S_i}\right) G_{i+1}(z). $$
Equivalently,
$$ G_i(z)=\frac{k_i z + S_{i+1}}{S_i},G_{i+1}(z). $$
Base case
For $i=n$, we have $S_n=k_n$. Among the $k_n$ identical maximal elements, exactly one becomes a record (the first occurrence), so:
$$ G_n(z)=z. $$
This matches the recursion since
$$ G_n(z)=\frac{k_n z}{k_n}=z. $$
Iteration
Iterating from $i=n$ down to $i=1$,
$$ G_1(z)=\prod_{i=1}^n \frac{k_i z + S_{i+1}}{S_i}, \qquad S_{n+1}=0. $$
Writing this explicitly,
$$ G_1(z) = \left(\frac{k_n z}{k_n}\right) \left(\frac{k_{n-1}z+k_n}{k_{n-1}+k_n}\right) \cdots \left(\frac{k_1 z + k_2+\cdots+k_n}{k_1+\cdots+k_n}\right). $$
Why the earlier argument failed
The incorrect step was interpreting the recursion as if the “first element” were always the first element of the entire permutation. It is not.
At level $i$, the process conditions on the first element among a shrinking subset of values, and that element is not necessarily a record globally. Once this distinction is made, the factor $z$ appears only when a genuinely new maximum value class is first revealed, which is exactly what the corrected conditioning captures.
Final result
$$ \boxed{ G(z) = \prod_{i=1}^n \frac{k_i z + (k_{i+1}+k_{i+2}+\cdots+k_n)}{k_i + k_{i+1}+\cdots+k_n} } \qquad (S_{n+1}=0). $$