The problem of the pawns

Kitaev, Sergey and Mansour, Toufik (2004) The problem of the pawns. Annals of Combinatorics, 8 (1). pp. 81-91. ISSN 0218-0006 (https://doi.org/10.1007/s00026-004-0206-6)

Full text not available in this repository.Request a copy

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.

CORE (COnnecting REpositories)