|
| |
|
|
A189281
|
|
Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.
|
|
7
|
|
|
|
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.
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
a(40)-a(300) were computed using an independent solution (dynamic programming, O(N^4) per term), and the conjectured recurrence was further confirmed to be correct up to n=300. Consequently, the keyword "hard" is removed. - Rintaro Matsuo, Oct 18 2022
|
|
|
LINKS
|
Rintaro Matsuo, Table of n, a(n) for n = 0..300 (terms 0..35 from Vaclav Kotesovec, terms 36..39 from Christoph Koutschan, computed using a parallelization of Kotesovec's Mathematica program)
|
|
|
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
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)
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
