login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A189281 Number of permutations p of 1,2,...,n satisfying p(i+2)-p(i)<>2 for all 1<=i<=n-2. 6
1, 1, 2, 5, 18, 75, 410, 2729, 20906, 181499, 1763490, 18943701, 222822578, 2847624899, 39282739034, 581701775369, 9202313110506, 154873904848803, 2762800622799362, 52071171437696453, 1033855049655584786, 21567640717569135515 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) is also the number of ways to place n nonattacking pieces rook + semi-leaper[2,2] on an n X n chessboard.

Comments from Vaclav Kotesovec, Mar 05 2022: (Start)

The original submission had keyword hard because of the following running times (in 2012):

a(33) 39 hours

a(34) 78 hours

a(35) 147 hours

The conjectured recurrence would imply the asymptotic expansion for a(n)/n! ~

(1 + 3/n + 2/n^2 + 1/n^3 + 0/n^4 + 3/n^5 + 26/n^6 + 101/n^7 + 124/n^8 - 1409/n^9 - 13266/n^10)/e.

This exactly matches the formula from 2011. In addition, all coefficients are integers. It is highly probable that recurrence is correct.

(End)

There are good reasons to believe the conjecture is correct. (It has the expected form.)  The problem is one of counting Hamiltonian cycles in the complement of some simple graph. There is a method for counting these efficiently (although I have not implemented in code). Similar to A242522 / A229430. - Andrew Howroyd, Mar 06 2022

See also Manuel Kauers's comments below. Since the four new terms took weeks of computation, the keyword "hard" continues to be justified. - N. J. A. Sloane, Mar 06 2022

LINKS

Christoph Koutschan, Table of n, a(n) for n = 0..39 [Terms 0..35 from Vaclav Kotesovec. The new terms were computed using a parallelization of Kotesovec's Mathematica program]

Manuel Kauers, Comments on the Conjectured Recurrence for A189281.

Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 644.

Vaclav Kotesovec, Mathematica program for this sequence

FORMULA

Asymptotics: a(n)/n! ~ (1 + 3/n + 2/n^2)/e.

Conjectured recurrence of degree 11 and order 8: (262711*n + 1387742*n^2 - 824875*n^3 - 1855253*n^4 - 111530*n^5 + 680983*n^6 + 364242*n^7 + 84992*n^8 + 10332*n^9 + 640*n^10 + 16*n^11)*a(n) + (-1050844*n - 9705192*n^2 - 7414683*n^3 + 3536494*n^4 + 6459004*n^5 + 3326393*n^6 + 903534*n^7 + 144684*n^8 + 13756*n^9 + 720*n^10 + 16*n^11)*a(n+1) + (3492344 - 2212342*n - 8507169*n^2 - 11544227*n^3 - 12034116*n^4 - 8216995*n^5 - 3442049*n^6 - 890050*n^7 - 142300*n^8 - 13660*n^9 - 720*n^10 - 16*n^11)*a(n+2) + (19817984 + 45323852*n + 825228*n^2 - 57004661*n^3 - 57059306*n^4 - 28077270*n^5 - 8398637*n^6 - 1631510*n^7 - 207980*n^8 - 16828*n^9 - 784*n^10 - 16*n^11)*a(n+3) + (9586160 + 6680237*n - 13772613*n^2 - 27689586*n^3 - 22162455*n^4 - 9855085*n^5 - 2629562*n^6 - 427656*n^7 - 41332*n^8 - 2176*n^9 - 48*n^10)*a(n+4) + (22192864 + 44710768*n - 2924668*n^2 - 52385912*n^3 - 45161616*n^4 - 18784740*n^5 - 4549208*n^6 - 674256*n^7 - 60400*n^8 - 3008*n^9 - 64*n^10)*a(n+5) + (557152 - 2032472*n - 2937392*n^2 - 1594200*n^3 - 517688*n^4 - 122032*n^5 - 19856*n^6 - 1792*n^7 - 64*n^8)*a(n+6) + (3786960 + 7105324*n - 1191064*n^2 - 8059160*n^3 - 5938996*n^4 - 2073752*n^5 - 402736*n^6 - 44528*n^7 - 2624*n^8 - 64*n^9)*a(n+7) + (-598208 - 943004*n + 414196*n^2 + 1213772*n^3 + 728648*n^4 + 203584*n^5 + 29616*n^6 + 2176*n^7 + 64*n^8)*a(n+8) = 0. This recurrence correctly predicted the four new terms in the b-file. - Christoph Koutschan, Feb 19 2022

Comment from N. J. A. Sloane, Mar 12 2022: (Start)

The preceding conjectured recurrence is equivalent to the following, which has degree 3 and order 13, and was obtained by Doron Zeilberger and then reformatted by Manuel Kauers (it uses Mathematica syntax):

Conjecture: ((-1 + n)^2*n*a[n])/4 + (n*(-16 + 38*n + 11*n^2)*a[1 + n])/16 +

(3/2 + (139*n)/16 + (29*n^2)/8 + (3*n^3)/16)*a[2 + n] +

(-21/4 - (51*n)/4 - (79*n^2)/16 - (5*n^3)/8)*a[3 + n] +

(-15/2 - n/8 + (5*n^2)/4 + n^3/8)*a[4 + n] +

(603/4 + (307*n)/4 + (49*n^2)/4 + (11*n^3)/16)*a[5 + n] +

(-41 - (533*n)/16 - (49*n^2)/8 - (5*n^3)/16)*a[6 + n] +

(-911/2 - 161*n - (303*n^2)/16 - (3*n^3)/4)*a[7 + n] +

(-363 - (417*n)/4 - (37*n^2)/4 - n^3/4)*a[8 + n] +

(-993/4 - 53*n - (11*n^2)/4)*a[9 + n] + (-130 - (93*n)/4 - n^2)*a[10 + n] +

(-71/4 - 2*n)*a[11 + n] + (-10 - n)*a[12 + n] + a[13 + n] == 0.

(End)

From Mark van Hoeij, Jul 25 2012: (Start)

A compact way to write the order 13 recurrence is as follows:

Let b(n) = a(n+3) + a(n+2) + (n/2+2)*a(n+1) + (n-1)*a(n)/2

and c(n) = b(n+4) + (n/2+2)*b(n+2) - b(n+1)/2 + (1-n)*b(n)/2;

then c(n+6) - (n+11)*c(n+5) - (2*n+75/4)*c(n+4) + (3-n)*c(n+3)/4 - c(n+2)/2 - (7*n+22)*c(n+1)/4-n*c(n) = 0. (End)

CROSSREFS

Cf. A000255, A002464, A055790, A110128.

Sequence in context: A352985 A319121 A289655 * A006848 A208968 A338179

Adjacent sequences:  A189278 A189279 A189280 * A189282 A189283 A189284

KEYWORD

nonn,hard

AUTHOR

Vaclav Kotesovec, Apr 19 2011

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 03:38 EDT 2022. Contains 356029 sequences. (Running on oeis4.)