\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_m<m+1$ such that
$$f_m(n)= (c_mn+d_m)(m+1)^n+O(\theta_m^n)\qquad (n\to\infty).$$


\vskip 10pt

For every such placement of kings, the chessboard is naturally divided
into $mn$ $2\times 2$ cells, each containing exactly one king. Let's
say that a cell is of type 1 (resp.  2, 3, 4) if the king sits in its
NW (resp. NE, SE, SW) corner. The arrangement of kings is then
completely specified by an $m\times n$ matrix whose entries are $\in
\{1,2,3,4\}$. For example, the array 
$$\matrix{1&4&1&1&2\cr
3&3&2&2&3\cr 4&4&4&3&3\cr}\eqno(1)$$ 
corresponds to a legal arrangement of
kings on a $6\times 10$ board, namely the following one.
\vskip 15pt

$\qquad\qquad\qquad\qquad\qquad$\vbox{{\parskip -.9pt

\hbox{$\squarek\square\square\square\squarek\square
\squarek\square\square\squarek$}
\vskip-1pt
\hbox{$\square\square\squarek\square\square\square
\square\square\square\square$}
\vskip-1pt
\hbox{$\square\square\square\square\square\squarek
\square\squarek\square\square$}
\vskip-1.5pt
\hbox{$\square\squarek\square\squarek\square\square
\square\square\square\squarek$}
\vskip-1pt
\hbox{$\square\square\square\square\square\square\square
\square\square\square$}
\vskip-1.6pt
\hbox{$\squarek\square\squarek\square\squarek\square\square
\squarek\square\squarek$}

}}

\vskip15pt

Conversely, a matrix such as (1) represents an allowable configuration of kings iff it satisfies certain adjacency conditions, namely that none of the following two letter words is permitted:
$$21,\ \quad 24,\ \quad  31,\ \quad  34,\ \quad  \ \matrix{3\cr 1\cr},\quad  \ \matrix{3\cr 2\cr},\ \quad  \matrix{4\cr 1\cr},\ \quad  \matrix{4\cr 2\cr},\ \quad  \matrix{3&\cr &1\cr},\ \quad \matrix{&4\cr 2&\cr}\eqno(2)$$

Think of the columns of the array (1) as wooden playing pieces, like
dominoes. If we scan one of the pieces from top to bottom we see a
block of 0 or more 1's and 2's followed by a block of 3's and 4's.
Hence the number of pieces is altogether $N=N(m)=(m+1)2^m$. Thus there
are 12 possible pieces that might be used to make a $2\times n$ array,
namely the pieces
$$\pce44\pce14\pce11\pce34\pce43\pce24\pce13\pce12\pce21
\pce22\pce23\pce33
.$$

Now fix an integer $m\ge 1$, and one of the $N(m)$ wooden pieces of
height $m$, say the piece $u$ ($1\le u\le N(m)$). Let $f_m(n,u)$ be
the number of legal $m\times n$ arrays whose last (i.e., $n$th) column
is the given piece $u$, and let $f_m(n)=\sum_uf_m(n,u)$. Then clearly
$$f_m(n+1,u)=\sum_vf_m(n,v)\lambda (v\rightarrow u),\qquad (n\ge
1;f_m(1,u)=1\ (1\le u\le N(m))) $$ in which $\lambda$ is the truth
value of the proposition that it is legal for the piece $v$ to be
immediately followed by the piece $u$. Thus $f_m(n,\cdot )$ is the
column vector of row sums of the matrix $\Lambda_m^{n-1}$, where 
$$\Lambda_m=\{\lambda (v\rightarrow u)\}_{1\le u,v\le N(m)}$$
is the {\it transfer matrix} of the problem. 

Finally, if
we don't care which piece is the last column, we see that {\it the
total number of $m\times n$ arrangements is the sum of all of the
entries of the $N(m)\times N(m)$ matrix $\Lambda_m^{n-1}$}.
 Hence {\it the generating function for the numbers of $m$-rowed
arrays, by their number of columns, is the sum of all of the entries
of the matrix $x(I-x\Lambda_m)^{-1}$}.

When $m=2$ this generating function turns out to be
$${{12x-29x^2+33x^3-9x^4}\over {(1-3x+x^2) (1-6x+9x^2)}}.\eqno(3)$$ The
eigenvalues of the transfer matrix in this case are 3 (twice), $(3\pm\sqrt{5})/2$
(each twice), and 0 (six times). The question is, in general what is the largest eigenvalue of the $N(m)\times
N(m)$ transfer matrix?
\proclaim Lemma 1. The transfer matrix $\Lambda_m$ has the eigenvalue $m+1$, and corresponding to it, a nonnegative eigenvector.

\noindent{\bf Proof.} Suppose we label the rows and columns of the matrix by the pieces. Consider the vector $\by$, of length $(m+1)2^m$, whose
entries are 0's except for the entries in positions that correspond
to pieces all of whose letters are 1's and 4's. In those positions
let the entries of $\by$ be 1's.

Then $\by$ is an eigenvector of the transfer matrix $\Lambda_m$, with
eigenvalue $m+1$. For, if $u$ is some piece, then
$$(\Lambda_m\by)_u=\sum_v\lambda (u\rightarrow v)\by_v$$ is equal to the number of 1-4 pieces $v$
that can legally follow $u$.  If $u$ is itself a 1-4 piece then it can be followed by any 1-4 piece, or $(m+1)$ of them. If $u$ contains a 2 or a 3 then it cannot be followed by any 1-4 piece. Hence $A\by =(m+1)\by$. \vrl

It remains to show that this eigenvalue $m+1$ is the {\it largest}
eigenvalue of $\Lambda_m$, that it has multiplicity two, and to look at its contribution to the growth of $f(n,m)$. 

We will show next that there is an ordering of the pieces in
which the matrix $\Lambda_m$ is {\it block triangular}. More precisely, the $(m+1)2^m\times (m+1)2^m$ matrix $\Lambda_m$, when
written as a $2^m\times 2^m$ matrix whose ``entries'' are $(m+1)\times
(m+1)$ blocks, will be a triangular matrix. From that it will follow
that the multiset of eigenvalues of $\Lambda_m$ is exactly the
multiset union of the spectra of its diagonal blocks. We will describe the latter in Lemma 4 below.

Intuitively speaking, this ordering expresses the following fact. If at a certain point in the chessboard there is a king that lives in the right hand one of the two columns of its $2\times 2$ cell, then everywhere to the right of that cell, in the same row of the board, all of the kings live in the right hand columns of their respective cells. Hence, pieces that have more 2's and 3's in them represent later ``life forms'' in that they cannot be followed by pieces with fewer 2's and 3's.


We now describe the ordering of the pieces. Each piece is an
$m$-letter word on an alphabet of $\{1,2,3,4\}$. We define an
equivalence relation on the pieces. For a given piece, replace every
occurrence of a 1 or a 4 in the piece by an ``L'', and replace every 2
or 3 by an ``R''. Say that two pieces are equivalent if the resulting
LR-sequences are identical.

\proclaim Lemma 2. The $(m+1)2^m$ pieces are partitioned, under
 this equivalence relation, into $2^m$ classes, each of size $m+1$.

\noindent{\bf Proof.} Consider the class that is defined by some fixed word $w$ of $m$ letters, each either an R or an L. In every piece, a 3 or 4 can never be just above a 1 or 2. Hence every piece consists of exactly $j$ 1's and 2's followed by exactly $m-j$ 3's and 4's. We claim that for a fixed $j$, exactly one such piece belongs to the class of the word $w$.

Indeed, as we scan each letter L or R in $w$, we can choose, a priori,
either a 1 or 4, for every L, and a 2 or 3, for every R, in order to
construct a piece in the class. However, in the spaces above position
$j$, we can choose only 1's or 2's. Hence every R in $w$ is forced to
be represented by a 2, and every L in $w$ must be represented by a 1,
as long as we are reading positions above the $j$th. Below the $j$th
position in the piece we are forced to choose a 3 every time we see an
R, and a 4, each time we find an L in the word $w$. Hence for the
fixed $j$, there is one and only one piece that has the given pattern
$w$. Since there are $m+1$ possible values of $j=0,1,\ldots ,m$, we are finished. \vrl

Now here is the ordering of the pieces.

Consider the set of all $2^m$ $m$-letter words $w$ of R's and L's.
Think of L as a ``smaller'' letter than R. For each fixed
$j=0,1,\ldots ,m$, the set of all words $w$ that contain exactly $j$
R's is ordered lexicographically. Then we make a grand list by first
writing down the list of all words that contain 0 R's, then all words
that have exactly one R, then all that have exactly two R's, etc.,
finishing with the words that consist entirely of R's. Finally, in
this grand list of patterns $w$, replace each pattern by the $m+1$
words over $\{1,2,3,4\}$ that lie in its equivalence class, these
being arranged in any order among themselves.  The collection of all
pieces has now been ordered.

\proclaim Lemma 3. Let $\Lambda_m$ be the transfer matrix, with its rows and columns labeled by pieces that have been ordered as we have just described. Then $\Lambda_m$ is block (upper) triangular. Furthermore, among the diagonal blocks of $\Lambda_m$ there are two $(m+1)\times (m+1)$ matrices whose entries are all 1's, and all other blocks have at least one ``0'' entry.

\noindent{\bf Proof.} We show first that if pattern $w$ (strictly)
 precedes pattern $w'$, and if $u$, $v$ are words that have the
patterns $w$, $w'$ respectively, then the piece $v$ cannot be followed
(on the right) immediately by the piece $u$, in the construction of a
chessboard.

First suppose that $w$ and $w'$ contain the same number of R's. Then
in some position we must have an L in $w$ and an R in $w'$. Then $u$
cannot follow $v$, because if it did, then in that position we would
find a letter 2 or 3 followed by a 1 or 4, which is a forbidden
succession. If $w$ and $w'$ have different numbers of $R$'s then $w'$ has more R's
than $w$, and the same argument as above shows again that $u$ cannot
follow $v$. Hence the full matrix is block-triangular.

Among the diagonal blocks, the first and the last are each matrices of
all 1's. For in the class of pieces whose pattern is LL$\ldots $L, any
piece can follow any other, and likewise for the pattern $RR\ldots R$.

We claim that in each of the other diagonal blocks there is at least
one zero entry. Indeed, a block on the diagonal corresponds to
transitions between two pieces each of which have the same LR word.
We assert that, given an LR word $w$ that does not consist entirely
 of
L's or entirely of R's, there exist two pieces $u,v$ that belong to
the class $w$ and are such that a transition from $u$ to $v$ cannot
occur, which will establish our claim. For in the word $w$ one of the
strings LR or RL must occur. Suppose $w$ contains LR. The set of
 $m+1$
pieces in the class of $w$ are parameterized by the number $j$ of 1's
and 2's that are in the maximal contiguous block of 1's and 2's with
which the piece begins. Consider the piece $v$ where the interface
 $j$
occurs just above the LR in $w$, and the piece $u$ where that
interface occurs just below the string LR. In the piece $v$ these two
positions must contain 43, whereas in $u$ there must be a 12. If $v$
were to follow $u$, the forbidden sequence that appears last in the
list (2) above would occur in the board, which is a contradiction.
Similarly, if $w$ contains an RL substring, then the forbidden
sequence that appears next-to-last in the list (2) above would occur,
which completes the proof of the claim, and of the lemma.  \vrl


For our next result we will use the following lemma about matrices
with nonnegative entries, which is due to Wielandt [2], see also
Gantmacher [1]. We state somewhat less than Wielandt actually proved,
but this form will suffice for our purposes.

\proclaim Lemma. (H. Wielandt). If $A$ and $C$ are two $n$-square matrices, and $A$ has positive entries, suppose that $|c_{i,j}|\le a_{i,j}$ for all $1\le i,j\le n$. If $\gamma$ is any eigenvalue of $C$, and $r$ is the largest eigenvalue of $A$, then $|\gamma|\le r$. Furthermore, the sign of equality can hold if and only if $C=e^{i\phi}DAD^{-1}$ where $e^{i\phi}=\gamma/r$, and $D$ is a diagonal matrix whose entries are of modulus 1.

Now we can prove that $m+1$ is the largest eigenvalue of the transfer
matrix.

\proclaim Lemma 4. Not only
does the matrix $\Lambda_m$ have $m+1$ for an eigenvalue, but this is
its {\it largest} eigenvalue, and it has multiplicity two.

\noindent{\bf Proof.} The eigenvalues of $\Lambda_m$ are the multiset union of the
multisets of eigenvalues of its diagonal blocks, if its lines are
labeled as described in lemma 3. Exactly two of the diagonal blocks
are $(m+1)\times (m+1)$ matrices all of whose entries are 1's. 

Now, in Wielandt's lemma above, take $A$ to be the $(m+1)$-square
matrix of 1's and take $C$ to be one of the diagonal blocks of
$\Lambda_m$ other than the first or last block. Certainly the
hypotheses of the lemma hold, so no eigenvalue of $C$ can exceed $m+1$
in modulus. But more interestingly, suppose that the sign of equality
holds. Then by the lemma, the modulus of each entry of $C$ must equal
that of the corresponding entry of $A$, i.e., must be equal to 1,
which contradicts the fact that $C$ has at least one zero entry. \vrl

If, e.g., $m=3$, there are 32 pieces, and when they are
arranged in the order specified above, they are the successive
 columns of the following array.
$$\vbox{
\hbox{4\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 4\sp2 1\spp 1\spp 1\spp 4\sp2 3\spp 2\spp 2\spp 2\sp2 1\spp 1\spp 1\spp 4\sp2 3\spp 2\spp 2\spp 2\sp2 3\spp 2\spp 2\spp 2\sp2 3\spp 2\spp 2\spp 2}

\hbox{4\spp 4\spp 1\spp 1\sp2 1\spp 1\spp 4\spp 4\sp2 2\spp 3\spp 2\spp 3\sp2 4\spp 4\spp 1\spp 1\sp2 3\spp 2\spp 2\spp 3\sp2 4\spp 4\spp 1\spp 1\sp2 3\spp 2\spp 3\spp 2\sp2 3\spp 3\spp 2\spp 2}

\hbox{4\spp 4\spp 4\spp 1\sp2 2\spp 3\spp 3\spp 3\sp2 1\spp 4\spp 4\spp 4\sp2 4\spp 4\spp 1\spp 4\sp2 3\spp 3\spp 2\spp 3\sp2 3\spp 3\spp 3\spp 2\sp2 4\spp 4\spp 4\spp 1\sp2 3\spp 3\spp 3\spp 2}}$$
Observe that the first $m+1=4$ pieces have no R's, the next 12 pieces each have one R, etc. With this labelling of its rows and columns, the $32\times 32$
transfer matrix is 

$$\vbox{\vskip\vsp\hbox{1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1}
 
\vskip\vsp\hbox{1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 
1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 
1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 
1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 
1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 
1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 
1\spp 1\spp 1\spp 1}

\vskip\vsp\hbox{1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 
1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 1\spp 1\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1\sp2 1\spp 1\spp 1\spp 1} 

\vv

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1} 

\vskip\vsp\hbox{0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 
0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 0\spp 0\spp 0\spp 0\sp2 1\spp 1\spp 1\spp 1}}$$ 

\noindent and its block-triangularity is evident.  




Hence the transfer matrix has $m+1$ as an eigenvalue of multiplicity
two, and all of its other eigenvalues are of moduli smaller than
$m+1$. The generating function $\sum_nf_m(n)x^n$ is therefore the sum
of all of the entries of the matrix
$$x(I-x\Lambda_m)^{-1}={{x\, {\rm cof}(I-x\Lambda_m)}\over
{\det{(I-x\Lambda_m)}}} ={{x\, {\rm cof}(I-x\Lambda_m)}\over
{\prod_{i=1}^N(1-\lambda_i x)}},$$
in which cof is
the $N\times N$ matrix of cofactors of $I-x\Lambda_m$ and the $\{\lambda_i\}$ are the eigenvalues of $\Lambda_m$.
But each entry of this matrix has a partial fraction expansion of the form
$${{\alpha}\over
{(1-x(m+1))^2}}+{{\beta}\over {1-x(m+1)}}+R(x),$$ where  the partial
fraction expansion of $R(x)$ involves only eigenvalues whose moduli
 are smaller than $m+1$. Hence the sum of all of the entries of the matrix has a partial fraction expansion of the same form, and so for each fixed $m$ there are numbers $c_m$ and $d_m$ for which $f_m(n)=(c_mn+d_m)(m+1)^n+O(\theta_m^n)$, where $\theta_m<m+1$. 

It remains to show that $c_m>0$.

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