%Version 4.3

\magnification = \magstep1
\input epsf
\def\implies{\Rightarrow}
\def\LP{\left(}
\def\RP{\right)}
\def\a{{\bf a}}
\def\b{{\bf b}}
\def\e{{\bf e}}
\def\x{{\bf x}}
\def\sgn{{\rm sgn}}
\baselineskip = 11pt
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1
{\smcp the electronic journal of combinatorics 2 (1995), \#R18\hfill\folio} \fi}\centerline{The Problem of Kings}\medskip
\centerline{Michael Larsen\footnote*{Partially supported by
N.S.A. Grant No. MDA 904-92-H-3026}}
\centerline{University of Pennsylvania}
\centerline{Philadelphia, PA 19104}
\centerline{\tt larsen@math.upenn.edu}
\vskip 5pt
\centerline{Submitted: May 30, 1994; Accepted: September 23, 1995}
\vskip 10pt
%Begin Abstract
\centerline{\bf Abstract}
\vskip 5pt
Let $f(n)$ denote the number of
configurations of $n^2$ mutually non-attacking kings
on a $2n\times 2n$ chessboard. We show
that $\log f(n)$ grows like $2n\log n - 2n\log 2$,
with an error term of $O(n^{4/5}\log n)$.  The result depends
on an estimate for the sum of the entries of a high power of a matrix
with positive entries.
%End Abstract
\vskip 15pt
In chess, two kings can attack one another if their squares are
horizontally, vertically, or diagonally adjacent. 
Consider the problem of placing mutually non-attacking
kings on a chessboard with $2m$ rows and $2n$ columns.
Partitioning the chessboard into $2\times 2$ {\it cells},
we see that no cell can contain more than one king, so
there can be no more than $mn$ kings:
$$\displaylines{\hfill\epsfbox{fig1.eps}\hfill\cr
\hfill\hfill{\it Figure\ 1}\hfill\cr}$$
In this note, we estimate the number $K(m,n)$
of configurations of $mn$ kings.  H. Wilf [5] has
obtained good estimates
in the case that $m$ is fixed and $n\gg m$.
We consider the order of growth when both $m$ and $n$
tend to infinity, and especially the case $m=n$.
Our main result is stated at the end of the paper.

Before proceeding with the problem of kings, it may be worth a brief
look at the analogous problem for other chess pieces.
No more than $n$ mutually non-attacking rooks can fit
on an $n\times n$ board; the legal configurations have one rook
in each row and column and are therefore given by the
$n!$ permutations.
It is known that there exist configurations
of $n$ mutually non-attacking queens as long as $n\ge 4$, and the number
of such configurations is conjecturally super-exponential
in $n$ [4].  For bishops, it is not too difficult to
see that there are exactly $2^n$ ways of placing $2n-2$ pieces
on an $n\times n$ board, when $n > 1$ [3].  The maximum number of knights
on an $n\times n$ board is $\lfloor{n^2+1\over 2}\rfloor$, when $n>2$.
For $n > 4$, the number of such configurations is $1$ or $2$ according
to whether $n$ is odd or even; this follows from the existence of a
knight's tour (resp. a closed knight's tour) [3].

All such problems can be reformulated in the language of statistical
mechanics, but from this point of view the problem of kings is
certainly the most natural.  Assign spin at each vertex in a
(region of a) square lattice according to whether there is or is not 
a king in the corresponding square of the chessboard.
The generating function $\sum_n a_n z^n$
for the number of configurations of $n$ kings is 
closely related to the $L = M = -\infty$ limit of
partition function of Baxter's ``hard square model'' [1]\ \S 14.2.
The only difference is that in the hard square model, a king on a
corner (resp. edge) of the board counts for only one quarter
(resp. one half).
Of course, questions in statistical mechanics can
be quite sensitive to boundary conditions; see, {\it e.g.}, [3].
In any case,
the hard square model has been solved in certain regions of the $(L,M)$
plane, but not in the ``unphysical'' third quadrant.

Our approach to the problem of the kings is completely
elementary.  It depends on estimates for the entries of powers of matrices.
These depend, in turn, on eigenvalue estimates.  It is clear that
for fixed $M$, the entries of $M^n$ grow like polynomial multiples
of $R^n$, where $R$ is the largest eigenvalue of $n$.  The coefficients
of this polynomial can be bounded if the entries of $M$ are bounded.
Theorem 2 below gives the estimates we need, which may be be of some
independent interest.

I would like to thank Herb Wilf for introducing me to this problem
and the referee for suggesting the simplified proof of Theorem 2
which appears below.
\bigskip
To each configuration of $mn$ kings on a $2m\times 2n$ chessboard,
we associate two diagrams.  Each diagram consists of an $m\times n$
array of squares, with an arrow in each square.  Squares are labelled by
an ordered pair $(i,j)$, $1\le i\le n$, $1\le j\le m$, with the top
row is labelled $m$ and the bottom row $1$.
A square in the
{\it vertical} diagram contains a $\uparrow$ if the corresponding
cell on the chessboard contains a king in one of its two upper
squares; otherwise it contains a $\downarrow$.  Thus figure 1 has the following vertical diagram:
$$\displaylines{\hfill\epsfbox{fig2.eps}\hfill\cr
\hfill\hfill{\it Figure\ 2}\hfill\cr}$$
Likewise, each square in the horizontal diagram contains a $\gets$ if
the king in the corresponding cell is in one of the two left squares of
the cell; otherwise it contains a $\to$.  The
horizontal diagram of figure 1 is
$$\displaylines{\hfill\epsfbox{fig3.eps}\hfill\cr
\hfill\hfill{\it Figure\ 3}\hfill\cr}$$

The condition that kings in vertically adjacent cells cannot attack each other
amounts to the condition that every $\uparrow$ in a column of
figure 2 must lie over every $\downarrow$ in that column; likewise,
the condition that kings in horizontally adjacent cells cannot attack
amounts to the condition that every $\gets$ in a row in figure 3 lies
to the left of every $\to$.  Thus a vertical (resp. horizontal) diagram
is specified uniquely by the number of $\downarrow$ (resp. $\gets$)
symbols in each column (resp. row).  For a $2m\times 2n$ board, this
is a an ordered $n$-tuple $(a_1,\ldots,a_n)$
(resp. $m$-tuple $(b_1,\ldots, b_m)$) of integers in
$[0,m]$ (resp. $[0,n]$).  Obviously a configuration of kings is
uniquely specified by its two diagrams.  The question that remains is
which pairs of diagrams are compatible.  The compatibility condition is
dictated by the rule that diagonally adjacent squares 
in diagonally adjacent cells should not
contain attacking kings.
This actually amounts to two separate rules depending on whether
the adjacency is NE$\leftrightarrow$SW or NW$\leftrightarrow$SE.
The first gives rise to the rule that we cannot have
$$a_i < j < a_{i+1}\hbox{ and }b_j < i < b_{j+1}\eqno{(1)}$$
for any $i$ and $j$.
The second implies that we cannot have
$$a_i > j > a_{i+1}\hbox{ and }b_j > i > b_{j+1}.\eqno{(2)}$$
One way of visualizing the situation is to extend $j\mapsto a_j$
and $i\mapsto b_i$ to piecewise linear functions, $y = a(x)$ and
$x = b(y)$ respectively, view their graphs
as oriented curves, and ask that the curves not intersect with ``positive''
orientation.  This is not quite right because the two
diagrams are incompatible only if (1) or (2) is sharp for some $(i,j)$.
Nevertheless, this picture motivates the computations below.

\medskip\noindent{\bf Lemma 1.} For all $m$ and $n$,
$$K(m,n)\ge \lfloor n/2\rfloor^m \lfloor m/2\rfloor^n.$$
\medskip\noindent{\bf Proof.} Consider all vertical diagrams satisfying
$$a_i\in\cases{[0,m/2]&if $i \le n/2$,\cr
		[m/2,m]&if $i > n/2$,\cr}$$
and all horizontal diagrams satisfying
$$b_j\in\cases{[n/2,n]&if $j \le m/2$,\cr
		[0,n/2]&if $j > m/2$.\cr}$$
There cannot be an incompatibility among two such diagrams.
Indeed, if (1) holds for some $(i,j)$, we have
$$i\le {n\over 2}\implies b_j < {n\over 2}\implies j > {m\over 2}
\implies a_{i+1} > {m\over 2}\implies i+1 > {n\over 2}
\implies b_{j+1}\ge i+1 > {n\over 2}\implies j+1\le {m\over 2}$$
and
$$i > n/2\implies j > a_i\ge m/2\implies i < b_{j+1}\le n/2,$$
a contradiction either way.
If (2) holds for some $(i,j)$,
$$j\le m/2\implies a_i>m/2\implies i>n/2\implies j > a_{i+1}>m/2,$$
and
$$j > m/2\implies i < b_j\le n/2\implies m/2\ge a_i > j,$$
again a contradiction.
The lemma follows.\hfill\rlap{$\sqcap$}$\sqcup$\medskip

From this and the trivial upper bound $K(m,n)\le (m+1)^n(n+1)^m$
we obtain
\medskip\noindent{\bf Theorem 1.} For all positive integers $m$ and $n$,
$$\log K(m,n) = m\log n + n\log m + O(m+n).$$
\hfill\rlap{$\sqcap$}$\sqcup$\medskip
\medskip

In order to improve the error term, we need a better upper
bound for $K$.
To get it, we need to bound the size of entries of
powers of matrices.  Let $\Sigma(M)$ denote the sum of the
entries of a matrix $M$.

\medskip\noindent{\bf Theorem 2.} Let $M$ be a $k\times k$
matrix with entries in $[0,1]$.  For all $n>k$,
$$\Sigma(M^n) < 35 (15 k)^k n^k \sup(r(M)^n,1)$$
where $r(M)$ denotes the largest absolute value of an eigenvalue of $M$.
\medskip\noindent{\bf Proof.} Note first that if $M$ is nilpotent,
$\Sigma(M^n) = 0$ for all
$n\ge k$.  We are therefore justified in assuming henceforth that $r(M) > 0$.

If $v$ denotes the column vector of length $k$ with all
entries $1$, the sum of the entries of $M^n$ is
$$S_n :=\;{}^tv M^n v.$$
By the Cayley-Hamilton theorem, the sequence $S$ satisfies the linear
recurrence
$$\sum_{i=0}^k c_i S_{n+i} = 0\quad\forall n\ge 0,\eqno{(3)}$$
where $\sum_i c_i x^i$ is the characteristic polynomial of $M$.
Moreover, if $I_{p,q}$ denotes the $p\times q$ matrix with
every entry equal to $1$, then each
entry of $M^n$ is dominated by the corresponding
entry of $I_{k,k}^n$,
so $S_n\le k^{n+1}$ for all $n$.  Setting
$$P(x) = \sum_{i=0}^k c_i x^{k-i},\quad S(x) = \sum_{i=0}^\infty S_i x^i,$$
we conclude that $P(x)S(x)$ is a polynomial
$Q(x) = \sum_i q_i x^i$ of degree less than $k$.
As the absolute value of the
determinant of a $j\times j$ matrix with entries in $[0,1]$
is bounded by $j!$, we have
$$c_i\le k(k-1)\cdots(i+1)\le k^{k-i}$$
and therefore
$$q_i \le (i+1)k^{i+1}.$$

By the residue theorem,
$$S_n = \oint {Q(z)\over z^{n+1}P(z)}dz,$$
as long as the contour of integration is contained in an open disk
about the origin of radius $1/r(M)$.  We choose a
counter-clockwise circle of radius ${n\over (n+k+1)r(M)}$.
For every point $z$ on this contour,
$$|P(z)|\ge \LP k+1 \over(n+k+1)r(M)\RP^k$$
and
$$|Q(z)|\le (k^{k+1} + (k-1)k^{k-1} + (k-2)k^{k-2} + \cdots)\sup(r(M)^{1-k},1)
\le k^{k+2}\sup(r(M)^{1-k},1).$$
Therefore, the integral is bounded above by
$$2\pi r(M)^{-1} k^{k+2}\sup(r(M)^{1-k},1) r(M)^k (n+k+1)^k (k+1)^{-k}
r(M)^{n+1} (n+k+1)^{n+1} n^{-n-1}$$
and thus by
$$2\pi k^2\sup(r(M)^{n+k},1)(n+k+1)^k{n+k+1\over n}e^{k+1}.$$
As $n\ge k+1$, $\sup(r(M))\le k$, $e^k\ge k^e > k^2$, $4\pi e < 35$,
and $2 e^2 < 15$,
we obtain the desired upper bound of
\medskip
\line{\hfill $4\pi e k^2 (2ek)^k n^k \sup(r(M)^n,1) < 35 (15 k)^k n^k \sup(r(M)^n,1).
\hfill\rlap{$\sqcap$}\sqcup$}
\bigskip

Fix $k\ge 3$ and assume that $m' = m/k$ and $n' = n/k$ are integers.
We divide
each diagram, horizontal and vertical, into a
$k\times k$ array of $m'\times n'$ {\it blocks},
indexed by ordered pairs $(p,q)$,
$1\le p,q\le k$, and consisting of the cells with integral
coordinates in the rectangle
$[(p-1)n'+1,pn']\times[(q-1)m'+1,qm']$.
We say that the $(p,q)$ block is of type $\uparrow$
if there exists $i\in [(p-1)n'+1, pn'-2]$
such that
$a_i\le (q-1)m' <  qm'\le a_{i+1}$.  In effect, the graph
of $i\mapsto a_i$ cuts entirely through the block from below.
We define blocks of type $\downarrow$, $\gets$, and $\to$
analogously.  For example, the figure below shows a vertical diagram,
its $a$-function, and its $\uparrow$ and $\downarrow$ blocks:
$$\displaylines{\hfill\epsfbox{fig4.eps}\hfill\cr
\hfill\hfill{\it Figure\ 4}\hfill\cr}$$

Thanks to condition (1), a block cannot be both of type $\uparrow$
and of type $\to$, and thanks to condition (2), it cannot
be both of type $\downarrow$ and of type $\gets$.
It turns out that we need to use only the first of these conditions.

We consider the single column $X^p$ of blocks of the form
$\{(p,i)\mid 1\le i\le k\}$.
Given a subset $U = U^p$ of
$X^p$, we consider the number of sequences $a_j$, $j\in[(p-1)n'+1,pn'-2]$,
for which the
set of blocks of type $\uparrow$ is contained in $U$.
Such sequences are characterized by the rule
$$a_j\le (i-1)m' <  im'\le a_{j+1}
\Rightarrow\ (p,i)\in U.\eqno{(4)}$$

The number of such sequences is
$\Sigma(M_U^{n'-2})$, where $M_U$ is the incidence matrix defined
by condition (4).
More precisely, $M_U$ is a $\{0,1\}$-matrix
whose $(u+1,v+1)$ entry is $1$ if and only if
$$v\le (i-1)m' < im'\le u
\Rightarrow\ (p,i)\in U,\quad 0\le u,v\le m$$
We extend the $m+1\times m+1$ matrix $M_U$ to a $(k+1)m'\times (k+1)m'$
matrix $\tilde M_U$ by adding $m'-1$ zero-rows and $m'-1$ zero-columns,
on the top and left respectively.  For example, if $m' = 2$, $k = 3$,
and $U$ is empty, we obtain
$$\tilde M_U = \LP\matrix{
0&0&0&0&0&0&0&0\cr
0&1&1&1&1&1&1&1\cr
0&1&1&1&1&1&1&1\cr
0&0&1&1&1&1&1&1\cr
0&0&1&1&1&1&1&1\cr
0&0&0&0&1&1&1&1\cr
0&0&0&0&1&1&1&1\cr
0&0&0&0&0&0&1&1\cr
}\RP.\eqno{(5)}$$

Let $N_U$ denote the $(k+1)m'\times (k+1)m'$ $\{0,1\}$-matrix
whose $(u,v)$ entry is $1$ if and only if
$$\lfloor v/m'\rfloor\le i-1 < i+1\le \lfloor u/m'\rfloor
\Rightarrow\ (p,i)\in U,\quad 0\le u,v\le m+m'-1.$$
For example, under the same conditions as (5), we obtain
$$N_U = \LP\matrix{
1&1&1&1&1&1&1&1\cr
1&1&1&1&1&1&1&1\cr
1&1&1&1&1&1&1&1\cr
1&1&1&1&1&1&1&1\cr
0&0&1&1&1&1&1&1\cr
0&0&1&1&1&1&1&1\cr
0&0&0&0&1&1&1&1\cr
0&0&0&0&1&1&1&1\cr
}\RP.$$

As $i+1\le \lfloor u/m'\rfloor$ implies $im'\le u - (m'-1)$,
each term in $N_U$ is at least as great as the corresponding
term in $\tilde M_U$, and
$$\Sigma(N_U^{n'-2})\ge \Sigma(\tilde M_U^{n'-2})\ge\Sigma(M_U^{n'-2})
\eqno{(6)}$$
On the other hand,
$$N_U = I_{m',m'}\otimes P_U,$$
where $P_U$ is the $\{0,1\}$-matrix with $(u+1,v+1)$ entry $1$ if and only
if
$$v\le i-1 < i+1\le u\Rightarrow\ (p,i)\in U.$$
Thus
$$\Sigma(N_U^{n'-2}) = \Sigma(I_{m',m'}^{n'-2})\Sigma(P_U^{n'-2})
= (m')^{n'-1}\Sigma(P_U^{n'-2}).\eqno{(7)}$$
By Theorem 2,
$$\Sigma(P_U^{n'-2}) < 35(15k)^k (n')^k r(P_U)^{n'},\eqno{(8)}$$
so we would like to estimate $r(P_U)$.

Consider the equivalence relation on $\{1,2,\ldots,k+1\}$ 
generated by the relation $i\sim i+1$ if $(p,i)\in U$.
Let $c_i$ be the cardinality of the $i^{\rm th}$ equivalence class,
where the equivalence classes are arranged by the increasing size of their
elements.
Thus
$$P_U = \LP\matrix{I_{c_1,c_1}&I_{c_1,c_2}&I_{c_1,c_3}&\cdots&I_{c_1,c_r}\cr
R_{c_2,c_1}&I_{c_2,c_2}&I_{c_2,c_3}&\cdots&I_{c_2,c_r}\cr
0&R_{c_2,c_3}&I_{c_3,c_3}&\cdots&I_{c_3,c_r}\cr
\vdots&\vdots&\vdots&\ddots&\vdots\cr
0&0&0&\cdots&I_{c_r,c_r}\cr}\RP,$$
where
$R_{p,q}$ is the $p\times q$ matrix whose first row consists of
entries $1$ but whose other entries are zero.  Letting $Q_\ell$ denote
the $\ell\times\ell$ matrix whose $(j,k)$ entry is
$$e^{2\pi i (j-1)(k-1)\over \ell},$$
and conjugating by
$$\LP\matrix{Q_{c_1}&0&\cdots&0\cr
0&Q_{c_2}&\cdots&0\cr
\vdots&\vdots&\ddots&\vdots\cr
0&0&\cdots&Q_{c_r}\cr}\RP,$$
we obtain
$$P'_U = \LP\matrix{c_1E_{c_1,c_1}&
\sqrt{c_1 c_2}E_{c_1,c_2}&\sqrt{c_1 c_3}E_{c_1,c_3}&\cdots&
\sqrt{c_1 c_r}E_{c_1,c_r}\cr
\sqrt{c_1/c_2}C_{c_2,c_1}&c_2 E_{c_2,c_2}&\sqrt{c_2c_3}E_{c_2,c_3}&
\cdots&\sqrt{c_2c_r}E_{c_2,c_r}\cr
0&\sqrt{c_2/c_3}C_{c_2,c_3}&c_3 E_{c_3,c_3}&\cdots&\sqrt{c_3c_r}E_{c_3,c_r}\cr
\vdots&\vdots&\vdots&\ddots&\vdots\cr
0&0&0&\cdots&c_r E_{c_r,c_r}\cr}\RP,$$
where $E_{i,j}$ denotes the $i\times j$ matrix with zero entries
except for a one in the upper left corner, and $C_{i,j}$
denotes the $i\times j$ matrix with zero entries except for
ones in the first column.  It follows that the non-zero
eigenvalues of $P_U$ coincide with the non-zero eigenvalues of
$$\LP\matrix{c_1&\sqrt{c_1c_2}&\sqrt{c_1c_3}&\cdots&\sqrt{c_1c_r}\cr
\sqrt{c_1/c_2}&c_2&\sqrt{c_2c_3}&\cdots&\sqrt{c_2c_r}\cr
0&\sqrt{c_2/c_3}&c_3&\cdots&\sqrt{c_3c_r}\cr
\vdots&\vdots&\vdots&\ddots&\vdots\cr
0&0&0&\cdots&c_r\cr}\RP.$$
The characteristic polynomial of this matrix is
$$\displaylines{\quad\biggl\{ 1 - \LP{c_1\over (c_1-\lambda)(c_2-\lambda)} + {c_2\over (c_2-\lambda)(c_3-\lambda)} + \cdots +
{c_{r-1}\over (c_{r-1}-\lambda)(c_r-\lambda)}\RP\hfill\cr
\hfill + \LP{c_1\over (c_1-\lambda)(c_2-\lambda)(c_3-\lambda)} + 
\cdots + {c_{r-2}\over (c_{r-2}-\lambda)(c_{r-1}-\lambda)(c_r-\lambda)}\RP
- \cdots\biggr\}\prod_{i=1}^r (c_i-\lambda).\quad\cr}$$

As $\sum_i c_i = k+1$,
$$r(P_U) \le 2\sqrt{k+1} + \sup_i c_i.$$
On the other hand,
$$(\sup_i c_i) - 1\le \sum_i (c_i - 1)
= |U|+1.$$
We deduce that
$$r(P_U) \le 2\sqrt{k+1}
+ 1 + |U|.$$
Combining this with $r\le k+1$, and the inequalities (6), (7), and (8),
we conclude that
$$\Sigma(M_{U^p}^{n'-2})\le 35(m')^{n'}(15n'(k+1))^{k+1}
\bigl(|U^p|+1+2\sqrt{k+1}\bigr)^{n'}.$$

We fix an array of subsets $\vec U = (U^1,\ldots,U^k)$, $U^i\subset X^i$,
with a total of
$$h = |U^1| + \cdots + |U^p|$$
blocks.
The
total number of vertical diagrams whose
blocks of type $\uparrow$ all lie in $U^1\cup\cdots\cup U^k$,
is
$$\displaylines{\qquad\prod_{p=1}^k 35(m')^{n'}(15n'(k+1))^{k+1} \bigl(|U^p|+1+2\sqrt{k+1}\bigr)^{n'}(m+1)\hfill\cr
\hfill\le 35^k(m')^n (15n'(k+1))^{k^2+k}\LP{h+k+2\sqrt2 k\sqrt{k}\over k}
(m+1)^k\RP^n
\qquad\cr\hfill
=(35m+35)^k m^n (15n'(k+1))^{k^2+k}
(hk^{-2}+k^{-1}+2\sqrt2k^{-1/2})^n.\qquad\cr}$$
Likewise, fixing an array $\vec L = (L^1,\ldots,L^k)$, each $L^i$ a 
subset of the $i^{\rm th}$ row of blocks, the number of horizontal
diagrams whose blocks of type $\to$ are contained in $L^1\cup\cdots\cup L^k$
is bounded by
$$(35n+35)^k n^m(15m'(k+1))^{k^2+k}(h'k^{-2}+k^{-1}+2\sqrt2k^{-1/2})^n.$$
As there are only $2^{k^2}$ ways of choosing $\vec U$ and $2^{k^2}$
ways of choosing $\vec L$,
the number of pairs of compatible diagrams is less than
$$(35m+35)^k(35n+35)^k m^n n^m (900m'n'(k+1)^2)^{k^2 + k}S,$$
where
$$S = \sup_{0\le h\le k^2}((2\sqrt2k^{-1/2}+k^{-1}) + hk^{-2})^n
((2\sqrt2k^{-1/2}+k^{-1}) + (1-hk^{-2}))^m.$$

If $n$ is a perfect $5^{\rm th}$ power, we set
$k = n^{2/5}$,
and obtain
$$\eqalign{\log K(m,n)&\le n^{2/5}(\log(35m+35)+\log(35n+35))
+ m\log n + n\log m\cr
&+ n^{4/5} \log (1800mn) + n^{2/5}\log(1800mn) + \log S.\cr}$$

When $m=n$, by the arithmetic-geometric mean inequality,
$$\eqalign{\log K(n,n) &\le 2n^{2/5}\log(35n+35) + 2n\log n
+ n^{4/5}\log (1800n^2)\cr
&\qquad+ n^{2/5}\log (1800n^2)
+ 2n\log(1/2 + 2\sqrt 2 k^{-1/2} + 2k^{-1})
\cr
&= 2n\log n - 2n\log 2 + (4\sqrt2+2)n^{4/5} \log (n) + O(n^{4/5}).\cr}$$
This result applies even when $n$ is not a perfect $5^{\rm th}$
power.  Indeed, $K(m,n)$ is monotonically increasing in each variable,
so setting $N = \lceil n^{1\over 5}\rceil^n$,
$$\eqalign{K(n,n)\le K(N,N) &\le 2N\log N - 2N\log 2 + O(N^{4/5}\log N)\cr
&= 2n\log n - 2n\log 2 + O(n^{4/5}\log n).\cr}$$

Combining this upper bound with Lemma 1, we deduce

\medskip\noindent{\bf Theorem 3.} For all positive integers $n$,
$$\log K(n,n) = 2n\log n - 2n\log 2 + O(n^{4/5}\log n).$$
\hfill\rlap{$\sqcap$}$\sqcup$\bigskip
\goodbreak
\centerline{REFERENCES}
\medskip
\item{[1]} R. Baxter, {\it Exactly Solved Models in Statistical Mechanics},
	Academic Press, London, 1982.
\item{[2]} N. Elkies, G. Kuperberg, M. Larsen, J. Propp,
	Domino tilings of Aztec diamonds I, II {\it J. of Algebraic Comb.}
	{\bf 1} (1992) 111--132, 219--234.
\item{[3]} N. Elkies, R. Stanley, Mathematical Chess, in preparation.
\item{[4]} I. Rivin, I. Vardi, P. Zimmermann, The $n$-queens problem,
	{\it American Mathematical Monthly} (1994) 629--638.
\item{[5]} H. Wilf, The problem of the kings, {\it Electronic Journal
of Combinatorics} {\bf 2} (1995) R3.
%http://ejc.math.gatech.edu:8080/Journal/Volume_2/volume2.html
\bigskip
%\line{\hskip 4truein Michael Larsen\hss}
%\line{\hskip 4truein University of Pennsylvania\hss}
%\line{\hskip 4truein Philadelphia, PA 19104\hss}
%\line{\hskip 4truein \tt larsen@math.upenn.edu\hss}
%\line{\hskip 4truein Submitted: May 30, 1994\hss}


\end