### Abstract

Language | English |
---|---|

Pages | 81-91 |

Number of pages | 11 |

Journal | Annals of Combinatorics |

Volume | 8 |

Issue number | 1 |

DOIs | |

Publication status | Published - May 2004 |

### Fingerprint

### Keywords

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

### Cite this

*Annals of Combinatorics*,

*8*(1), 81-91. https://doi.org/10.1007/s00026-004-0206-6

}

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

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 -