login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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.

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 25 20:28 EDT 2017. Contains 289797 sequences.