TAOCP 7.2.1.4 Exercise 62

Section 7.2.1.4: Generating All Partitions

Exercise 62. [46] [46] Prove or disprove: For all sufficiently large integers n and 3 ≤m < n such that n mod m ̸= 0, and for all partitions α of n with a1 ≤m, there is a Gray path for all partitions with parts ≤m, beginning at 1n and ending at α, unless α = 1n or α = 21n−2.

Verified: no
Solve time: 22m36s

Setup

Let $\mathcal{P}(n,m)$ denote the set of partitions $\alpha = a_1 \ge a_2 \ge \cdots$ of $n$ with largest part $a_1 \le m$. A Gray path in this context is a Hamiltonian path in the graph whose vertices are $\mathcal{P}(n,m)$ and whose edges correspond to consecutive partitions differing by the elementary move used throughout Section 7.2.1.4, namely the transfer of a single unit between adjacent parts (equivalently, one application of the successor mechanism in Algorithm P, interpreted as an adjacency relation on partitions).

The problem asks whether, for all sufficiently large $n$ and integers $m$ satisfying $3 \le m < n$ with $n \bmod m \ne 0$, and for every partition $\alpha \in \mathcal{P}(n,m)$, there exists a Gray path starting at $1^n$ and ending at $\alpha$, except when $\alpha = 1^n$ or $\alpha = 21^{n-2}$.

This is equivalent to asking whether the induced subgraph of the partition lattice restricted to parts $\le m$ is Hamilton-connected from $1^n$ to every vertex except the two specified endpoints.

Known results

The existence of Gray codes for unrestricted partitions of $n$ is established in Algorithm P of Section 7.2.1.4, which produces a Hamiltonian path of the full partition set of $n$ in reverse lexicographic order, with consecutive partitions differing by a localized modification of suffix structure. This construction does not preserve a bound on the largest part, since intermediate steps may increase a part beyond a fixed $m$ even when both endpoints lie in $\mathcal{P}(n,m)$.

Gray codes for restricted combinatorial classes, including restricted compositions and restricted integer sequences, are classical, but results for partitions with a hard upper bound on part size are substantially sparser. Standard constructions based on lexicographic or colexicographic orderings do not in general preserve feasibility under the constraint $a_1 \le m$, and no general Hamilton-connectedness theorem for this constrained partition graph appears in the literature accompanying TAOCP Vol. 4 or in the standard enumerative combinatorics treatments of restricted partitions.

The two excluded partitions are extremal in the restricted poset. The partition $1^n$ is the unique minimum element. The partition $21^{n-2}$ is the unique partition whose only deviation from $1^n$ consists of a single merge of two $1$ parts into a $2$, making it adjacent only to configurations that necessarily force a temporary violation of monotonicity constraints under many natural Gray transitions. These two configurations are therefore natural obstructions for endpoint-fixing Gray constructions.

Partial argument

The partition graph on $\mathcal{P}(n,m)$ is connected for all $m \ge 2$ because any partition can be transformed into any other by repeated transfers of single units between parts while maintaining nonincreasing order, and the bound $a_1 \le m$ is preserved throughout such transfers provided all intermediate redistributions remain within the Ferrers diagram contained in an $m \times \infty$ strip.

From $1^n$, any partition $\alpha \in \mathcal{P}(n,m)$ can be reached by repeatedly merging parts of size $1$ into larger parts until the multiplicities match the part counts of $\alpha$. This yields a monotone path in the dominance order, but not a Gray path in the sense required, since the resulting sequence does not control adjacency steps to guarantee that successive partitions differ by the single localized transformation used in Algorithm P.

A standard obstruction to constructing a Hamilton path with fixed endpoints in such constrained partition graphs arises from parity and degree considerations at boundary vertices. The vertex $1^n$ has limited available moves: any legal move must begin by merging two $1$ parts into a $2$, producing $21^{n-2}$. Thus $21^{n-2}$ is the unique neighbor of $1^n$ in the natural partition adjacency graph under single-unit transfer moves. Any Hamilton path starting at $1^n$ is therefore forced to begin with the edge

$$ 1^n \to 21^{n-2}, $$

which explains the necessity of excluding $\alpha = 21^{n-2}$ as an endpoint distinct from $1^n$.

Beyond this forced initial transition, the existence of a Hamilton path from $21^{n-2}$ to arbitrary $\alpha \in \mathcal{P}(n,m)$ requires that the induced subgraph $\mathcal{P}(n,m) \setminus {1^n}$ be Hamilton-connected from $21^{n-2}$, a property that is not guaranteed by known Gray code constructions for restricted partitions. In particular, known lexicographic successor rules do not preserve the constraint $a_1 \le m$ in a way that yields a uniform traversal structure compatible with arbitrary terminal vertices.

No construction is known that simultaneously enforces all three constraints: (i) visits every partition in $\mathcal{P}(n,m)$ exactly once, (ii) preserves adjacency by a single elementary partition modification, and (iii) allows arbitrary terminal vertex $\alpha$ with $a_1 \le m$, except in degenerate cases where $m$ is very large relative to $n$ or where $\mathcal{P}(n,m)$ has special product structure.

Status

The statement is not settled in general form. There is no known theorem establishing Hamilton-connectedness of the partition graph of bounded largest part $m$ for all sufficiently large $n$ under the Gray adjacency implicit in Section 7.2.1.4, and no known construction covering all endpoints $\alpha \in \mathcal{P}(n,m)$ except the two trivial obstructions.

The result is therefore best regarded as an open problem in full generality, with only partial structural constraints understood, in particular the forced adjacency $1^n \leftrightarrow 21^{n-2}$ and the existence of Hamilton paths in the unrestricted partition lattice.

This completes the analysis. ∎