|
%I #82 Feb 21 2022 01:14:48
%S 0,0,0,0,24,204,1024,3628,10320,25096,54400,107880,199400,348020,
%T 579264,926324,1431584,2148048,3141120,4490256,6291000,8656860,
%U 11721600,15641340,20597104,26797144,34479744,43915768,55411720,69312516,86004800,105919940
%N Number of ways to place 3 nonattacking queens on an n X n board.
%C Lucas mentions that the number of ways of placing p <= n non-attacking queens on an n X n chessboard is given by a polynomial in n of degree 2p and attribute the result to Mantel, professor in Delft. Cf. Stanley, exercise 15.
%D E. Landau, Naturwissenschaftliche Wochenschrift (Aug. 2 1896).
%D R. P. Stanley, Enumerative Combinatorics, vol. I, exercise 15 in chapter 4 (and its solution) asks one to show the existence of a rational generating function for the number of ways of placing k non-attacking queens on an n X n chessboard.
%H Vincenzo Librandi, <a href="/A047659/b047659.txt">Table of n, a(n) for n = 0..1000</a>
%H S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, <a href="http://www.math.binghamton.edu/zaslav/Tpapers/qq1.pdf">A q-queens problem I. General theory</a>, Jan 26 2013. - _N. J. A. Sloane_, Feb 16 2013
%H S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, <a href="http://arxiv.org/abs/1609.00853">A q-Queens Problem. IV. Queens, Bishops, Nightriders (and Rooks)</a>, arXiv:1609.00853 [math.CO], Sep 03 2016.
%H Christopher R. H. Hanusa, T Zaslavsky, S Chaiken, <a href="http://arxiv.org/abs/1609.00853">A q-Queens Problem. IV. Queens, Bishops, Nightriders (and Rooks)</a>, arXiv preprint arXiv:1609.00853 [math.CO], 2016-2020.
%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 11.
%H Edmund Landau, <a href="/A047659/a047659.pdf">Ueber das Achtdamenproblem und seine Verallgemeinerung</a>, Naturwissenschaftliche Wochenschrift, Aug 02 1896.
%H Edouard Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k3943s/f253.image">Récréations mathématiques</a>, Gauthier-Villars, Paris, 1882-1894, Vol. I, p. 228.
%H Antal Pinter, <a href="http://pinter.netii.net/queens_down.php?sifart=101&nazart=K3Queens_en_rev2.pdf">Numerical solution of the k=3 Queens problem</a>, 2011, P(3) at p.8-9.
%H I. Rivin, I. Vardi and P. Zimmermann, <a href="http://www.jstor.org/stable/2974691">The n-queens problem</a>, Amer. Math. Monthly, 101 (1994), 629-639.
%H Wenxi Wang, Muhammad Usman, Alyas Almaawi, Kaiyuan Wang, Kuldeep S. Meel, Sarfraz Khurshid, <a href="https://www.comp.nus.edu.sg/~meel/Papers/tacas20.pdf">A Study of Symmetry Breaking Predicates and Model Counting</a>, National University of Singapore (2020).
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (5,-8,0,14,-14,0,8,-5,1).
%F a(n) = n(n - 2)^2(2n^3 - 12n^2 + 23n - 10)/12 if n is even and (n - 1)(n - 3)(2n^4 - 12n^3 + 25n^2 - 14n + 1)/12 if n is odd (Landau, 1896).
%F a(n) = 5a(n - 1) - 8a(n - 2) + 14a(n - 4) - 14a(n - 5) + 8a(n - 7) - 5a(n - 8) + a(n - 9) for n >= 9.
%F G.f.: 4(9*x^4 + 35*x^3 + 49*x^2 + 21*x + 6)*x^4/((1 - x)^7*(1 + x)^2).
%F a(0)=0, a(1)=0, a(2)=0, a(3)=0, a(4)=24, a(5)=204, a(6)=1024, a(7)=3628, a(8)=10320, a(n) = 5*a(n-1)-8*a(n-2)+14*a(n-4)-14*a(n-5)+8*a(n-7)- 5*a(n-8)+ a(n-9). - _Harvey P. Dale_, Nov 06 2011
%F a(n) = n^6/6 - 5*n^5/3 + 79*n^4/12 - 25*n^3/2 + 11*n^2 - 43*n/12 + 1/8 + (-1)^n*(n/4 - 1/8) [Chaiken et al.]. - _N. J. A. Sloane_, Feb 16 2013
%F a(n) = (3*(2*n-1)*(-1)^n +4*n^6 -40*n^5 +158*n^4 -300*n^3 +264*n^2 -86*n +3)/24. - _Antal Pinter_, Oct 03 2014
%F E.g.f.: (exp(2*x)*(3 - 6*x^2 + 8*x^3 + 18*x^4 + 20*x^5 + 4*x^6) -3 - 6*x) / (24*exp(x)). - _Vaclav Kotesovec_, Feb 15 2015
%F For n>3, a(n) = A179058(n) -4*(n-2)*A000914(n-2) -2*(n-2)*A002415(n-1) + 2*A008911(n-1) +8*(A001752(n-4) +A007009(n-3)). - _Antal Pinter_, Sep 20 2015
%F In general, for m <= n, n >= 3, the number of ways to place 3 nonattacking queens on an m X n board is n^3/6*(m^3 - 3*m^2 + 2*m) - n^2/2*(3*m^3 - 9*m^2 + 6*m) + n/6*(2*m^4 + 20*m^3 - 77*m^2 + 58*m) - 1/24*(39*m^4 - 82*m^3 - 36*m^2 + 88*m) + 1/16*(2*m - 4*n + 1)*(1 + (-1)^(m+1)) + 1/2*(1 + abs(n - 2*m + 3) - abs(n - 2*m + 4))*(1/24*((n - 2*m + 11)^4 - 42*(n - 2*m + 11)^3 + 656*(n - 2*m + 11)^2 - 4518*(n - 2*m + 11) + 11583) - 1/16*(4*m - 2*n - 1)*(1 + (-1)^(n+1))) [Panos Louridas, idee & form 93/2007, pp. 2936-2938]. - _Vaclav Kotesovec_, Feb 20 2016
%p f:=n-> n^6/6 - 5*n^5/3 + 79*n^4/12 - 25*n^3/2 + 11*n^2 - 43*n/12 + 1/8 + (-1)^n*(n/4 - 1/8); [seq(f(n),n=1..40)]; # _N. J. A. Sloane_, Feb 16 2013
%t Table[If[EvenQ[n],n (n-2)^2 (2n^3-12n^2+23n-10)/12,(n-1)(n-3) (2n^4- 12n^3+25n^2-14n+1)/12],{n,0,30}] (* or *) LinearRecurrence[ {5,-8,0,14,-14,0,8,-5,1},{0,0,0,0,24,204,1024,3628,10320},30] (* _Harvey P. Dale_, Nov 06 2011 *)
%o (Magma) [(3*(2*n-1)*(-1)^n +4*n^6 -40*n^5 +158*n^4 -300*n^3 +264*n^2 -86*n +3)/24: n in [0..35]]; // _Vincenzo Librandi_, Sep 21 2015
%o (PARI) a(n)=if(n%2, (n - 1)*(n - 3)*(2*n^4 - 12*n^3 + 25*n^2 - 14*n + 1), n*(n - 2)^2*(2*n^3 - 12*n^2 + 23*n - 10))/12 \\ _Charles R Greathouse IV_, Feb 09 2017
%Y Cf. A036464, A061994, A108792, A176186, A178721.
%Y Column k=3 of A348129.
%K nonn,easy,nice
%O 0,5
%A _Paul Zimmermann_
%E The formula given in the Rivin et al. paper is wrong.
%E Entry improved by comments from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 30 2001
|
