login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A236602 Number of canonical Gray cycles of length 2n. 5

%I

%S 1,1,1,6,4,22,96,1344,672,3448,12114,158424,406312,4579440,37826256,

%T 906545760,362618304,1784113248

%N Number of canonical Gray cycles of length 2n.

%C 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.

%C 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.

%C The sequence is a superset of A066037: A066037(n)=A236602(2^(n-1)).

%H Sykora S., <a href="http://dx.doi.org/10.3247/SL5Math14.001">On Canonical Gray Cycles</a>, Stan's Library, Vol.V, January 2014, DOI: 10.3247/SL5Math14.001.

%e a(5) = 4 since there are only these 4 CGC's of length 10:

%e {0 2 3 7 6 4 5 1 9 8}

%e {0 2 6 4 5 7 3 1 9 8}

%e {0 4 5 7 6 2 3 1 9 8}

%e {0 4 6 2 3 7 5 1 9 8}

%t A236602[n_] := Count[Map[lpf, Map[j0f, Permutations[Range[2 n - 1]]]], 0]/2;

%t j0f[x_] := Join[{0}, x, {0}];

%t btf[x_] := Module[{i},

%t Table[DigitCount[BitXor[x[[i]], x[[i + 1]]], 2, 1], {i,

%t Length[x] - 1}]];

%t lpf[x_] := Length[Select[btf[x], # != 1 &]];

%t Join[{1}, Table[A236602[n], {n, 2, 5}]]

%t (* OR, a less simple, but more efficient implementation. *)

%t A236602[n_, perm_, remain_] := Module[{opt, lr, i, new},

%t If[remain == {},

%t If[DigitCount[BitXor[First[perm], Last[perm]], 2, 1] == 1, ct++];

%t Return[ct],

%t opt = remain; lr = Length[remain];

%t For[i = 1, i <= lr, i++,

%t new = First[opt]; opt = Rest[opt];

%t If[DigitCount[BitXor[Last[perm], new], 2, 1] != 1, Continue[]];

%t A236602[n, Join[perm, {new}],

%t Complement[Range[2 n - 1], perm, {new}]];

%t ];

%t Return[ct];

%t ];

%t ];

%t Join[{1}, Table[ct = 0; A236602[n, {0}, Range[2 n - 1]]/2, {n, 2, 8}] ](* _Robert Price_, Oct 25 2018 *)

%o (C++) See the link

%Y Cf. A066037 (subset), A236603

%K nonn,hard,more

%O 1,4

%A _Stanislav Sykora_, Feb 01 2014

%E a(17)-a(18) from _Fausto A. C. Cariboni_, May 13 2017

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 January 18 05:30 EST 2019. Contains 319269 sequences. (Running on oeis4.)