Gray code enumeration of families of integer partitions (Q1805052)

Let \(P(n, k)\) be the set of partitions \(n= \sum_{j\geq 1} x_ j\) with \(x_ j\) nonnegative integers such that \(k\geq x_ 1\geq x_ 2\geq \dots\). Two partitions \(n = \sum_{j \geq 1} x_ j\) and \(n= \sum_{j\geq 1} y_ j\) are called adjacent if \(\sum_{j\geq 1} | x_ j- y_ j|= 2\). A Gray code enumeration of \(P(n, k)\) is a listing of all elements of \(P(n, k)\) such that two consecutive partitions are adjacent in the above sense. In terms of graph theory this means a Hamilton path in the graph of the adjacency relation in \(P(n, k)\). Such a Gray code has been constructed by one of the authors in a previous paper. In the present paper they address the question of existence of a Gray code for the classes of partitions \(P_ \delta(n, k)\) in \(P(n, k)\) such that \(x_ j\equiv 1\pmod\delta\) if \(x_ j\geq 1\). The adjacency condition is then replaced by the condition \(\sum_{j\geq 1} | x_ j- y_ j|= 2\delta\). Also the classes \(D(n, k)\) consisting of partitions in \(P(n, k)\) for which \(x_ j> x_{j+ 1}\) if \(x_ j\geq 1\) are considered. The answer is affirmative in both cases and the strategy to produce a Gray code consists in dividing the class of partitions into subclasses, according to the value of the first two elements in the partitions. In each subclass a Gray code, which begins at the largest point and ends at the smallest, in the lexicographic order, is constructed by induction, and then enough adjacency relations between the largest and smallest elements belonging to different subclasses are established so that they can be related to produce the Gray code. The analysis is complicated by the existence of some exceptional subclasses for which the Gray code from largest to smallest elements does not exist, and so another Gray code has to be produced. This implies that a lot of cases have to be considered in inductive constructions.