login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047659 Number of ways to place 3 nonattacking queens on an n X n board. 21
0, 0, 0, 0, 24, 204, 1024, 3628, 10320, 25096, 54400, 107880, 199400, 348020, 579264, 926324, 1431584, 2148048, 3141120, 4490256, 6291000, 8656860, 11721600, 15641340, 20597104, 26797144, 34479744, 43915768, 55411720, 69312516, 86004800, 105919940 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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.

REFERENCES

E. Landau, Naturwissenschaftliche Wochenschrift (Aug. 2 1896).

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.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-queens problem I. General theory, Jan 26 2013. - N. J. A. Sloane, Feb 16 2013

S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, A q-Queens Problem. IV. Queens, Bishops, Nightriders (and Rooks), arXiv:1609.00853 [math.CO], Sep 03 2016.

Christopher R. H. Hanusa, T Zaslavsky, S Chaiken, A q-Queens Problem. IV. Queens, Bishops, Nightriders (and Rooks), arXiv preprint arXiv:1609.00853 [math.CO], 2016-2020.

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 11.

Edmund Landau, Ueber das Achtdamenproblem und seine Verallgemeinerung, Naturwissenschaftliche Wochenschrift, Aug 02 1896.

Edouard Lucas, Récréations mathématiques, Gauthier-Villars, Paris, 1882-1894, Vol. I, p. 228.

Antal Pinter, Numerical solution of the k=3 Queens problem, 2011, P(3) at p.8-9.

I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639.

Wenxi Wang, Muhammad Usman, Alyas Almaawi, Kaiyuan Wang, Kuldeep S. Meel, Sarfraz Khurshid, A Study of Symmetry Breaking Predicates and Model Counting, National University of Singapore (2020).

Index entries for linear recurrences with constant coefficients, signature (5,-8,0,14,-14,0,8,-5,1).

FORMULA

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).

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.

G.f.: 4(9*x^4 + 35*x^3 + 49*x^2 + 21*x + 6)*x^4/((1 - x)^7*(1 + x)^2).

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

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

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

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

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

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

MAPLE

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

MATHEMATICA

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 *)

PROG

(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

(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

CROSSREFS

Cf. A036464, A061994, A108792, A176186, A178721.

Sequence in context: A269691 A282644 A283540 * A108671 A097321 A105946

Adjacent sequences:  A047656 A047657 A047658 * A047660 A047661 A047662

KEYWORD

nonn,easy,nice

AUTHOR

Paul Zimmermann

EXTENSIONS

The formula given in the Rivin et al. paper is wrong.

Entry improved by comments from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 30 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 29 19:26 EST 2020. Contains 338769 sequences. (Running on oeis4.)