cp's OEIS Frontend

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

%I A242525 #38 Mar 26 2025 22:18:02
%S A242525 1,1,1,3,6,10,17,31,57,104,188,340,616,1117,2025,3670,6651,12054,
%T A242525 21847,39596,71764,130065,235730,427238,774328,1403395,2543518,
%U A242525 4609881,8354965,15142569,27444447,49740415,90149708,163387657,296124381,536696900
%N A242525 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at most 3.
%C A242525 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.
%H A242525 Yifan Xie, <a href="/A242525/b242525.txt">Table of n, a(n) for n = 1..3000 (First 100 terms from Andrew Howroyd)</a>
%H A242525 Stanislav Sykora, <a href="http://dx.doi.org/10.3247/SL5Math14.002">On Neighbor-Property Cycles</a>, <a href="http://ebyte.it/library/Library.html#math">Stan's Library</a>, Volume V, 2014.
%H A242525 Yifan Xie, <a href="/A242525/a242525.txt">Proof of the formulas</a>
%F A242525 Empirical: a(n) = a(n-1)+a(n-2)+a(n-4)+a(n-5) for n>7. - _Andrew Howroyd_, Apr 08 2016
%F A242525 Empirical G.f.: x^2 + ((1-x)^2*(1+x)^2)/(1-x-x^2-x^4-x^5). - _Andrew Howroyd_, Apr 08 2016
%F A242525 Empirical first differences of A185265. - _Sean A. Irvine_, Jun 26 2022
%F A242525 See link for proofs of the above formulas. - _Yifan Xie_, Mar 19 2025
%e A242525 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}.
%e A242525 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}.
%t A242525 A242525[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
%t A242525 j1f[x_] := Join[{1}, x, {1}];
%t A242525 lpf[x_] := Length[Select[Abs[Differences[x]], # > 3 &]];
%t A242525 Join[{1, 1}, Table[A242525[n], {n, 3, 10}]]
%t A242525 (* OR, a less simple, but more efficient implementation. *)
%t A242525 A242525[n_, perm_, remain_] := Module[{opt, lr, i, new},
%t A242525    If[remain == {},
%t A242525      If[Abs[First[perm] - Last[perm]] <= 3, ct++];
%t A242525      Return[ct],
%t A242525      opt = remain; lr = Length[remain];
%t A242525      For[i = 1, i <= lr, i++,
%t A242525       new = First[opt]; opt = Rest[opt];
%t A242525       If[Abs[Last[perm] - new] > 3, Continue[]];
%t A242525       A242525[n, Join[perm, {new}],
%t A242525        Complement[Range[2, n], perm, {new}]];
%t A242525       ];
%t A242525      Return[ct];
%t A242525      ];
%t A242525    ];
%t A242525 Join[{1, 1},
%t A242525 Table[ct = 0; A242525[n, {1}, Range[2, n]]/2, {n, 3, 12}] ](* _Robert Price_, Oct 24 2018 *)
%o A242525 (C++) See the link.
%o A242525 (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
%Y A242525 Cf. A242519, A242520, A242521, A242522, A242523, A242524, A242526, A242527, A242528, A242529, A242530, A242531, A242532, A242533, A242534.
%K A242525 nonn
%O A242525 1,4
%A A242525 _Stanislav Sykora_, May 27 2014
%E A242525 a(28)-a(35) from _Andrew Howroyd_, Apr 08 2016