cp's OEIS Frontend

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

%I A242522 #73 Feb 16 2025 08:33:22
%S A242522 0,0,0,0,1,5,33,245,2053,19137,196705,2212037,27029085,356723177,
%T A242522 5058388153,76712450925,1239124984693,21241164552785,385159565775633,
%U A242522 7365975246680597,148182892455224845,3128251523599365177,69149857480654157545,1597343462243140957757
%N A242522 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at least 2.
%C A242522 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.
%C A242522 Number of Hamiltonian cycles in the complement of P_n, where P_n is the n-path graph. - _Andrew Howroyd_, Mar 15 2016
%C A242522 a(n) also agrees with the number of optimal fundamentally distinct radio labelings of the wheel graph on (n+1) nodes for n = 5 up to at least n = 10 (and likely all larger n). - _Eric W. Weisstein_, Jan 12 2021
%C A242522 a(n) also agrees with the number of optimal fundamentally distinct radio labelings of the n-dipyramidal graph for n = 5 up to at least n = 9 (and likely all larger n). - _Eric W. Weisstein_, Jan 14 2021
%H A242522 Andrew Woods, <a href="/A242522/b242522.txt">Table of n, a(n) for n = 1..100</a> (terms up to a(24) from _Hiroaki Yamanouchi_, Aug 28 2014)
%H A242522 F. C. Holroyd and W. J. G. Wingate, <a href="http://dx.doi.org/10.1016/S0012-365X(85)80003-0">Cycles in the complement of a tree or other graph</a>, Discrete Math., 55 (1985), 267-282.
%H A242522 S. 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 A242522 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DipyramidalGraph.html">Dipyramidal Graph</a>
%H A242522 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H A242522 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>
%H A242522 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RadioLabeling.html">Radio Labeling</a>
%H A242522 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>
%F A242522 a(n) = A002493(n)/(2*n), n>1. - _Andrew Woods_, Dec 08 2014
%F A242522 a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*A102413(n,k) / (2*n), n>2. - _Andrew Woods_ after _Vladeta Jovovic_, Dec 08 2014
%F A242522 a(n) = (n-1)!/2 + sum_{i=1..n-1} ((-1)^i * (n-i-1)! * sum_{j=0..i-1} (2^j * C(i-1,j) * C(n-i,j+1))), for n>=5. - _Andrew Woods_, Jan 08 2015
%F A242522 a(n) = n a(n-1) - (n-5) a(n-2) - (n-4) a(n-3) + (n-4) a(n-4), for n>6. - _Jean-François Alcover_, Oct 07 2017
%e A242522 The 5 cycles of length n=6 having this property are {1,3,5,2,4,6}, {1,3,5,2,6,4}, {1,3,6,4,2,5}, {1,4,2,5,3,6}, {1,4,2,6,3,5}.
%t A242522 a[n_ /; n < 5] = 0; a[5] = 1; a[6] = 5; a[n_] := a[n] = n a[n - 1] - (n - 5) a[n - 2] - (n - 4) a[n - 3] + (n - 4) a[n - 4]; Array[a, 24] (* _Jean-François Alcover_, Oct 07 2017 *)
%t A242522 Join[{0, 0}, RecurrenceTable[{a[n] == n a[n - 1] - (n - 5) a[n - 2] - (n - 4) a[n - 3] + (n - 4) a[n - 4], a[3] == a[4] == 0, a[5] == 1, a[6] == 5}, a, {n, 20}]] (* _Eric W. Weisstein_, Apr 12 2018 *)
%o A242522 (C++) See the link.
%Y A242522 Cf. A242519, A242520, A242521, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242530, A242531, A242532, A242533, A242534.
%Y A242522 Cf. A006184.
%K A242522 nonn
%O A242522 1,6
%A A242522 _Stanislav Sykora_, May 27 2014