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

1, 1, 1, 3, 6, 10, 17, 31, 57, 104, 188, 340, 616, 1117, 2025, 3670, 6651, 12054, 21847, 39596, 71764, 130065, 235730, 427238, 774328, 1403395, 2543518, 4609881, 8354965, 15142569, 27444447, 49740415, 90149708, 163387657, 296124381, 536696900

Offset

1,4

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

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

Formula

Empirical: a(n) = a(n-1)+a(n-2)+a(n-4)+a(n-5) for n>7. - Andrew Howroyd, Apr 08 2016

Empirical G.f.: x^2 + ((1-x)^2*(1+x)^2)/(1-x-x^2-x^4-x^5). - Andrew Howroyd, Apr 08 2016

Empirical first differences of A185265. - Sean A. Irvine, Jun 26 2022

Example

For n=4, The three cycles are: C_1={1,2,3,4}, C_2={1,2,4,3}, C_3={1,3,2,4}.
The first and the last of the 104 such cycles of length n=10 are: C_1={1,2,3,5,6,8,9,10,7,4}, C_104={1,3,6,9,10,8,7,5,2,4}.

Mathematica

A242525[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 &]];
Join[{1, 1}, Table[A242525[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242525[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[]];
      A242525[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Join[{1, 1},
Table[ct = 0; A242525[n, {1}, Range[2, n]]/2, {n, 3, 12}] ](* Robert Price, Oct 24 2018 *)

Prog

(C++) See the link.

Crossrefs

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

Sequence in context: A069241 A092263 A259968 * A266617 A291608 A182152

Adjacent sequences: A242522 A242523 A242524 * A242526 A242527 A242528

Keyword

nonn

Author

Stanislav Sykora, May 27 2014

Extensions

a(28)-a(35) from Andrew Howroyd, Apr 08 2016

Status

approved