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

Author

Stanislav Sykora, May 27 2014

Keywords

• nonn

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

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

Links

• Yifan Xie, Table of n, a(n) for n = 1..3000 (First 100 terms from Andrew Howroyd)
• Stanislav Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
• Yifan Xie, Proof of the formulas

Crossrefs

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

Programs

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

PARI

lista(nn) = {my(v=[1, 1, 1, 3, 6, 10, 17]); for(n=8, nn, v = concat(v, v[n-1] + v[n-2] + v[n-4] + v[n-5])); v}; \\ Yifan Xie, Mar 20 2025

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

See link for proofs of the above formulas. - Yifan Xie, Mar 19 2025

Extensions

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