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

0, 0, 1, 0, 2, 8, 0, 0, 224, 754, 0, 26256, 0, 0, 22472304, 0, 90654576, 277251016, 0, 7852128780

Offset: 1

Author

Stanislav Sykora, May 30 2014

Keywords

• nonn
• hard
• more

Comments

Here, a(n)=NPC(2n;S;P) is the count of all neighbor-property cycles for a specific set S of 2n elements and a pair-property 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,...,2n-1}, the sequence changes completely and becomes A236602.

Examples

			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}.
		

Links

• S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.

Crossrefs

Cf. A236602, A242519, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242531, A242532, A242533, A242534.

Programs

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 *)

Extensions

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