The problem of the pawns

الأصل · EN

In this paper we study the number Mₘ,ₙ of ways to place nonattacking pawns on an m× n chessboard. We find an upper bound for Mₘ,ₙ and analyse its asymptotic behavior. It turns out that ₘ,ₙ→∞(Mₘ,ₙ)1/mn exists and is bounded from above by (1+√5)/2. Also, we consider a lower bound for Mₘ,ₙ 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 Mₘ,ₙ for given m.