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

0, 0, 0, 0, 1, 5, 33, 245, 2053, 19137, 196705, 2212037, 27029085, 356723177, 5058388153, 76712450925, 1239124984693, 21241164552785, 385159565775633, 7365975246680597, 148182892455224845, 3128251523599365177, 69149857480654157545, 1597343462243140957757

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.

Number of Hamiltonian cycles in the complement of P_n, where P_n is the n-path graph. - Andrew Howroyd, Mar 15 2016

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

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

Examples

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

Links

• Andrew Woods, Table of n, a(n) for n = 1..100 (terms up to a(24) from _Hiroaki Yamanouchi_, Aug 28 2014)
• F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
• S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
• Eric Weisstein's World of Mathematics, Dipyramidal Graph
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, Path Complement Graph
• Eric Weisstein's World of Mathematics, Radio Labeling
• Eric Weisstein's World of Mathematics, Wheel Graph

Crossrefs

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

Cf. A006184.

Programs

Mathematica

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

Formula

a(n) = A002493(n)/(2*n), n>1. - Andrew Woods, Dec 08 2014

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

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

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