The Problem of the Kings

Herbert S. Wilf^{∗} University of Pennsylvania Philadelphia, PA 19104-6395

Submitted: June 21, 1994; Accepted: December 9, 1994

On a 2m × 2n chessboard, the maximum number of nonattacking kings that can be placed is mn, since each 2×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 × 2n chessboard. The purpose of this paper is to prove the following result.

Theorem. For each m = 1, 2, 3, … there are constants c_{m} > 0, d_{m}, and 0 ≤ θ_{m} < m + 1 such that

f_{m}(n) = (c_{m}n + d_{m})(m + 1)^{n} + O(θ_{m}^{n}) (n → ∞).

For every such placement of kings, the chessboard is naturally divided into mn 2 × 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 × n matrix whose entries are ∈ {1, 2, 3, 4}. For example, the array

1 4 1 1 2 3 3 2 2 3 4 4 4 3 3  (1)

corresponds to a legal arrangement of kings on a 6 × 10 board, namely the following one.

K  K  K  K

K

K  K
K  K  K
K  K  K  K  K

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, 24, 31, 34, {3 \atop 1} , {3 \atop 2} , {4 \atop 1} , {4 \atop 2} , {3 \atop 1} , {4 \atop 2}  (2)

∗ Supported in part by the Office of Naval Research

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 × n array, namely the pieces

{4 \atop 4} {1 \atop 4} {1 \atop 1} {3 \atop 4} {4 \atop 3} {2 \atop 4} {1 \atop 3} {1 \atop 2} {2 \atop 1} {2 \atop 2} {2 \atop 3} {3 \atop 3} .

Now fix an integer m ≥ 1, and one of the N(m) wooden pieces of height m, say the piece u (1 ≤ u ≤ N(m)). Let f_{m}(n, u) be the number of legal m × n arrays whose last (i.e., nth) column is the given piece u, and let f_{m}(n) = ∑_{u} f_{m}(n, u). Then clearly

f_{m}(n + 1, u) = ∑_{v} f_{m}(n, v)λ(v → u), (n ≥ 1; f_{m}(1, u) = 1 (1 ≤ u ≤ N(m)))

in which λ 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, ·) is the column vector of row sums of the matrix Λ_{m}^{n−1}, where

Λ_{m} = {λ(v → u)}_{1≤u,v≤N(m)}

is the transfer matrix of the problem.

Finally, if we don’t care which piece is the last column, we see that the total number of m × n arrangements is the sum of all of the entries of the N(m) × N(m) matrix Λ_{m}^{n−1}. Hence 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Λ_{m})^{−1}.

When m = 2 this generating function turns out to be

\frac{12x − 29x^{2} + 33x^{3} − 9x^{4}}{(1 − 3x + x^{2})(1 − 6x + 9x^{2})}.  (3)

The eigenvalues of the transfer matrix in this case are 3 (twice), (3±\sqrt{5})/2 (each twice), and 0 (six times). The question is, in general what is the largest eigenvalue of the N(m)×N(m) transfer matrix?

Lemma 1. The transfer matrix Λ_{m} has the eigenvalue m + 1, and corresponding to it, a nonnegative eigenvector.

Proof. Suppose we label the rows and columns of the matrix by the pieces. Consider the vector y, 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 y be 1’s.

Then y is an eigenvector of the transfer matrix Λ_{m}, with eigenvalue m + 1. For, if u is some piece, then

(Λ_{m}y)_{u} = ∑_{v} λ(u → v)y_{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 Ay = (m + 1)y.

It remains to show that this eigenvalue m + 1 is the largest eigenvalue of Λ_{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 Λ_{m} is block triangular. More precisely, the (m + 1)2^{m} × (m + 1)2^{m} matrix Λ_{m}, when written as a 2^{m} × 2^{m} matrix whose “entries” are (m + 1) × (m + 1) blocks, will be a triangular matrix. From that it will follow that the multiset of eigenvalues of Λ_{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 × 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.

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

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 jth. Below the jth 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, …, m, we are finished.

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, …, 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.

Lemma 3. Let Λ_{m} be the transfer matrix, with its rows and columns labeled by pieces that have been ordered as we have just described. Then Λ_{m} is block (upper) triangular.

Furthermore, among the diagonal blocks of Λ_{m} there are two (m + 1) × (m + 1) matrices whose entries are all 1’s, and all other blocks have at least one “0” entry.

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…L, any piece can follow any other, and likewise for the pattern RR … 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.

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.

Lemma. (H. Wielandt). If A and C are two n-square matrices, and A has positive entries, suppose that |c_{i,j}| ≤ a_{i,j} for all 1 ≤ i, j ≤ n. If γ is any eigenvalue of C, and r is the largest eigenvalue of A, then |γ| ≤ r. Furthermore, the sign of equality can hold if and only if C = e^{iϕ}DAD^{−1} where e^{iϕ} = γ/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.

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

Proof. The eigenvalues of Λ_{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) × (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 Λ_{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.

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.

4 1 1 1 1 1 1 4 1 1 1 4 3 2 2 2 1 1 1 4 3 2 2 2 3 2 2 2 3 2 2 2 4 4 1 1 1 1 4 4 2 3 2 3 4 4 1 1 3 2 2 3 4 4 1 1 3 2 3 2 3 3 2 2 4 4 4 1 2 3 3 3 1 4 4 4 4 4 1 4 3 3 2 3 3 3 3 2 4 4 4 1 3 3 3 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 × 32 transfer matrix is

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

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 ∑_{n} f_{m}(n)x^{n} is therefore the sum of all of the entries of the matrix

x(I − xΛ_{m})^{−1} = \frac{x cof(I − xΛ_{m})}{det (I − xΛ_{m})} = \frac{x cof(I − xΛ_{m})}{∏_{i=1}^{N}(1 − λ_{i}x)},

in which cof is the N × N matrix of cofactors of I − xΛ_{m} and the {λ_{i}} are the eigenvalues of Λ_{m}. But each entry of this matrix has a partial fraction expansion of the form

\frac{α}{(1 − x(m + 1))^{2}} + \frac{β}{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_{m}n + d_{m})(m + 1)^{n} + O(θ_{m}^{n}), where θ_{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 ≤ j ≤ 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) ≥ (n + 1)(m + 1)^{n}. Hence c_{m} > 0 and the theorem is proved.

The block triangularity of the transfer matrix Λ greatly facilitates the computation of the generating matrix x(I − xΛ)^{−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Λ)z = e, where e is the vector of all 1’s. Then z ·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) × (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 · 3^{n} + O(2.618..^{n}).

When m = 3 the generating function is

\frac{8 x (−4 + 25 x − 73 x^{2} + 163 x^{3} − 203 x^{4} + 116 x^{5} − 24 x^{6})}{(−1 + 3 x) (−1 + 4 x)^{2} (1 − 4 x + 2 x^{2})^{2}},

from which we find

f_{3}(n) = 231 n 4^{n} − 2377 · 4^{n} − 384 · 3^{n} + O(1.707..^{n}).

We have also computed that f_{4}(n) ∼ (7963567/2610)n5^{n}.

In general, the number θ_{m} that appears in our Theorem can be taken to be |λ_{m}| + ϵ, where λ_{m} is the second-largest eigenvalue of the transfer matrix, and ϵ > 0 is arbitrary. We can obtain some information about λ_{m} by noting that it cannot exceed the largest eigenvalue of an (m + 1) × (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

\frac{m + 1}{2}\{1 + \sqrt{1 − \frac{4}{(m + 1)^{2}}} \} = m + 1 − \frac{1}{m} + \frac{1}{m^{2}} − · · · .

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.

References

1. F. R. Gantmacher, Applications of the theory of matrices, Interscience Publishers, New York, 1959.

2. H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-648.