A242522 - OEIS

%I #72 Jan 22 2021 14:22:36

%S 0,0,0,0,1,5,33,245,2053,19137,196705,2212037,27029085,356723177,

%T 5058388153,76712450925,1239124984693,21241164552785,385159565775633,

%U 7365975246680597,148182892455224845,3128251523599365177,69149857480654157545,1597343462243140957757

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

%C 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 Number of Hamiltonian cycles in the complement of P_n, where P_n is the n-path graph. - _Andrew Howroyd_, Mar 15 2016

%C 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DipyramidalGraph.html">Dipyramidal Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RadioLabeling.html">Radio Labeling</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>

%F a(n) = A002493(n)/(2*n), n>1. - _Andrew Woods_, Dec 08 2014

%F 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 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 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 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 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 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 (C++) See the link.

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

%Y Cf. A006184.

%K nonn

%O 1,6

%A _Stanislav Sykora_, May 27 2014