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

Abstract:

In this paper we study the number
*M*_{m,n} of ways to place nonattacking pawns on an *m** n*
chessboard. We find an upper
bound for *M*_{m,n} and consider a lower bound for
*M*_{m,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 *M*_{m,n} for given *m*.
Moreover, we show that the double limit
exists
and .
Also, the true value of is around .

References:

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.