\magnification 1200
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 2 (1995), \#R3\hfill\folio} \fi}
\def\vsp{-4pt}
\def\vv{\vskip 4pt}
\def\spp{\kern4pt}
\def\sp2{\kern 8pt}
\font\smmth=cmmi8
\def\one{\hbox{\smmth 1}}
\def\zero{\hbox{\smmth 0}}
\def\sqr#1{{\vcenter{\hrule height1pt
\hbox{\vrule width1pt height#1pt \kern#1pt
\vrule width1pt}
\hrule height1pt}}}
\def\squarek{\mathchoice\sqr{13}\sqr{13}\sqr{13}\sqr{13}
\kern-11.2pt \lower.9pt\hbox{{\rm K}}\kern3.4pt}
\def\square{\mathchoice\sqr{13}\sqr{13}\sqr{13}\sqr{13}\kern.0pt}
\def\vrl{\vrule height 5pt width 4pt}
\def\pce#1#2{\matrix{#1\cr#2\cr}\quad}
\def\by{\hbox{\bf y}}
\centerline{\bf The Problem of the Kings}
\vskip 12pt
\centerline{Herbert S. Wilf\footnote{$^*$}{Supported in part by the Office of Naval Research}}
\centerline{University of Pennsylvania}
\centerline{Philadelphia, PA 19104-6395}
\vskip 10pt
\centerline{Submitted: June 21, 1994; Accepted: December 9, 1994}
\vskip 30pt
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.
\vskip 10pt
\proclaim Theorem. For each $m=1,2,3,\ldots $ there are constants $c_m>0$, $d_m$, and $0\le \theta_m0$.
To do this we will construct, quite explicitly, $(n+1)(m+1)^n$ different nonattacking arrangements. Fix some $j$, $0\le j\le n$. In each of columns 1 through $j$ of the array (1), independently place any of the $(m+1)$ pieces that consist solely of 1's and 4's. In each of the remaining columns place, independently, any of the $(m+1)$ pieces that consist solely of 2's and 3's. This yields $(m+1)^n$ arrangements for each $j$, and so $f_m(n)\ge (n+1)(m+1)^n$. Hence $c_m>0$ and the theorem is proved. \vrl
The block triangularity of the transfer matrix $\Lambda$ greatly
facilitates the computation of the generating matrix $x(I-x\Lambda
)^{-1}$. In fact, since one is interested in the sum of all of the
entries of that matrix, one can avoid computing the inverse and
instead solve the simultaneous equations $(I-x\Lambda )z=e$, where $e$
is the vector of all 1's. Then $z\cdot e$ will be the required
generating function. The solution of the simultaneous system is done
using the usual recurrence formula for triangular systems, applied to
the $(m+1)\times (m+1)$ blocks.
The generating function for $m=2$ is shown in (3) above, and asymptotically we have
$$f_2(n)=17n\, 3^n-109\cdot 3^n +O(2.618..^n).$$
When $m=3$ the generating function is
$${{8\,x\,\left( -4 + 25\,x - 73\,{x^2} + 163\,{x^3} - 203\,{x^4} + 116\,{x^5} -
24\,{x^6} \right) }\over
{\left( -1 + 3\,x \right) \,{{\left( -1 + 4\,x \right) }^2}\,
{{\left( 1 - 4\,x + 2\,{x^2} \right) }^2}}},$$
from which we find
$$f_3(n)= 231\, n\, 4^n -2377\cdot 4^n-384\cdot 3^n+O(1.707..^n).$$
We have also computed that $f_4(n)\sim (7963567/2610)n5^n$.
In general, the number $\theta_m$ that appears in our Theorem can be taken to be $|\lambda_m| +\epsilon$, where $\lambda_m$ is the second-largest eigenvalue of the transfer matrix, and $\epsilon >0$ is arbitrary. We can obtain some information about $\lambda_m$ by noting that it cannot exceed the largest eigenvalue of an $(m+1)\times (m+1)$ matrix whose entries are all 1's except for a single 0 entry, the latter being off-diagonal. A simple calculation shows that the latter is
$${{m+1}\over 2}\biggl\{1+\sqrt{1-{4\over {(m+1)^2}}}\biggr\}=m+1-{1\over m}+{1\over {m^2}}-\cdots .$$
\vskip 5pt
\noindent{\bf Acknowledgement.} This lovely problem was communicated
to me by Donald Knuth, whose main interest lay in the asymptotics in
the case $m=n$. This remains an open question which seems to be
beyond the methods of this paper.
\vskip 10pt
\centerline{\bf References}
\vskip 5pt
{\parindent 12pt
\item{1.} F. R. Gantmacher, Applications of the theory of matrices,
Interscience Publishers, New York, 1959.
\item{2.} H. Wielandt, {\it Unzerlegbare, nicht negative Matrizen},
{Math. Z.} {\bf 52} (1950), 642-648.
}
\bye