Warning: jsMath requires JavaScript to process the mathematics on this page.
If your browser supports JavaScript, be sure it is enabled.

G. Hurlbert Ucycles
Universal Cycles

An $(n,k)$ deBruijn-Good sequence is a cyclic sequence containing every $k$-ary $n$-tuple exactly once as a contiguous subsequence. For example, $$00000100101100111110001101110101$$ is one for $(n,k)=(5,2)$, and $$000222122021121020120011101$$ is one for $(n,k)=(3,3)$. A Universal Cycle is a generalization of this idea for other combinatorial structures, such as $k$-subsets of $[n]$, permutations of $[n]$, partitions of $[n]$, $k$-dimensional subspaces of a vector space, etc. For example, $$13567256823472357814782456145712361246783671345834681256$$ lists all $3$-subsets of $[8]$ exacly once. The biggest open problem here is the \$250 CDG conjecture: for every $k$ and every large $n$ (maybe only $n\ge k+2$?) for which $n$ divides $n\choose k$ there is a Ucycle for $k$-subsets of $[n]$. Another variation involves listing all arrays of a certain type within a larger toroidal array. The Chung/Diaconis/Graham paper started this area in 1992, and a workshop was held in Banff in 2004 among an exceptionally fun crew of practitioners. Here is a recent research article.