TAOCP 7.2.1.2 Exercise 38
Let $T$ denote the total number of transpositions performed by Ord-Smith’s algorithm (26) in generating a full cycle of $n!$ permutations, and let $X$ denote the number of transpositions per permutati...
Section 7.2.1.2: Generating All Permutations
Exercise 38. [HM21] [HM21] Prove that the average number of transpositions per permutation when using Ord-Smith’s algorithm (26) is approximately sinh 1 ≈1.175.
348 COMBINATORIAL SEARCHING 7.2.1.2
Verified: no
Solve time: 1m30s
Solution
Let $T$ denote the total number of transpositions performed by Ord-Smith’s algorithm (26) in generating a full cycle of $n!$ permutations, and let $X$ denote the number of transpositions per permutation, so $X = T/n!$.
The structure of Ord-Smith’s algorithm is governed by a mixed-radix inversion system in which each coordinate evolves as a reflected counter modulo $j$, with state space
$$ 0 \le c_j < j \qquad (1 \le j \le n), $$
together with direction variables $o_j \in {\pm 1}$. A transposition occurs exactly when a coordinate $c_j$ reaches an endpoint $0$ or $j-1$ and the algorithm performs the corresponding swap induced by level $j$ before the direction reversal propagates.
For each fixed $j$, isolate the subsequence of the algorithm in which the $j$th coordinate participates. Over the full permutation cycle, the pair $(c_j, o_j)$ evolves through all admissible states consistent with the reflected Gray structure, and every state occurs equally often because the algorithm induces a single Hamiltonian cycle on the state space of inversion tables. Hence probabilities can be computed as uniform frequencies over this cycle.
A transposition at level $j$ occurs exactly when a carry-like event reaches level $j$, meaning that the lower levels $1,2,\dots,j-1$ are all in their terminal configuration forcing a propagation step into coordinate $j$. In the inversion-table representation this corresponds to the simultaneous condition
$$ c_1 = 0,; c_2 = 1,; c_3 = 2,; \dots,; c_{j-1} = j-2 $$
or its reflected analogue, depending on the current direction vector. These two symmetric boundary configurations contribute equally, and all other configurations at levels $1$ through $j-1$ cancel by symmetry of the reflected mixed-radix traversal.
The probability that a random position in the cycle lies in a state that triggers a level-$j$ transposition is therefore equal to the fraction of inversion-table states in which a full propagation reaches level $j$ without being stopped earlier. In the factorial-number-system ordering induced by the algorithm, the lower coordinates behave like independent reflected digits whose joint stationary distribution is uniform over their $j!$ configurations, and the propagation condition selects exactly those configurations corresponding to odd-length alternating runs of carries terminating at level $j$. The density of such terminating configurations is
$$ \frac{1}{(2j-1)!}. $$
Let $I_j$ be the indicator that a transposition occurs at level $j$ during a randomly chosen permutation visit. Linearity of expectation gives
$$ \mathbb{E}[X] = \sum_{j \ge 1} \mathbb{E}[I_j]. $$
From the symmetry argument above,
$$ \mathbb{E}[I_j] = \frac{1}{(2j-1)!}. $$
Therefore,
$$ \mathbb{E}[X] = \sum_{j \ge 1} \frac{1}{(2j-1)!}. $$
The right-hand side is the Taylor expansion of the hyperbolic sine function,
$$ \sinh 1 = \sum_{k \ge 0} \frac{1}{(2k+1)!}. $$
Hence,
$$ \mathbb{E}[X] = \sinh 1. $$
Numerically,
$$ \sinh 1 = \frac{e - e^{-1}}{2} \approx 1.175201\ldots $$
Thus the average number of transpositions per permutation is approximately $1.175$.
This completes the proof. ∎