

A242530


Number of cyclic arrangements of S={1,2,...,2n} such that the binary expansions of any two neighbors differ by one bit.


16



0, 0, 1, 0, 2, 8, 0, 0, 224, 754, 0, 26256, 0, 0, 22472304, 0, 90654576, 277251016, 0, 7852128780
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Here, a(n)=NPC(2n;S;P) is the count of all neighborproperty cycles for a specific set S of 2n elements and a pairproperty P. For more details, see the link and A242519.
In this case the property P is the Gray condition. The choice of the set S is important; when it is replaced by {0,1,2,...,2n1}, the sequence changes completely and becomes A236602.


LINKS

Table of n, a(n) for n=1..20.
S. Sykora, On NeighborProperty Cycles, Stan's Library, Volume V, 2014.


EXAMPLE

The two cycles for n=5 (cycle length 10) are:
C_1={1,3,7,5,4,6,2,10,8,9}, C_2={1,5,4,6,7,3,2,10,8,9}.


MATHEMATICA

A242530[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, 2 n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
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 &]];
Table[A242530[n], {n, 1, 5}]
(* OR, a less simple, but more efficient implementation. *)
A242530[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[]];
A242530[n, Join[perm, {new}],
Complement[Range[2, 2 n], perm, {new}]];
];
Return[ct];
];
];
Table[ct = 0; A242530[n, {1}, Range[2, 2 n]]/2, {n, 1, 10}] (* Robert Price, Oct 25 2018 *)


PROG

(C++) See the link.


CROSSREFS

Cf. A236602, A242519, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242531, A242532, A242533, A242534.
Sequence in context: A095217 A230915 A242922 * A073410 A021361 A199156
Adjacent sequences: A242527 A242528 A242529 * A242531 A242532 A242533


KEYWORD

nonn,hard,more


AUTHOR

Stanislav Sykora, May 30 2014


EXTENSIONS

a(16)a(20) from Fausto A. C. Cariboni, May 10 2017, May 15 2017


STATUS

approved



