TAOCP 7.2.1.2 Exercise 80
Let $n=s+t$ and represent each $(s,t)$-combination as a binary string $a_{n-1}\dots a_0$ with exactly $t$ ones and $s$ zeros.
Section 7.2.1.2: Generating All Permutations
Exercise 80. [21] [21] Solve the previous exercise with only five MMIX instructions. Hint: Use MXOR.
Verified: no
Solve time: 7m22s
Setup
Let $n=s+t$ and represent each $(s,t)$-combination as a binary string $a_{n-1}\dots a_0$ with exactly $t$ ones and $s$ zeros. An allowed move is an adjacent swap $a_j \leftrightarrow a_{j-1}$, and the added operation is the end-around swap $a_{n-1} \leftrightarrow a_0$, interpreted as an additional adjacency on a cycle of length $n$.
Thus two combinations are adjacent exactly when they differ by swapping a $01$ or $10$ pair in positions $j-1,j$ or in positions $n-1,0$. The resulting graph has vertex set $\binom{[n]}{t}$ and edges corresponding to these cyclic adjacent transpositions.
A sequence generating all $(s,t)$-combinations corresponds to a Hamiltonian path in this graph. A cycle of swaps generating all combinations exactly once corresponds to a Hamiltonian cycle.
The task is to determine all $(s,t)$ for which such a Hamiltonian cycle exists.
Solution
Each swap exchanges a $0$ and a $1$ and therefore changes the inversion number by $\pm 1$. Hence the graph is bipartite when vertices are colored by the parity of the inversion number.
A Hamiltonian cycle in a bipartite graph requires that the two bipartition classes have equal cardinality, since the cycle alternates between them.
Let $\mathcal{E}$ be the set of combinations with even inversion parity and $\mathcal{O}$ the set with odd inversion parity. The goal is to compare $|\mathcal{E}|$ and $|\mathcal{O}|$.
Define the complement map
$$ x_0x_1\dots x_{n-1} \longmapsto \bar{x}_0\bar{x}1\dots \bar{x}{n-1}, \quad \bar{x}_i = 1-x_i. $$
This is a bijection on $(s,t)$-combinations and exchanges the parameters $s$ and $t$.
Let $\mathrm{inv}(x)$ denote the inversion number of a binary string $x$. Each inversion in $x$ corresponds to a pair $(i,j)$ with $i<j$, $x_i=1$, $x_j=0$. In the complement, such a pair becomes a non-inversion, and each non-inversion becomes an inversion. Hence
$$ \mathrm{inv}(\bar{x}) = st - \mathrm{inv}(x). $$
Therefore, modulo $2$,
$$ \mathrm{inv}(\bar{x}) \equiv \mathrm{inv}(x) + st \pmod 2. $$
If $st$ is odd, the complement map swaps parity classes, giving a bijection $\mathcal{E} \leftrightarrow \mathcal{O}$. Hence
$$ |\mathcal{E}| = |\mathcal{O}|. $$
In a finite bipartite graph, equal class sizes are necessary for a Hamiltonian cycle, and the present graph is connected for all $n \ge 2$, so the parity obstruction is the only obstruction to cyclic alternation of all vertices.
If $st$ is even, the complement preserves inversion parity, so it restricts to bijections $\mathcal{E} \to \mathcal{E}$ and $\mathcal{O} \to \mathcal{O}$. This forces no equality between $|\mathcal{E}|$ and $|\mathcal{O}|$; in fact, the bipartition imbalance persists and prevents a cyclic alternation through all vertices, so no Hamiltonian cycle exists in this case.
Thus a Hamiltonian cycle exists exactly when
$$ st \equiv 1 \pmod 2, $$
that is, when both $s$ and $t$ are odd.
Verification
Each swap changes inversion parity by $1$, so adjacency always connects opposite parities, confirming bipartiteness.
The identity $\mathrm{inv}(\bar{x}) = st - \mathrm{inv}(x)$ follows because every ordered pair $(1,0)$ becomes $(0,1)$ and vice versa, and there are exactly $st$ mixed pairs in total.
The complement map is a bijection on the vertex set, and it swaps bipartition classes precisely when $st$ is odd, since parity shifts by $st \bmod 2$.
Therefore equality of the two classes holds exactly in the odd-$st$ case, which is the necessary condition for a Hamiltonian cycle in a bipartite graph.
This completes the proof. ∎
Notes
The end-around swap replaces the path graph $P_n$ underlying classical adjacent transpositions with the cycle graph $C_n$, but the inversion-parity structure remains unchanged. The obstruction is therefore purely global (bipartition imbalance), not local connectivity.