The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A259839 Number of order-preserving Hamiltonian paths in the n-cube (Gray codes); see the comments for the precise definition of order-preserving. 0
1, 1, 1, 1, 1, 10, 123, 1492723 (list; graph; refs; listen; history; text; internal format)



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].


Table of n, a(n) for n=0..7.

C. Biro and D. Howard, The first three levels of an order preserving Hamiltonian path in the subset lattice, Order, 26(2):101-107, 2009.

S. Felsner and W. Trotter, Colorings of diagrams of interval orders and alpha-sequences of sets, Discrete Math., 144(1-3):23-31, 1995.

C. Savage and P. Winkler, Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A, 70(2):230-248, 1995.


For n=4 the a(4)=1 solution is 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_9={2,4}, S_10={1,2,4}, S_11={1,4}, S_12={1,3,4}, S_13={1,3}, S_14={1,2,3}, S_15={1,2,3,4}, S_16={2,3,4}.


Cf. A003042, A003043, A006069, A006070, A066037, A091302, A159344.

Sequence in context: A239760 A296190 A263552 * A005174 A034668 A215854

Adjacent sequences:  A259836 A259837 A259838 * A259840 A259841 A259842




Torsten Muetze, Jul 06 2015



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 04:12 EST 2020. Contains 332321 sequences. (Running on oeis4.)