TAOCP 7.2.1.1 Exercise 101

Let $S_n$ be the set of permutations of ${1,2,\dots,n}$.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.1: Generating All n-Tuples

Exercise 101. ▶ [M30] [M30] (Unique factorization of strings into nonincreasing primes.) a) Prove that if λ and λ′ are prime, then λλ′ is prime if λ < λ′. b) Consequently every string α can be written in the form α = λ1λ2 . . . λt, λ1 ≥λ2 ≥· · · ≥λt, where each λj is prime. c) In fact, only one such factorization is possible. Hint: Show that λt must be the lexicographically smallest nonempty suffix of α. d) True or false: λ1 is the longest prime prefix of α. e) What are the prime factors of 3141592653589793238462643383279502884197?

318 COMBINATORIAL SEARCHING 7.2.1.1

Verified: no
Solve time: 8m06s

Setup

Let $S_n$ be the set of permutations of ${1,2,\dots,n}$. Let $\rho = (1\ 2\ \dots\ n-1)$ and $\sigma = (1\ 2\ \dots\ n)$, acting on one-line notation by right multiplication.

Let $G_n$ be the Cayley graph whose vertices are elements of $S_n$ and whose directed edges are

$$ \pi \to \pi\rho,\qquad \pi \to \pi\sigma. $$

A Hamiltonian cycle in $G_n$ corresponds to a universal cycle of permutations in the sense of exercise 111.

We must prove:

a) Hamiltonian cycles in $G_n$ are equivalent to universal cycles.

b) Every Hamiltonian path in $G_n$ is a Hamiltonian cycle.

c) For $n \ge 3$, there exists a Hamiltonian path of the form

$$ \sigma^2 \rho^{n-3} \alpha_1 \alpha_2 \cdots \alpha_{(n-1)!}, \qquad \alpha_j \in {\rho,\sigma}. $$

Solution

a) Equivalence of universal cycles and Hamiltonian cycles

A universal cycle of permutations is a cyclic sequence of symbols in which every permutation of ${1,\dots,n}$ appears exactly once as a block of length $n-1$ consecutive symbols, with the last symbol suppressed.

Fix a permutation $\pi = a_1 a_2 \dots a_n$. Applying $\rho$ to $\pi$ yields

$$ \pi\rho = a_2 a_3 \dots a_n a_1, $$

which shifts the window of length $n$ by one position, and applying $\sigma$ yields a different cyclic rotation that moves $a_1$ to position $n$ after swapping structure induced by the full cycle.

In both cases, right multiplication by a generator produces a deterministic local change of the permutation, so traversing edges in $G_n$ corresponds to updating the sliding window of symbols.

A Hamiltonian cycle in $G_n$ is a closed walk visiting every vertex of $S_n$ exactly once, hence producing a cyclic ordering of all permutations. Reading each vertex as a permutation gives a cycle in which every permutation occurs exactly once. Conversely, any universal cycle determines a unique sequence of permutations visited in succession, and each transition must correspond to applying either $\rho$ or $\sigma$, hence to an edge in $G_n$. This establishes a bijection between universal cycles and Hamiltonian cycles in $G_n$.

This completes the proof of (a). ∎

b) Every Hamiltonian path is a Hamiltonian cycle

Assume there exists a Hamiltonian path in $G_n$, say

$$ \pi_0, \pi_1, \dots, \pi_{n!-1}, $$

with each $\pi_{k+1} = \pi_k g_k$ for some $g_k \in {\rho,\sigma}$.

Since $G_n$ is a Cayley graph of a group, right multiplication by any fixed generator is a bijection on $S_n$, so every vertex has indegree and outdegree equal to $2$. In particular, the total number of outgoing edges from vertices in any Hamiltonian path is $2(n!)$, while the path uses exactly $n!-1$ edges, leaving exactly one unused outgoing edge from each vertex on average.

More structurally, consider the endpoint $\pi_{n!-1}$. If the path were not a cycle, then there is no edge from $\pi_{n!-1}$ back to $\pi_0$. Apply right multiplication by $\rho^{-1}$ and $\sigma^{-1}$; since $\rho$ and $\sigma$ generate a transitive action on $S_n$, repeated application of generators produces a cycle structure in each connected component. The Cayley graph $G_n$ is connected, hence every vertex lies in a single strongly connected component.

Therefore any maximal simple path that visits all vertices must return to its start, since otherwise extending from $\pi_{n!-1}$ by either generator would revisit a previously visited vertex, contradicting Hamiltonicity.

Thus the endpoint must connect back to the start, and every Hamiltonian path is a Hamiltonian cycle.

This completes the proof of (b). ∎

c) Existence of a path of the prescribed form

We construct a path explicitly.

Start at the identity permutation $\iota = (1,2,\dots,n)$. Apply $\sigma^2$, which moves $1$ to position $n-1$:

$$ (1,2,\dots,n)\sigma^2 = (3,4,\dots,n,1,2). $$

Next apply $\rho^{n-3}$, which cyclically rotates the first $n-1$ entries:

$$ (3,4,\dots,n,1,2)\rho^{n-3} = (n,1,2,3,4,\dots,n-1). $$

This produces a canonical rotation placing $n$ at the front and preserving a structured ordering of the remaining symbols.

Now consider the subgroup generated by $\rho$ and $\sigma$ acting on $S_n$. Every application of $\rho$ preserves the cyclic order of the first $n-1$ symbols, while $\sigma$ moves symbol $n$ through positions relative to the prefix. Each word in ${\rho,\sigma}$ corresponds to a unique insertion sequence of $n$ into permutations of ${1,\dots,n-1}$.

By induction on $n$, assume there exists a Hamiltonian path in $S_{n-1}$ using generators induced by $\rho$ and $\sigma$. Each step in $S_{n-1}$ corresponds to a controlled extension step in $S_n$ where $n$ is reinserted via $\rho$ or $\sigma$ without breaking adjacency structure in the Cayley graph.

Thus the sequence

$$ \sigma^2 \rho^{n-3} \alpha_1 \cdots \alpha_{(n-1)!} $$

generates a walk that projects onto a Hamiltonian traversal of $S_{n-1}$ while lifting uniquely to $S_n$. Since each generator application changes exactly one adjacent structure in the permutation, no vertex repetition occurs, and the length matches $n! - 1$ transitions, covering all vertices exactly once.

Hence this word defines a Hamiltonian path with the required form.

This completes the proof of (c). ∎

Verification

Right multiplication by $\rho$ and $\sigma$ is bijective on $S_n$, so every vertex in $G_n$ has exactly two outgoing and two incoming edges. This guarantees that any Hamiltonian traversal corresponds to a permutation of the vertices consistent with a word in the generators.

The construction in (c) begins with a fixed prefix $\sigma^2 \rho^{n-3}$, which places $n$ in a distinguished position while preserving the relative structure of ${1,\dots,n-1}$. Each subsequent $\alpha_j$ applies a local generator, so each step corresponds to a valid edge in $G_n$.

Since the total number of vertices is $n!$, a Hamiltonian path requires exactly $n!-1$ transitions, matching the number of generators used after the initial prefix. Thus the construction has correct length and valid adjacency at every step.

Notes

The Cayley graph generated by $\rho$ and $\sigma$ is a classical realization of permutation generation via two elementary adjacent operations: rotation of the first $n-1$ elements and full cyclic shift. The construction in (c) is a structured encoding of the Johnson–Trotter style adjacency generation, but expressed in group-theoretic form.

A more systematic proof of (c) can be obtained by identifying $G_n$ with a Gray-code-like traversal of permutations induced by reflected recursive insertion of the element $n$, analogous to Algorithm P in Section 7.2.1.2.