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

0, 0, 0, 0, 0, 0, 1, 11, 125, 1351, 15330, 184846, 2382084, 32795170, 481379278, 7513591430, 124363961357, 2176990766569, 40199252548280, 781143277669538, 15937382209774353, 340696424417421213, 7616192835573406931, 177723017354688250713, 4321711817908214684734

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 cycle with this property has length n=7: {1,4,7,3,6,2,5}.
		

Links

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

Crossrefs

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

Programs

Mathematica

A242523[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]], # < 3 &]];
Table[A242523[n], {n, 1, 10}]
 (* OR, a less simple, but more efficient implementation. *)
A242523[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[Abs[First[perm] - Last[perm]] >= 3, 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] < 3, Continue[]];
      A242523[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242523[n, {1}, Range[2, n]]/2, {n, 1, 11}] (* Robert Price, Oct 24 2018 *)

Extensions

a(16)-a(25) from Hiroaki Yamanouchi, Aug 28 2014