<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
The Problem of the Pawns
Sergey Kitaev and Toufik Mansour
Matematik, Chalmers tekniska högskola och Göteborgs universitet, 412 96 Göteborg, Sweden
{kitaev, toufik}@math.chalmers.se
Annals of Combinatorics 8 (1) p.81-91 March, 2004
AMS Subject Classification: 05A16, 05C50, 52C20, 82B20
In this paper we study the number Mm,n of ways to place nonattacking pawns on an m n chessboard. We find an upper bound for Mm,n and consider a lower bound for Mm,n by reducing this problem to that of tiling an (m+1) (n+1) board with square tiles of size 11 and 22. Also, we use the transfer-matrix method to implement an algorithm that allows us to get an explicit formula for Mm,n for given m. Moreover, we show that the double limit exists and . Also, the true value of is around .
Keywords: pawns, nonattacking placements, tilings, transfer matrices, asymptotic value


1. N. Calkin and H. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math. 11 (1) (1998) 54–60.

2. P. Chinn and S. Heubach, Patterns arising from tiling rectangles with 1×1 and 2×2 squares, Congr. Numer. 150 (2001) 173–192.

3. I. Flores, k-Generalized Fibonacci numbers, Fibonacci Quart. 5 (1967) 258–266.

4. S. Heubach, Tiling an n-by-m area with squares of size up to k-by-k (m ≤ 5), Congr. Numer. 140 (1999) 43–64.

5. T. Mansour, Pawns, Maple Programming, http://www.math.chalmers.se/~toufik.

6. N.J.A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York, 1995.

7. H. Wilf, The problem of the kings, Elect. J. Combin. 2 (1995) #R3.