Nonattacking queens in a rectangular strip. (English) Zbl 1233.05022

Chaiken, Seth; Hanusa, Christopher R. H.; Zaslavsky, Thomas

Ann. Comb. 14, No. 4, 419-441 (2010).

Summary: The function that counts the number of ways to place nonattacking identical chess or fairy chess pieces in a rectangular strip of fixed height and variable width, as a function of the width, is a piecewise polynomial which is eventually a polynomial and whose behavior can be described in some detail. We deduce this by converting the problem to one of counting lattice points outside an affinographic hyperplane arrangement, which Forge and Zaslavsky solved by means of weighted integral gain graphs. We extend their work by developing both generating functions and a detailed analysis of deletion and contraction for weighted integral gain graphs. For chess pieces we find the asymptotic probability that a random configuration is nonattacking, and we obtain exact counts of nonattacking configurations of small numbers of queens, bishops, knights, and nightriders.

MSC:

05A15	Exact enumeration problems, generating functions
05B30	Other designs, configurations
00A08	Recreational mathematics
05C22	Signed and weighted graphs
52C35	Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

Keywords:

nonattacking chess pieces; fairy chess pieces; affinographic arrangement of hyperplanes; weighted integral gain graph; generating function

Software:

OEIS; SF

References:

[1]	Comtet L.: Advanced Combinatorics. D. Reidel Publishing Co., Dordrecht (1974)
[2]	Forge D., Zaslavsky T.: Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements. J. Combin. Theory Ser. A 114(1), 97–109 (2007) · Zbl 1105.52014 · doi:10.1016/j.jcta.2006.03.006
[3]	Forge, D., Zaslavsky, T.: Colorations, orthotopes, and a huge polynomial Tutte invariant of weighted gain graphs. Submitted. · Zbl 1332.05065
[4]	Hanusa, C.R.H.: The WIGG (weighted integral gain graph) programs. http://people.qc.cuny.edu/faculty/christopher.hanusa/
[5]	Stanley R.P.: Enumerative Combinatorics, Vol. 1. Wadsworth & Brooks/Cole, Monterey CA (1986) · Zbl 0608.05001
[6]	Stembridge, J.: The SF package. http://www.math.lsa.umich.edu/jrs/maple.html#SF
[7]	Azemard, L.: Echecs et Mathématiques, III: une communication de Vaclav Kotesovec, Rex Multiplex 28 (1992)
[8]	Kotěšovec, V.: Mezi šachovnicí a počítačem. On line at http://members.chello.cz/chessproblems/index0.htm ; find ”Between chessboard and computer” (1996)
[9]	Kotěšovec, V.: Web page with formulas. http://web.telecom.cz/vaclav.kotesovec/math.htm#kap12 Publication list, http://members.chello.cz/chessproblems/articles.htm
[10]	Pauls E.: Das Maximalproblem der Damen auf dem Schachbrete. Deutsche Schachzeitung 29, 261–263 (1874)
[11]	N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/njas/sequences/ · Zbl 1274.11001
[12]	Tarry H.: Presentation to the Association française pour l’avancement des sciences, Limoges, 1890. L’intermédiaire des mathématiciens 10, 297–298 (1903)