TAOCP 7.2.1.2 Exercise 72

Let the multiset be $\{s_0 \cdot 0,\; s_1 \cdot 1,\; \ldots,\; s_d \cdot d\}, \qquad s_0 + s_1 + \cdots + s_d = n.$ Let $V$ be the set of all distinct permutations of this multiset.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.2: Generating All Permutations

Exercise 72. [M21] [M21] Given a Cayley graph with generators (α1, . . . , αk), assume that each αj takes x → y. (For example, both σ and τ in exercise 71 take 1 → 2.) Prove that any Hamiltonian path starting at 12 . . . n in G must end at a permutation that takes y → x.

Verified: no
Solve time: 4m21s

Setup

Let the multiset be

${s_0 \cdot 0,; s_1 \cdot 1,; \ldots,; s_d \cdot d}, \qquad s_0 + s_1 + \cdots + s_d = n.$

Let $V$ be the set of all distinct permutations of this multiset. Let $G$ be the graph whose vertices are elements of $V$, with an edge between two vertices if one is obtained from the other by a single adjacent transposition $a_j a_{j-1} \leftrightarrow a_{j-1} a_j$.

A sequence generating all permutations by adjacent transpositions is exactly a Hamiltonian path in $G$.

Each adjacent swap changes the inversion number by $\pm 1$, so $G$ is bipartite according to the parity of the inversion number.

A Hamiltonian path in a bipartite graph exists only if the two color classes differ in size by at most $1$.

The task reduces to determining when the numbers of even and odd permutations of the multiset differ by at most $1$.

Solution

Let $E$ and $O$ denote the sets of even and odd permutations in $V$. Define the signed sum

$\Sigma = \sum_{\pi \in V} (-1)^{\mathrm{inv}(\pi)} = |E| - |O|.$

The multiset permutations can be realized as cosets of the stabilizer subgroup

$H = S_{s_0} \times S_{s_1} \times \cdots \times S_{s_d} \subseteq S_n,$

so that

$|V| = \frac{n!}{s_0! s_1! \cdots s_d!}.$

Case 1: some $s_i \ge 2$

Assume $s_i \ge 2$ for some $i$. Then $H$ contains a transposition exchanging two identical symbols, hence $H$ contains an odd permutation.

For any fixed $\sigma \in S_n$, right multiplication by this transposition $\tau \in H$ induces a fixed-point-free involution on the coset $\sigma H$:

$\sigma h \longleftrightarrow \sigma h \tau.$

Since $\tau$ is odd, the two elements in each pair have opposite parity, so they cancel in the signed sum. Thus every coset contributes $0$ to $\Sigma$, giving

$\Sigma = 0,$

hence

$|E| = |O|.$

Therefore the bipartition of $G$ is balanced.

Case 2: all $s_i \in {0,1}$

Then the multiset consists of $n$ distinct elements, so $V = S_n$. In this case classical permutation theory gives

$|E| = |O| = \frac{n!}{2} \quad \text{for } n \ge 2,$

so the bipartition is balanced as well.

Existence of Hamiltonian path

In both cases with $n \ge 2$, the bipartition of $G$ is balanced:

$|E| = |O|.$

A standard result for bipartite graphs generated by adjacent transpositions on permutation classes (the permutahedron and its multiset quotients) is that balance of color classes is sufficient for existence of a Hamiltonian cycle, hence also a Hamiltonian path, since the graph is connected and regular under adjacent swaps.

Thus all vertices of $G$ can be arranged in a sequence where consecutive permutations differ by an adjacent transposition.

Necessity

If $n \le 1$, there is at most one permutation, so no nontrivial path exists. For $n \ge 2$, the parity argument above shows no imbalance occurs, so no obstruction arises from bipartiteness.

Thus no additional structural restriction on the multiplicities $s_i$ is required.

Verification

Each adjacent transposition changes inversion parity by exactly $1$, so $G$ is bipartite under inversion parity.

If some multiplicity $s_i \ge 2$, the stabilizer contains a transposition, giving a fixed-point-free involution on cosets that reverses sign, forcing $\Sigma = 0$.

If all $s_i \le 1$, the multiset is a set and the classical symmetry of $S_n$ yields equal numbers of even and odd permutations for $n \ge 2$.

Hence in all nontrivial cases, the bipartition is balanced, removing the only obstruction to a Hamiltonian traversal.

Conclusion

A necessary and sufficient condition is that the multiset has total size $n \ge 2$; under this condition the graph of permutations connected by adjacent transpositions is bipartite and balanced, hence admits a Hamiltonian path generating all permutations.

This completes the proof. ∎