TAOCP 7.2.1.2 Exercise 6

Section 7.2.1.2: Generating All Permutations

Exercise 6. [HM34] [HM34] Derive generating functions for the mean number of comparisons made by Algorithm L in (a) step L2, (b) step L3, when {a1, . . . , an} is a general multiset as in exercise 4. Also give the results in closed form when {a1, . . . , an} is the binary multiset {s · 0, (n −s) · 1}.

Verified: no
Solve time: 1m20s

Setup

Algorithm $L$ enumerates permutations (and multiset permutations) by maintaining an inversion table $c_1,\dots,c_n$ satisfying

$0 \le c_j < B_j,$

where $B_j$ is the admissible bound for coordinate $j$ determined by the multiset structure.

At each transition, step $L2$ scans indices from the right to the left until it finds the largest $j$ for which a change is possible, and step $L3$ performs the comparison test that continues this scan or terminates it. Each scan position contributes exactly one comparison in $L2$, and each continuation test contributes exactly one comparison in $L3$.

Let $C^{(2)}_n$ denote the number of comparisons performed in step $L2$ per generated permutation, and $C^{(3)}_n$ the number in step $L3$.

Let $\mathcal{C}n = \prod{j=1}^n {0,1,\dots,B_j-1}$ be the inversion-table state space for $n$ symbols in the multiset model of Exercise 4. The algorithm visits each element of $\mathcal{C}_n$ exactly once, hence the uniform distribution on $\mathcal{C}_n$ governs mean values.

The task is to derive exponential generating functions

$F^{(2)}(z) = \sum_{n \ge 0} \mathbb{E}[C^{(2)}n]\frac{z^n}{n!}, \qquad F^{(3)}(z) = \sum{n \ge 0} \mathbb{E}[C^{(3)}_n]\frac{z^n}{n!},$

and to specialize to the binary multiset ${s\cdot 0,(n-s)\cdot 1}$.

Solution

For a fixed state $c_1,\dots,c_n$, step $L2$ performs a scan from $j=n$ downward until it finds the first index $j_0$ such that $c_{j_0} < B_{j_0}-1$. The scan inspects all indices $k>j_0$ and verifies that $c_k = B_k-1$, after which it inspects $j_0$ itself and stops.

Hence the number of comparisons in $L2$ equals

$C^{(2)}n = \min{k \ge 1 : c{n-k+1} < B_{n-k+1}-1}.$

For each fixed $k$, the event $C^{(2)}_n \ge k$ occurs exactly when

$c_n = B_n-1, c_{n-1} = B_{n-1}-1, \dots, c_{n-k+2} = B_{n-k+2}-1,$

which has probability

$\prod_{i=n-k+2}^{n} \frac{1}{B_i}$

under the uniform product distribution on $\mathcal{C}_n$.

Therefore

= \sum_{k=1}^{n} \prod_{i=n-k+2}^{n} \frac{1}{B_i}.$$ Reindexing with $j=n-k+1$ yields $$\mathbb{E}[C^{(2)}n] = \sum{j=1}^{n} \prod_{i=j+1}^{n} \frac{1}{B_i}.$$ For step $L3$, each time a coordinate $j$ fails the condition $c_j + o_j \in {0,j}$, the algorithm performs exactly one additional comparison before continuing. The scan structure is identical, so each visited index contributes one $L3$ comparison. The scan always inspects the same prefix of indices as in $L2$; hence $$\mathbb{E}[C^{(3)}n] = \mathbb{E}[C^{(2)}n].$$ To obtain generating functions, define $$A_n = \sum{j=1}^{n} \prod{i=j+1}^{n} \frac{1}{B_i}.$$ Then $$F^{(2)}(z) = F^{(3)}(z) = \sum_{n \ge 0} A_n \frac{z^n}{n!}.$$ Interchanging summations gives $$F^{(2)}(z) = \sum_{j \ge 1} \sum_{n \ge j} \left(\prod_{i=j+1}^{n} \frac{1}{B_i}\right)\frac{z^n}{n!}.$$ Introduce the tail product $$P_{j,n} = \prod_{i=j+1}^{n} \frac{1}{B_i}, \quad P_{n,n}=1.$$ Then $$F^{(2)}(z) = \sum_{j \ge 1} \sum_{m \ge 0} P_{j,j+m}\frac{z^{j+m}}{(j+m)!}.$$ This is the required general exponential generating function form. ### Binary multiset specialization For the multiset ${s\cdot 0,(n-s)\cdot 1}$, inversion-table coordinates split into two independent groups: the $0$-block contributes no freedom in later coordinates, while the $1$-block contributes a standard binary inversion structure. In this case the admissible bounds satisfy $$B_i = 1 \quad \text{for coordinates corresponding to the maximal symbol},$$ and $$B_i = s+1 \quad \text{for the remaining $n-s$ coordinates},$$ because each 1 can have at most $s$ zeros to its right. Hence the tail product simplifies to a geometric form: $$\prod_{i=j+1}^{n} \frac{1}{B_i} = (s+1)^{-(n-j)}.$$ Substituting into $A_n$ gives $$A_n = \sum_{j=1}^{n} (s+1)^{-(n-j)} = \sum_{k=0}^{n-1} (s+1)^{-k}.$$ This is a finite geometric series, hence $$A_n = \frac{1-(s+1)^{-n}}{1-\frac{1}{s+1}} = \frac{s+1}{s}\left(1-(s+1)^{-n}\right).$$ Therefore the exponential generating function becomes $$F^{(2)}(z) = F^{(3)}(z) = \frac{s+1}{s}\sum_{n \ge 0}\left(1-(s+1)^{-n}\right)\frac{z^n}{n!}.$$ Split into two standard series: $$F^{(2)}(z) = \frac{s+1}{s}\left(e^z - \sum_{n \ge 0}\frac{(z/(s+1))^n}{n!}\right).$$ Hence $$F^{(2)}(z) = \frac{s+1}{s}\left(e^z - e^{z/(s+1)}\right).$$ The same expression holds for $F^{(3)}(z)$. ## Verification For $L2$, the distribution of the scan length depends only on the event that a suffix of coordinates is maximal in the inversion-table order. Under the product structure of $\mathcal{C}_n$, each coordinate contributes independently to the event that it equals its maximum value, yielding the product form for tail probabilities. Summing tail probabilities recovers the expectation. For the binary specialization, $B_i=s+1$ is constant over the relevant coordinates, so each additional scanned position multiplies probability by $(s+1)^{-1}$, producing a geometric series. Substitution into the exponential generating function separates into two standard exponentials, which simplifies to $$\frac{s+1}{s}(e^z - e^{z/(s+1)}).$$ Both $L2$ and $L3$ count identical scan lengths, since both steps inspect the same maximal suffix before the first non-maximal coordinate is encountered. This completes the proof. ∎