The problem of the pawns

Sergey Kitaev, Toufik Mansour

Research output: Contribution to journal › Article

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.
LanguageEnglish
Pages81-91
Number of pages11
JournalAnnals of Combinatorics
Volume8
Issue number1
DOIs
Publication statusPublished - May 2004

Fingerprint

Transfer Matrix Method
Tile
Tiling
Explicit Formula
Asymptotic Behavior
Lower bound
Upper bound

Keywords

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

Cite this

Kitaev, Sergey ; Mansour, Toufik. / The problem of the pawns. In: Annals of Combinatorics. 2004 ; Vol. 8, No. 1. pp. 81-91.
@article{66d7808d5fa643328d489c902bce208b,
title = "The problem of the pawns",
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.",
keywords = "nonattacking placements, pawns, tilings, transfer matrices, asymptotic value, chess",
author = "Sergey Kitaev and Toufik Mansour",
year = "2004",
month = "5",
doi = "10.1007/s00026-004-0206-6",
language = "English",
volume = "8",
pages = "81--91",
journal = "Annals of Combinatorics",
issn = "0218-0006",
number = "1",

}

Kitaev, S & Mansour, T 2004, 'The problem of the pawns' Annals of Combinatorics, vol. 8, no. 1, pp. 81-91. https://doi.org/10.1007/s00026-004-0206-6

The problem of the pawns. / Kitaev, Sergey; Mansour, Toufik.

In: Annals of Combinatorics, Vol. 8, No. 1, 05.2004, p. 81-91.

Research output: Contribution to journal › Article

TY - JOUR

T1 - The problem of the pawns

AU - Kitaev, Sergey

AU - Mansour, Toufik

PY - 2004/5

Y1 - 2004/5

N2 - 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.

AB - 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.

KW - nonattacking placements

KW - pawns

KW - tilings

KW - transfer matrices

KW - asymptotic value

KW - chess

UR - http://link.springer.com/journal/26

U2 - 10.1007/s00026-004-0206-6

DO - 10.1007/s00026-004-0206-6

M3 - Article

VL - 8

SP - 81

EP - 91

JO - Annals of Combinatorics

T2 - Annals of Combinatorics

JF - Annals of Combinatorics

SN - 0218-0006

IS - 1

ER -

Kitaev S, Mansour T. The problem of the pawns. Annals of Combinatorics. 2004 May;8(1):81-91. https://doi.org/10.1007/s00026-004-0206-6

Access to Document