The problem of the pawns

Sergey Kitaev, Toufik Mansour

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)81-91
Number of pages11
JournalAnnals of Combinatorics
Volume8
Issue number1
DOIs
Publication statusPublished - May 2004

    Fingerprint

Keywords

  • nonattacking placements
  • pawns
  • tilings
  • transfer matrices
  • asymptotic value
  • chess

Cite this