cp's OEIS Frontend

Finding a(6) is Problem 43 in the Knuth reference.

More precisely, this is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one. The final node may or may not be adjacent to the first.

Row n contains 2^(n-1)-1 terms.

Also the triangle of even-order coefficients (odd coefficients are all 0) of the hypercube graph cycle polynomials ordered from smallest to largest exponent starting with x^4. - Eric W. Weisstein, Feb 05 2014

Equals A066037(n)/(n!/2). See A006069, A003042, A066037 for more information.

More precisely, this is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one. The final node may or may not be adjacent to the first. Finally, divide by 2^n since the starting node really doesn't matter.

Also, the number of strings s of length 2^n - 1 over the alphabet {1,2,...,n} with the property that every contiguous subblock has some letter that appears an odd number of times.

By a canonical Gray cycle (CGC) of length 2n is intended a monocyclic permutation of the integers {0,1,2,...,2n-1} such that (i) it starts with "0", (ii) the binary expansions of any two adjacent terms of the cycle differ by exactly one bit, and (iii) the last term is larger than the second. Note: there are no CGC's of odd length.

For n>1, a(n) is also the number of all distinct Hamiltonian circuits in a simple graph with 2n vertices, labeled 0,1,2,...,(2n-1), in which two vertices are connected by an edge only if the binary expansions of their labels differ by exactly one bit.

The sequence is a superset of A066037.

Here we count equivalence classes under the full automorphism group of the n-cube. - N. J. A. Sloane, Sep 06 2012

a(4) is due to Gilbert and a(5) is due to Dejter & Delgado.

Comments on Abbott's (1966) lower bound, from Charles R Greathouse IV and David Applegate (Sequence Fans Mailing List, Dec 06 2012: (Start)

a(n) is, in Abbott's terminology, h*(n); see (2) and (3) which yield a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n) [Note that we have written sqrt(294) for 7 sqrt(6)].

Unfortunately, the lower bound seems incompatible with the known values of a(n), even for a(3) and a(4) which were known to Abbott.

Looking at Abbot's paper, at least one error is the claim "it is easy to verify that (12) implies (3)."

(12) is h(m+3) >= 6^2^m h(m), which implies h(m) >= 6^2^(m-3) for m >= 4, or h(m) >= 2/5 * (6^2^(m-3)) for m >= 1, but certainly doesn't imply (3) h(m) >= (7 sqrt(6))^(2^n-4). (End)

Terms up to a(5)=18651552840 confirmed by independent computation. [Joerg Arndt, Aug 07 2012]

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