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,6

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

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

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

Example

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

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

Prog

(C++) See the link.

Crossrefs

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

Cf. A006184.

Sequence in context: A084131 A084771 A153398 * A034015 A268563 A056159

Adjacent sequences: A242519 A242520 A242521 * A242523 A242524 A242525

Keyword

nonn

Author

Stanislav Sykora, May 27 2014

Status

approved