cp's OEIS Frontend

From Andrey Zabolotskiy, Aug 23 2017: (Start)

The smallest number of bits needed is ceiling(log_2(n)). For larger number of bits, more Gray codes exist. Cyclic Gray codes of odd lengths do not exist, hence only even lengths are considered.

A003042 is a subsequence: A003042(n+1) = a(2^n).

a(n) is also the number of self-avoiding directed cycles of length 2n on a cube of the least possible dimension starting from the origin.

(End)

An order-preserving Hamiltonian path in the n-cube is a listing S_1,...,S_N of all N:=2^n many subsets of [n]:={1,2,...,n}, such that if S_j is a subset of S_i then j <= i+1. For the counting we ignore paths that differ only by renaming elements of the ground set (=automorphisms of the n-cube), i.e., without loss of generality every such path starts as follows: S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4},..., S_{2n-2}={n-1}, S_{2n-1}={n-1,n}, S_{2n}={n} (after visiting the set {n}, there are multiple ways to proceed).

It is shown in [Felsner, Trotter 95] that an order-preserving Hamiltonian path is level-accurate in the following sense: After visiting a set of size k, the path will never visit a set of size (k-2) (*).

For odd n we will have S_N={1,2,...,n} (i.e., |S_N|=n) and for even n we will have |S_N|=n-1.

Hamiltonian paths that have property (*) have been constructed in [Savage, Winkler 95] for all n (but these paths are not order-preserving).

For n=8,9,10 we know that a(n)>=1. It is unknown whether a(n)>=1 for n>=11 (i.e., it is not known whether such order-preserving paths exist). Some partial results have been obtained in [Biro, Howard 09].