The problem of the kings

Herbert S. Wilf

The electronic journal of combinatorics, Tome 2 (1995)

Résumé

On a $2m\times 2n$ chessboard, the maximum number of nonattacking kings that can be placed is $mn$, since each $2\times 2$ cell can have at most one king. Let $f_m(n)$ denote the number of ways that $mn$ nonattacking kings can be placed on a $2m\times 2n$ chessboard. The purpose of this paper is to prove the following result. Theorem. For each $m=1,2,3,\ldots $ there are constants $c_m>0$, $d_m$, and $0\le \theta_m < m+1$ such that $$f_m(n)= (c_mn+d_m)(m+1)^n+O(\theta_m^n)\qquad (n\to\infty).$$

Détail

DOI : 10.37236/1197

Classification : 05A15, 05B30, 05A10
Mots-clés : chessboard, maximum number, nonattacking kings, number of ways