

A236602


Number of canonical Gray cycles of length 2n.


5



1, 1, 1, 6, 4, 22, 96, 1344, 672, 3448, 12114, 158424, 406312, 4579440, 37826256, 906545760, 362618304, 1784113248
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

By a canonical Gray cycle (CGC) of length 2n is intended a monocyclic permutation of the integers {0,1,2,...,2n1} 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,...,(2n1), 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: A066037(n)=A236602(2^(n1)).


LINKS

Table of n, a(n) for n=1..18.
Sykora S., On Canonical Gray Cycles, Stan's Library, Vol.V, January 2014, DOI: 10.3247/SL5Math14.001.


EXAMPLE

a(5) = 4 since there are only these 4 CGC's of length 10:
{0 2 3 7 6 4 5 1 9 8}
{0 2 6 4 5 7 3 1 9 8}
{0 4 5 7 6 2 3 1 9 8}
{0 4 6 2 3 7 5 1 9 8}


PROG

(C++) See the link


CROSSREFS

Cf. A066037 (subset), A236603
Sequence in context: A292696 A318209 A120462 * A169689 A061592 A081631
Adjacent sequences: A236599 A236600 A236601 * A236603 A236604 A236605


KEYWORD

nonn,hard,more


AUTHOR

Stanislav Sykora, Feb 01 2014


EXTENSIONS

a(17)a(18) from Fausto A. C. Cariboni, May 13 2017


STATUS

approved



