cp's OEIS Frontend

A236602 Number of canonical Gray cycles of length 2n.

%I A236602 #44 Jan 07 2025 12:45:25
%S A236602 1,1,1,6,4,22,96,1344,672,3448,12114,158424,406312,4579440,37826256,
%T A236602 906545760,362618304,1784113248,5576251408,68998853808,154939065862
%N A236602 Number of canonical Gray cycles of length 2n.
%C A236602 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.
%C A236602 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 A236602 The sequence is a superset of A066037.
%H A236602 Stanislav Sykora, <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.
%F A236602 a(2^(n-1)) = A066037(n).
%F A236602 a(n) = A350784(n)/2 for n >= 2. - _Martin Ehrenstein_, Feb 16 2022
%e A236602 a(5) = 4 since there are only these 4 CGC's of length 10:
%e A236602 {0 2 3 7 6 4 5 1 9 8}
%e A236602 {0 2 6 4 5 7 3 1 9 8}
%e A236602 {0 4 5 7 6 2 3 1 9 8}
%e A236602 {0 4 6 2 3 7 5 1 9 8}
%t A236602 A236602[n_] := Count[Map[lpf, Map[j0f, Permutations[Range[2 n - 1]]]], 0]/2;
%t A236602 j0f[x_] := Join[{0}, x, {0}];
%t A236602 btf[x_] := Module[{i},
%t A236602    Table[DigitCount[BitXor[x[[i]], x[[i + 1]]], 2, 1], {i,
%t A236602      Length[x] - 1}]];
%t A236602 lpf[x_] := Length[Select[btf[x], # != 1 &]];
%t A236602 Join[{1}, Table[A236602[n], {n, 2, 5}]]
%t A236602 (* OR, a less simple, but more efficient implementation. *)
%t A236602 A236602[n_, perm_, remain_] := Module[{opt, lr, i, new},
%t A236602    If[remain == {},
%t A236602      If[DigitCount[BitXor[First[perm], Last[perm]], 2, 1] == 1, ct++];
%t A236602      Return[ct],
%t A236602      opt = remain; lr = Length[remain];
%t A236602      For[i = 1, i <= lr, i++,
%t A236602       new = First[opt]; opt = Rest[opt];
%t A236602       If[DigitCount[BitXor[Last[perm], new], 2, 1] != 1, Continue[]];
%t A236602       A236602[n, Join[perm, {new}],
%t A236602        Complement[Range[2 n - 1], perm, {new}]];
%t A236602       ];
%t A236602      Return[ct];
%t A236602      ];
%t A236602    ];
%t A236602 Join[{1}, Table[ct = 0; A236602[n, {0}, Range[2 n - 1]]/2, {n, 2, 8}] ](* _Robert Price_, Oct 25 2018 *)
%o A236602 (C++) // See Sykora link.
%Y A236602 Cf. A066037 (subset), A236603, A350784.
%K A236602 nonn,hard,more
%O A236602 1,4
%A A236602 _Stanislav Sykora_, Feb 01 2014
%E A236602 a(17)-a(18) from _Fausto A. C. Cariboni_, May 13 2017
%E A236602 a(19)-a(20) from _Martin Ehrenstein_, Feb 16 2022
%E A236602 a(21) from _Martin Ehrenstein_, Feb 21 2022