login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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, January 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.

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.

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

CROSSREFS

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

Sequence in context: A239574 A223748 A269691 * 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 4 21:09 EST 2016. Contains 278755 sequences.