|
%I #39 May 01 2022 01:39:17
%S 0,0,0,0,2,82,982,7002,34568,131248,412596,1123832,2739386,6106214,
%T 12654614,24675650,45704724,80999104,138170148,227938788,365106738,
%U 569681574,868289594,1295775946,1897176508,2729909796
%N Number of ways to place 4 nonattacking queens on an n X n board.
%C An analytical solution for the 4-queens problem permits us to combine six particular cases into a single "unified" expression: a(n) = n(n-1)(45n^6 - 855n^5 + 6945n^4 - 30891n^3 + 78864n^2 - 106226n + 53404)/1080 + (n^3 - 21/2n^2 + 28n - 14)*floor(n/2) + 32/9(n-1)*floor(n/3) + (16/9n-4)*floor((n+1)/3). The method used to derive this formula helps to fine-tune an estimate by E. Lucas for a(n) (see comment to A047659 "3-queens problem"). For any fixed value of k > 1, a(n) = n^(2k)/k! - 5/3n^(2k-1)/(k-2)! + O(n^(2k-2)). - _Sergey Perepechko_, Sep 16 2005
%D Vaclav Kotesovec, Between chessboard and computer, 1996, pp. 204-206.
%H Vincenzo Librandi, <a href="/A061994/b061994.txt">Table of n, a(n) for n = 0..1000</a>
%H Louis Azemard, <a href="http://problem64.beda.cz/silo/azemard_vk_rm1992.pdf">Une communication de Vaclav Kotesovec</a>, Echecs et Mathématiques, Rex Multiplex 38/1992.
%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 12.
%H <a href="/index/Rec#order_17">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-9,0,12,7,-15,-16,16,15,-7,-12,0,9,-1,-3,1).
%F G.f.: x^4*(2 + 76*x + 734*x^2 + 3992*x^3 + 13318*x^4 + 29356*x^5 + + 46304*x^6 + + 53580*x^7 + 46890*x^8 + 29768*x^9 + 13522*x^10 + 3804*x^11 + 574*x^12)/((1-x)^3*(1-x^2)^4*(1-x^3)^2).
%F Recurrence: a(n) = 3*a(n-1) + a(n-2) - 9*a(n-3) + 12*a(n-5) + 7*a(n-6) - 15*a(n-7) - 16*a(n-8) + 16*a(n-9) + 15*a(n-10) - 7*a(n-11) - 12*a(n-12) + 9*a(n-14) - a(n-15) - 3*a(n-16) + a(n-17), n >= 17.
%F Explicit formula (V. Kotesovec, 1992) for n >= 2: a(n) = n^8/24 - 5*n^7/6 + 65*n^6/9 - 1051*n^5/30 + 817*n^4/8 added to one of the following terms:
%F - 4769*n^3/27 + 1963*n^2/12 - 1769*n/30 if n = 0 (mod 6)
%F - 9565*n^3/54 + 1013*n^2/6 - 6727*n/90 + 257/27 if n = 1 (mod 6)
%F - 4769*n^3/27 + 1963*n^2/12 - 5467*n/90 + 28/27 if n = 2 (mod 6)
%F - 9565*n^3/54 + 1013*n^2/6 - 2189*n/30 + 7 if n = 3 (mod 6)
%F - 4769*n^3/27 + 1963*n^2/12 - 5467*n/90 + 68/27 if n = 4 (mod 6)
%F - 9565*n^3/54 + 1013*n^2/6 - 6727*n/90 + 217/27 if n = 5 (mod 6).
%F a(n) = n^8/24 - 5n^7/6 + 65n^6/9 - 1051n^5/30 + 817n^4/8 - 19103n^3/108 + 3989n^2/24 - 18131n/270 + 253/54 + (n^3/4 - 21n^2/8 + 7n - 7/2)*(-1)^n + 32*(n - 1)/27*cos(2*Pi*n/3) + 40/81*sqrt(3)*sin(2*Pi*n/3). - _Vaclav Kotesovec_, Feb 11 2010
%F E.g.f.: (3*(exp(2*x)*(5060 - 4645*x + 1755*x^2 - 590*x^3 + 480*x^4 + 414*x^5 + 870*x^6 + 360*x^7 + 45*x^8) - 135*(28 + 37*x + 15*x^2 + 2*x^3)) - 1920 * exp(x/2) * (2+x) * cos(sqrt(3)*x/2) - 320 * sqrt(3) * exp(x/2) * (6*x-5) * sin(sqrt(3)*x/2)) / (3240 * exp(x)). - _Vaclav Kotesovec_, Feb 15 2015
%t CoefficientList[Seriesx^4*(2 +76*x +734*x^2 +3992*x^3 +13318*x^4 +29356*x^5 +46304*x^6 +53580*x^7 +46890*x^8 +29768*x^9 +13522*x^10 +3804*x^11 +574*x^12)/((1-x)^3*(1-x^2)^4*(1-x^3)^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, May 12 2013 *)
%t LinearRecurrence[{3,1,-9,0,12,7,-15,-16,16,15,-7,-12,0,9,-1,-3,1}, {0,0,0,0,2,82, 982,7002,34568,131248,412596,1123832,2739386,6106214,12654614,24675650, 45704724}, 40] (* _Harvey P. Dale_, Jan 21 2017 *)
%o (SageMath)
%o def p(x): return x^4*(2 +76*x +734*x^2 +3992*x^3 +13318*x^4 +29356*x^5 +46304*x^6 +53580*x^7 +46890*x^8 +29768*x^9 +13522*x^10 +3804*x^11 +574*x^12)/((1-x)^3*(1-x^2)^4*(1-x^3)^2)
%o def A061994_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( p(x) ).list()
%o A061994_list(40) # _G. C. Greubel_, Apr 30 2022
%Y Cf. A036464, A047659.
%Y Column k=4 of A348129.
%K nonn,nice,easy
%O 0,5
%A Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 31 2001
%E Minor edits by _Vaclav Kotesovec_, Feb 15 2015
|
