

A242522


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


17



0, 0, 0, 0, 1, 5, 33, 245, 2053, 19137, 196705, 2212037, 27029085, 356723177, 5058388153, 76712450925, 1239124984693, 21241164552785, 385159565775633, 7365975246680597, 148182892455224845, 3128251523599365177, 69149857480654157545, 1597343462243140957757
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

a(n)=NPC(n;S;P) is the count of all neighborproperty cycles for a specific set S of n elements and a specific pairproperty P. For more details, see the link and A242519.
Number of Hamiltonian cycles in the complement of P_n, where P_n is the npath graph.  Andrew Howroyd, Mar 15 2016


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), 267282.
S. Sykora, On NeighborProperty Cycles, Stan's Library, Volume V, 2014.


FORMULA

a(n) = A002493(n)/(2*n), n>1.  Andrew Woods, Dec 08 2014
a(n) = Sum_{k=1..n} (1)^(nk)*k!*A102413(n,k) / (2*n), n>2.  Andrew Woods after Vladeta Jovovic, Dec 08 2014
a(n) = (n1)!/2 + sum_{i=1..n1} ((1)^i * (ni1)! * sum_{j=0..i1} (2^j * C(i1,j) * C(ni,j+1))), for n>=5.  Andrew Woods, Jan 08 2015


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


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



