Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649192 | Discrete Mathematics | 2009 | 9 Pages |
Abstract
In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles . Universal cycles have been investigated for permutations, partitions, kk-partitions and kk-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n−1n−1-partitions of an nn-set when nn is odd and conjectured that when nn is even, they do not exist. Herein we prove Hurlbert’s conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for n≤13n≤13 and give a lower bound on the total number for all nn. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Karel Casteels, Brett Stevens,