login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A236602
Number of canonical Gray cycles of length 2n.
6
1, 1, 1, 6, 4, 22, 96, 1344, 672, 3448, 12114, 158424, 406312, 4579440, 37826256, 906545760, 362618304, 1784113248, 5576251408, 68998853808, 154939065862
OFFSET
1,4
COMMENTS
By a canonical Gray cycle (CGC) of length 2n is intended a mono-cyclic 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.
LINKS
Stanislav Sykora, On Canonical Gray Cycles, Stan's Library, Vol.V, January 2014, DOI: 10.3247/SL5Math14.001.
FORMULA
a(2^(n-1)) = A066037(n).
a(n) = A350784(n)/2 for n >= 2. - Martin Ehrenstein, Feb 16 2022
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}
MATHEMATICA
A236602[n_] := Count[Map[lpf, Map[j0f, Permutations[Range[2 n - 1]]]], 0]/2;
j0f[x_] := Join[{0}, x, {0}];
btf[x_] := Module[{i},
Table[DigitCount[BitXor[x[[i]], x[[i + 1]]], 2, 1], {i,
Length[x] - 1}]];
lpf[x_] := Length[Select[btf[x], # != 1 &]];
Join[{1}, Table[A236602[n], {n, 2, 5}]]
(* OR, a less simple, but more efficient implementation. *)
A236602[n_, perm_, remain_] := Module[{opt, lr, i, new},
If[remain == {},
If[DigitCount[BitXor[First[perm], Last[perm]], 2, 1] == 1, ct++];
Return[ct],
opt = remain; lr = Length[remain];
For[i = 1, i <= lr, i++,
new = First[opt]; opt = Rest[opt];
If[DigitCount[BitXor[Last[perm], new], 2, 1] != 1, Continue[]];
A236602[n, Join[perm, {new}],
Complement[Range[2 n - 1], perm, {new}]];
];
Return[ct];
];
];
Join[{1}, Table[ct = 0; A236602[n, {0}, Range[2 n - 1]]/2, {n, 2, 8}] ](* Robert Price, Oct 25 2018 *)
PROG
(C++) See link.
CROSSREFS
Cf. A066037 (subset), A236603, A350784.
Sequence in context: A292696 A318209 A120462 * A169689 A328757 A061592
KEYWORD
nonn,hard,more
AUTHOR
Stanislav Sykora, Feb 01 2014
EXTENSIONS
a(17)-a(18) from Fausto A. C. Cariboni, May 13 2017
a(19)-a(20) from Martin Ehrenstein, Feb 16 2022
a(21) from Martin Ehrenstein, Feb 21 2022
STATUS
approved