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 Mm,n and analyse its asymptotic behavior. It turns out that lim_{m,n→∞}(M_{m,n})1/mn exists and is bounded from above by (1+\sqrt{5})/2. Also, we 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 1×1 and 2×2. Moreover, we use the transfer-matrix method to implement an algorithm that allows us to get an explicit formula for Mm,n for given m.
Original language | English |
---|---|
Pages (from-to) | 81-91 |
Number of pages | 11 |
Journal | Annals of Combinatorics |
Volume | 8 |
Issue number | 1 |
DOIs | |
Publication status | Published - May 2004 |
Keywords
- nonattacking placements
- pawns
- tilings
- transfer matrices
- asymptotic value
- chess