A242524 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at least 4.

0, 0, 0, 0, 0, 0, 0, 0, 1, 24, 504, 8320, 131384, 2070087, 33465414, 561681192, 9842378284, 180447203232, 3462736479324, 69517900171056, 1458720714556848, 31955023452174314, 729874911380470641, 17359562438053760533, 429391730229931885360

Offset: 1

Author

Stanislav Sykora, May 27 2014

Keywords

• nonn
• hard

Comments

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S of n elements and a specific pair-property P. For more details, see the link and A242519.

Examples

			The shortest such cycle has length n=9: {1,5,9,4,8,3,7,2,6}.
		

Links

• Hiroaki Yamanouchi, Table of n, a(n) for n = 1..27 (terms a(1)-a(16) from _Stanislav Sykora_)
• S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.

Crossrefs

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

Programs

Mathematica

A242524[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], # < 4 &]];
Table[A242524[n], {n, 1, 10}]
 (* OR, a less simple, but more efficient implementation. *)
A242524[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[Abs[First[perm] - Last[perm]] >= 4, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[Abs[Last[perm] - new] < 4, Continue[]];
      A242524[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242524[n, {1}, Range[2, n]]/2, {n, 1, 12}] (* Robert Price, Oct 24 2018 *)

Extensions

a(17)-a(25) from Hiroaki Yamanouchi, Aug 29 2014