The problem of the pawns

DOI10.1007/S00026-004-0206-6MaRDI QIDQ1889892zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Toufik Mansour

Publication date 13 December 2004

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0305253

zbMATH Keywords

enumerationtransfer matricestransfer matrix methodchessboardnonattacking positions

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Asymptotic enumeration (05A16)

Abstract: In this paper we study the number $M_{m,n}$ of ways to place nonattacking pawns on an $mimesn$ chessboard. We find an upper bound for $M_{m,n}$ and analyse its asymptotic behavior. It turns out that $li{m}_{m,noinfty}(M_{m,n}{)}^{1/mn}$ exists and is bounded from above by $(1+sqrt5)/2$. Also, we consider a lower bound for $M_{m,n}$ by reducing this problem to that of tiling an $(m+1)imes(n+1)$ board with square tiles of size $1imes1$ and $2imes2$. Moreover, we use the transfer-matrix method to implement an algorithm that allows us to get an explicit formula for $M_{m,n}$ for given $m$.

Recommendations

• The problem of pawns
• The problem of the kings
• Queens on non-square tori
• scientific article; zbMATH DE number 861434
• Non-attacking Bishop and King positions on regular and cylindrical chessboards

Cited in

(8)

• Parity party with picture proofs: an odd checkerboard problem
• The problem of the moody chess players
• The problem of kings
• The problem of the kings
• The problem of pawns
• Counting kings: explicit formulas, recurrence relations, and generating functions! Oh my!
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group

This page was built for publication: The problem of the pawns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1889892)