cp's OEIS Frontend

A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.

%I A189281 #105 Apr 04 2024 11:42:30
%S A189281 1,1,2,5,18,75,410,2729,20906,181499,1763490,18943701,222822578,
%T A189281 2847624899,39282739034,581701775369,9202313110506,154873904848803,
%U A189281 2762800622799362,52071171437696453,1033855049655584786,21567640717569135515
%N A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.
%C A189281 a(n) is also the number of ways to place n nonattacking pieces rook + semi-leaper (2,2) on an n X n chessboard.
%C A189281 Comments from _Vaclav Kotesovec_, Mar 05 2022: (Start)
%C A189281 The original submission had keyword hard because of the following running times (in 2012):
%C A189281 a(33) 39 hours
%C A189281 a(34) 78 hours
%C A189281 a(35) 147 hours
%C A189281 The conjectured recurrence would imply the asymptotic expansion for a(n)/n! ~
%C A189281 (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.
%C A189281 This exactly matches the formula from 2011. In addition, all coefficients are integers. It is highly probable that recurrence is correct.
%C A189281 (End)
%C A189281 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
%C A189281 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
%C A189281 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
%H A189281 Rintaro Matsuo, <a href="/A189281/b189281.txt">Table of n, a(n) for n = 0..300</a> (terms 0..35 from Vaclav Kotesovec, terms 36..39 from Christoph Koutschan, computed using a parallelization of Kotesovec's Mathematica program)
%H A189281 Robert Dougherty-Bliss, <a href="https://sites.math.rutgers.edu/~zeilberg/Theses/RobertDoughertyBlissThesis.pdf">Experimental Methods in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 4.
%H A189281 Manuel Kauers, <a href="/A189281/a189281_1.txt">Comments on the Conjectured Recurrence for A189281</a>.
%H A189281 Manuel Kauers and Christoph Koutschan, <a href="https://arxiv.org/abs/2202.07966">Guessing with Little Data</a>, arXiv:2202.07966 [cs.SC], 2022.
%H A189281 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 644.
%H A189281 Vaclav Kotesovec, <a href="/A189281/a189281.txt">Mathematica program for this sequence</a>.
%H A189281 Rintaro Matsuo, <a href="https://github.com/windows-server-2003/OEIS_calculation/tree/master/contents/A189281">O(n^4) code to calculate a(n)</a>
%H A189281 George Spahn and Doron Zeilberger, <a href="https://arxiv.org/abs/2211.02550">Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s)</a>, arXiv:2211.02550 [math.CO], 2022.
%F A189281 Asymptotics: a(n)/n! ~ (1 + 3/n + 2/n^2)/e.
%F A189281 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
%F A189281 Comment from _N. J. A. Sloane_, Mar 12 2022: (Start)
%F A189281 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):
%F A189281 Conjecture: ((-1 + n)^2*n*a[n])/4 + (n*(-16 + 38*n + 11*n^2)*a[1 + n])/16 +
%F A189281 (3/2 + (139*n)/16 + (29*n^2)/8 + (3*n^3)/16)*a[2 + n] +
%F A189281 (-21/4 - (51*n)/4 - (79*n^2)/16 - (5*n^3)/8)*a[3 + n] +
%F A189281 (-15/2 - n/8 + (5*n^2)/4 + n^3/8)*a[4 + n] +
%F A189281 (603/4 + (307*n)/4 + (49*n^2)/4 + (11*n^3)/16)*a[5 + n] +
%F A189281 (-41 - (533*n)/16 - (49*n^2)/8 - (5*n^3)/16)*a[6 + n] +
%F A189281 (-911/2 - 161*n - (303*n^2)/16 - (3*n^3)/4)*a[7 + n] +
%F A189281 (-363 - (417*n)/4 - (37*n^2)/4 - n^3/4)*a[8 + n] +
%F A189281 (-993/4 - 53*n - (11*n^2)/4)*a[9 + n] + (-130 - (93*n)/4 - n^2)*a[10 + n] +
%F A189281 (-71/4 - 2*n)*a[11 + n] + (-10 - n)*a[12 + n] + a[13 + n] == 0.
%F A189281 (End)
%F A189281 From _Mark van Hoeij_, Jul 25 2012: (Start)
%F A189281 A compact way to write the order 13 recurrence is as follows:
%F A189281 Let b(n) = a(n+3) + a(n+2) + (n/2+2)*a(n+1) + (n-1)*a(n)/2
%F A189281 and c(n) = b(n+4) + (n/2+2)*b(n+2) - b(n+1)/2 + (1-n)*b(n)/2;
%F A189281 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)
%Y A189281 Cf. A000255, A002464, A055790, A110128.
%K A189281 nonn
%O A189281 0,3
%A A189281 _Vaclav Kotesovec_, Apr 19 2011