0,5

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.

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

Edouard Lucas, Recreations mathematiques, Gauthier-Villars, Paris, 1882-1894, Vol. I, p. 228.

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

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.

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

Sequence in context: A048355 A132458 A055857 this_sequence A108671 A097321 A105946

Adjacent sequences: A047656 A047657 A047658 this_sequence A047660 A047661 A047662

nonn,easy,nice

Paul.Zimmermann(AT)loria.fr

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