the problem of the pawns

Sergey Kitaev and Toufik Mansour ^{∗}

16th May 2003

Matematik, Chalmers tekniska högskola och Göteborgs universitet, 412 96

Göteborg, Sweden kitaev@math.chalmers.se, toufik@math.chalmers.se

Abstract

In this paper we study the number M_{m,n} of ways to place nonattacking pawns on an m × n chessboard. We find an upper bound for M_{m,n} and analyse its asymptotic behavior. It turns out that lim_{m,n→∞}(M_{m,n})^{1/mn} exists and is bounded from above by (1 + \sqrt{5})/2. Also, we consider a lower bound for M_{m,n} by reducing this problem to that of tiling an (m + 1) × (n + 1) board with square tiles of size 1×1 and 2×2. Moreover, we use the transfer-matrix method to implement an algorithm that allows us to get an explicit formula for M_{m,n} for given m.

2000 Mathematics Subject Classification: 05A16, 05C50, 52C20, 82B20

1 Introduction

On an m × n chessboard, we place a number of nonattacking pawns, all of the same colour, say white. The main question here is: How many different placements are possible? A similar problem concerning placements of the maximum number of nonattacking kings on a 2m × 2n chessboard is treated in [W]. The main result of that paper is the following theorem.

∗Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

Theorem 1. Let f_{m}(n) denote the number of ways that mn nonattacking kings can be placed on a 2m × 2n chessboard. 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 → ∞).

Given an m × n chessboard. We mark a square containing a pawn by 1, and a square that does not contain a pawn by 0. The placement of pawns is then completely specified by an m×n binary matrix. Moreover, to be a legal placement, the binary matrix cannot contain the following two letter words:

and (here we use the fact that all pawns are of the same colour and thus they are allowed to attack at the same directions: either at North-West and North-East or at South-West and South-East). For example, the matrix

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

corresponds to a legal placement of pawns on a 3 × 6 board. So, our main question can be reformulated as follows: How many binary m × n matrices simultaneously avoid the words and ? We denote the number of such matrices by M_{m,n}.

Studying matrices avoiding certain words, and thus studying our original problem, is interesting, for instance, from a graph theoretic point of view [CW]. In that paper, the authors considered the (vertex) independence number of the m × n grid graph using the matrices with the property that no two consecutive 1’s occur in a row or a column.

In this paper, we use the transfer-matrix approach to implement an algorithm that allows us to find a formula for M_{m,n} for any given m (see Sections 3 and 4). Moreover, in Section 2 we find an upper bound for M_{m,n} and, in Section 3, we discuss how the tiling problem is related to finding a lower bound for M_{m,n}. Also, we prove that the double limit lim_{m,n→∞}(M_{m,n})^{1/mn} exists and is bounded from above by (1 + \sqrt{5})/2 (see Sections 4 and 2). Finally, in Section 5, we suggest an approach to study M_{m,n}, which, in particular, allows to prove that M_{2m,n} is a perfect square (see Theorem 7). Using this approach we obtain formulas for M_{m,n}, where 2 ≤ m ≤ 6.

2 The upper bound for M_{m,n}

To obtain an upper bound for M_{m,n}, we determine the number U_{m,n} of binary m × n matrices that avoid the word . Of course, U_{m,n} counts also the number of binary m×n matrices that avoid the word , which follows from arranging the columns of all matrices under consideration in reverse order (in particular, is the reverse of ).

The following theorem gives a formula for the number of binary matrices that avoid the word in terms of the Fibonacci numbers.

Theorem 2. For any n, m ≥ 0,

U_{m,n} = \{ \begin{matrix}F_{m+1}^{n−m+1} (∏_{i=0}^{m} F_{i})^{2} , & if n ≥ m, \\ F_{n+1}^{m−n+1} (∏_{i=0}^{n} F_{i})^{2} , & if n < m, \end{matrix}

where F_{i} is the i-th Fibonacci number defined by F_{0} = F_{1} = 1, and F_{n+2} = F_{n+1} + F_{n} for n ≥ 0.

Proof. Let A be an m × n (0,1)-matrix that avoids the word . We change the shape of A using the following procedure. We shift the first column of A one position down with respect to the second column. In the obtained shape, we shift the first and second columns one position down with respect to the third column, and so on. After shifting with respect to the n-th column, one obtains the shape Ā, that has the form similar to that on Figure 1.

Figure 1: The shape Ā for m = 4.

It is easy to see that A avoids the word if and only if Ā avoids the word . But Ā avoids if and only if each row of Ā avoids (there are no additional restrictions). This is well known and is not difficult to see that the number of different binary strings of length ℓ that avoid is given by F_{ℓ+2}.

To find U_{m,n}, it remains to find out the lengths of the rows in Ā, and since these rows are independent from each other, to multiply together the corresponding Fibonacci numbers. If n ≥ m, Ā has two rows of each of the following lengths: 1, 2, …, m − 1, and n − m + 1 rows of length m. So, in this case

U_{m,n} = F_{m+1}^{n−m+1} (∏_{i=0}^{m} F_{i})^{2} .

The case n < m is given by changing m by n, and n by m in the considerations above.

Let A be any binary matrix, we say that A avoids the k-diagonal word (see Figure 2) if there are no k consecutive 1’s in any diagonal of A. Theorem 2 can be generalized to the case of avoiding the k-diagonal word. This generalization involves the k-generalized Fibonacci numbers. We do not use the generalization to proceed with the problem of the pawns, but we state it as Theorem 3 because it is interesting by its own.

Figure 2: The k-diagonal word.

Let F_{k,n} be the n-th k-generalized Fibonacci number defined by F_{k,n} = 0 for n < 0, F_{k,0} = 1, and F_{k,n} = F_{k,n−1} + F_{k,n−2} + ⋯ + F_{k,n−k} for n ≥ 1 (for example, see [F, SP]).

Let U_{m,n}(k) denote the number of m × n binary matrices that avoid the k-diagonal word. The following theorem can be proved using the same arguments as those in Theorem 2 and the observation that the number of different binary strings of length ℓ that avoid the word \underbrace{11 … 1}_{k} is given by F_{k,ℓ+1} (we leave this observation as an exercise). Theorem 3. Let k ≥ 2. For all n, m ≥ 0,

U_{m,n}(k) = \{ \begin{matrix}F_{k,m+1}^{n−m+1} (∏_{i=0}^{m} F_{k,i})^{2} , & if n ≥ m, \\ F_{k,n+1}^{m−n+1} (∏_{i=0}^{n} F_{k,i})^{2} , & if n < m, \end{matrix}

where F_{k,i} is the i-th k-generalized Fibonacci number.

As a corollary to Theorem 2, we get an upper bound for M_{m,n}. Indeed, M_{m,n} ≤ U_{m,n} since U_{m,n} deals with avoidance of , whereas M_{m,n} deals additionaly with one more restriction, namely . We state this result as the following theorem. Theorem 4. We have

M_{m,n} ≤ \{ \begin{matrix}F_{m+1}^{n−m+1} (∏_{i=0}^{m} F_{i})^{2} , & if n ≥ m, \\ F_{n+1}^{m−n+1} (∏_{i=0}^{n} F_{i})^{2} , & if n < m, \end{matrix}

where F_{i} is the i-th Fibonacci number.

The upper bound for M_{m,n} involves the product of the first nonzero Fibonacci numbers. It is known [SP, A003266] that an asymptotic for the product of the first n nonzero Fibonacci numbers is given by

\frac{c}{\sqrt{5}^{n−1}} (\frac{1 + \sqrt{5}}{2})^{\frac{n(n−1)}{2}} ,  (1)

where c = ∏_{j≥1} (1 − (\frac{\sqrt{5} − 3}{2})^{j}) = 1.2267420107203532444176302 . . .. This result and Theorem 4 give the following theorem.

Theorem 5. We have

lim_{n,m→∞}(M_{m,n})^{\frac{1}{mn}} ≤ \frac{1 + \sqrt{5}}{2}.

Proof. The existence of the limit lim_{n,m→∞}(M_{m,n})^{\frac{1}{mn}} is proved in Theorem 6. Using Theorem 4, it is enough to prove that

lim_{n,m→∞}(U_{m,n})^{\frac{1}{mn}} = \frac{1 + \sqrt{5}}{2}.  (2)

For given two functions f(n) and g(n), we define f(n) ∼ g(n) if lim_{n→∞} \frac{f(n)}{g(n)} = 1. Suppose n ≥ m. By (1) we have

(∏_{i=0}^{m} F_{i})^{2} ∼ \frac{c^{2}}{\sqrt{5}^{2m−2}} (\frac{1 + \sqrt{5}}{2})^{m^{2}−m} ,

and using the formula for the Fibonacci numbers, namely

F_{m} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{m+1} − (\frac{1 − \sqrt{5}}{2})^{m+1}) ,

we obtain that

U_{m,n} ∼ \frac{c^{2}}{\sqrt{5}^{n+m−1}} (\frac{1 + \sqrt{5}}{2})^{nm+2n−2m+2} .

This formula holds for the case n < m, by replacing m, n by n, m in the considerations above. Hence, (2) holds.

3 Tiling rectangles and a lower bound for M_{m,n}

Let L_{m,n} denote the number of m × n binary matrices that simultaneously avoid the words , , and . Clearly, L_{m,n} ≤ M_{m,n}, since when we deal with L_{m,n} we have more restrictions than when we consider M_{m,n}.

Thus, we are interested in finding the numbers L_{m,n}, that give us a lower bound for M_{m,n}. In this section we show that L_{m,n}, in fact, gives the number of tilings of an (m + 1) × (n + 1) area with square tiles of size 1 × 1 and 2 × 2 which was studied in [H] and [CH]. So, the number of the tilings is equal to the number of m × n binary matrices that avoid the words , , and

. A bijection θ between these two combinatorial objects is given by the following.

Let A be an m × n matrix that avoids the words , , and . We make from A an (m+1)×(n+1) matrix Ā by adjoin an additional m×1 column consisting of 0’s from the right side, and an additional 1 × (n + 1) row, also having only 0’s, from below. Now, once we meet an occurrence of 1 in Ā, we place a 2 × 2 tile in such way, that the 1 appears in the top-left corner of the tile. After considering all 1’s and placing corresponding 2 × 2 tiles, we fill in the uncovered squares of Ā by 1 × 1 tiles. The fact that A avoids , , and guarantees that covering in the way proposed by us is non-overlapping, and thus we get a tiling of an (m + 1) × (n + 1) board.

Conversely, for any given tiling with square tiles of size 1 × 1 and 2 × 2, we can place 1 in the top-left corner of any 2×2 tile, 0’s in the other squares, and remove the rightmost column and the bottom row. Obviously, we get an m × n binary matrix that avoids the words , , and .

Figure 3 shows how the bijection θ works in the case of a 4 × 5 matrix.

Figure 3: The bijection θ.

Unfortunately, we cannot get much use of the papers [H] and [CH], since there, for our purpose, one has explicit formulas only for m = 2, 3, and for m = 4, 5 one has recursive formulas only. That means that from that source, we have an information about L_{m,n}, where 1 ≤ m ≤ 4.

Remark 1. If we use the transfer-matrix approach (see [M, pawns-kings]) for finding the formula for L_{m,n}, where m is given, then we get the following: L_{1,n} = F_{n+1}, L_{2,n} = \frac{1}{3}(2^{n+2} − (−1)^{n}), and

L_{3,n} = a (\frac{2}{3} + \frac{2\sqrt{13}}{3} cos β)^{n} + b (\frac{2}{3} − \frac{2\sqrt{39}}{3} sin β − \frac{2\sqrt{13}}{3} cos β)^{n}

+c (\frac{2}{3} + \frac{2\sqrt{39}}{3} sin β − \frac{2\sqrt{13}}{3} cos β)^{n} ,

where β = \frac{1}{3} arctan (\frac{3}{8} \sqrt{237}), a ≈ 1.51212496094, b ≈ −0.542960193686, and c ≈ 0.0308352327442.

4 The transfer-matrix method

We use the transfer-matrix method, in a manner that is similar to way it was used in [W].

For m, n fixed, we can think of constructing the m × n binary matrices avoiding the words and by gluing together columns that are chosen from the collection of possible columns, making sure that when we glue an additional column onto the right-hand edge of the structure, the new column does not come into conflict with the previous right-hand column. The collection of possible columns C_{m} is the set of all m-vectors v of 0’s and 1’s. Clearly, |C_{m}| = 2^{m}.

The condition that vectors v, w in C_{m} are possible consecutive pair of columns in a matrix avoiding and is simply that v_{i}w_{i+1} = 0 and v_{i+1}w_{i} = 0 for all i, 1 ≤ i ≤ m − 1. We say that such v and w are crossorthogonal.

Thus, all possible matrices under consideration are obtained by beginning with some vector of C_{m}, and in general, having arrived at some sequence of vectors of C_{m}, adjoin any vector of C_{m} that is cross-orthogonal to the last one previously chosen until n vectors have been selected.

We define a matrix T = T_{m}, the transfer matrix of the problem, as follows. T is an 2^{m} × 2^{m} symmetric matrix of 0’s and 1’s whose rows and columns are indexed by vectors of C_{m}. The entry of T in position (v, w) is 1 if the vectors v, w are cross-orthogonal, and 0 otherwise. T depends only on m, not on n.

Let M_{m,n}(u) denote the number of m × n binary matrices avoiding the words and whose rightmost column vector is u. Then, clearly, we have

M_{m,n+1}(v) = ∑_{u∈C_{m}} M_{m,n}(u)T_{u,v} (n ≥ 0; v ∈ C_{m}),

or, in matrix-vector notation, M_{n+1} = T M_{n}, with M_{0} = 1 the vector of length 2^{m} whose entries are all 1’s. It follows that M_{n} = T^{n} · 1, for all n ≥ 0. The number of matrices M_{m,n} is the sum of the entries of the vector M_{n}. Thus, if 1′ denote the row of length 2^{m} whose entries are all 1’s, we have

M_{m,n} = 1′ · T^{n} · 1,

i.e., M_{m,n} is the sum of all of the entries of the matrix T^{n}.

Example 1. The transfer-matrices T_{2} and T_{3} (see [M, pawns]) are given, for instance, by

T_{2} = (\begin{matrix}1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}) and T_{3} = (\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) .

Since T has nonnegative entries, its dominant eigenvector cannot be orthogonal to 1, and so we have at once that lim_{n→∞}(M_{m,n})^{\frac{1}{n}} exists for each m, and is equal to α_{m}, the largest eigenvalue of the transfer-matrix T (real and symmetric matrix). It follows that

lim inf_{m}(α_{m})^{\frac{1}{m}} = lim inf_{m,n}(M_{m,n})^{\frac{1}{mn}} ≤ lim sup_{m,n}(M_{m,n})^{\frac{1}{mn}} = lim sup_{m}(α_{m})^{\frac{1}{m}} . (3)

Theorem 6. The limit lim_{m,n→∞}(M_{m,n})^{\frac{1}{mn}} exists.

Proof. By the fact that T is symmetric and real matrix together with using the maximum principle we get, for any q ≥ 1,

\frac{(1, (T_{m})^{q} · 1)}{(1, 1)} ≤ (α_{m})^{q}.

Since M_{m,q} = M_{q,m} by the definitions, we have (1, (T_{m})^{q} · 1) = (1, (T_{q})^{m} · 1). Hence,

(\frac{(1, (T_{q})^{m} · 1)}{(1, 1)})^{\frac{1}{m}} ≤ (α_{m})^{\frac{q}{m}} .

Taking the lim inf_{m} of both sides of the inequality above, together with using the fact that |C_{m}| = 2^{m}, we have \frac{α_{q}}{2} ≤ (lim inf_{m}(α_{m})^{\frac{1}{m}} )^{q}, which implies

lim sup_{q}(α_{q})^{\frac{1}{q}} ≤ lim inf_{m}(α_{m})^{\frac{1}{m}} .

Using (3) we get the desired result.

Using the transfer-matrix approach one can obtain an explicit formula for M_{m,n}, where m ≥ 1 is given. We implemented an algorithm for finding the transfer-matrix T_{m} in Maple (see [M, pawns]). This algorithm yields an explicit formula for M_{m,n}, where 1 ≤ m ≤ 3 (see Table 1). Moreover, it finds the maximum eigenvalue of T_{m} for given m.

m M_{m,n}
1 2^{n}
2 \frac{7}{10}(η_{1}^{2n} + η_{2}^{2n}) + \frac{3\sqrt{5}}{10}(η_{1}^{2n} − η_{2}^{2n}) − \frac{2}{5}(−1)^{n},

where η_{1} = \frac{1}{2}(1 + \sqrt{5}) and η_{2} = \frac{1}{2}(1 − \sqrt{5})

3 \frac{1}{13}(η_{1}^{n+2} + η_{2}^{n+2}) + \frac{\sqrt{3}^{n+1}}{13} (4 − \sqrt{3} − (4 + \sqrt{3})(−1)^{n}),

where η_{1} = \frac{1}{2}(5 + \sqrt{13}) and η_{2} = \frac{1}{2}(5 − \sqrt{13})

Table 1: Explicit formula for M_{m,n} where m = 1, 2, 3.

For example, the maximum eigenvalue of T_{m} is 2, (\frac{1+\sqrt{5}}{2})^{2}, \frac{5+\sqrt{13}}{2} and

\frac{8}{3} + \frac{4}{3} \sqrt{7} cos (\frac{1}{3} arctan (\frac{3}{67} \sqrt{111})), for m = 1, 2, 3, 4; respectively.

Remark 2. In the case of m = 4, the eigenvalues of T are given by

λ_{1} = \frac{2}{3} − \frac{4}{3} cos (\frac{1}{3}π − β) − \frac{4}{3} \sqrt{3} sin (\frac{1}{3}π − β) ,
λ_{2} = \frac{2}{3} − \frac{4}{3} cos (\frac{1}{3}π − β) + \frac{4}{3} \sqrt{3} sin (\frac{1}{3}π − β) ,
λ_{3} = \frac{8}{3} − \frac{2}{3} \sqrt{7} cos γ − \frac{2}{3} \sqrt{21} sin γ,
λ_{4} = \frac{8}{3} − \frac{2}{3} \sqrt{7} cos γ + \frac{2}{3} \sqrt{21} sin γ,
λ_{5} = −\frac{2}{3} − \frac{4}{3} cos β − \frac{4}{3} \sqrt{3} sin β,
λ_{6} = −\frac{2}{3} − \frac{4}{3} cos β + \frac{4}{3} \sqrt{3} sin β,
λ_{7} = \frac{2}{3} + \frac{8}{3} cos (\frac{1}{3}π − β) ,
λ_{8} = −\frac{2}{3} + \frac{8}{3} cos (\frac{1}{3}π − β) ,
λ_{9} = \frac{8}{3} + \frac{4}{3} \sqrt{7} cos γ,

where β = \frac{1}{3} arctan (\frac{3}{5} \sqrt{111}) and γ = \frac{1}{3} arctan (\frac{3}{67} \sqrt{(}111)).

5 Formulas for M_{m,n}

In this section we suggest another approach to study M_{m,n}. In particular, we obtain formulas for M_{m,n}, where 2 ≤ m ≤ 6 (the cases m = 2, 3 already appear in Table 1). We show how to use the following simple observation in order to investigate M_{m,n}.

Observation 1. A pawn placed on a square of a chessboard cannot attack a square of the different colour.

According to Observation 1, M_{m,n} = B_{m,n}·W_{m,n}, where B_{m,n} (resp. W_{m,n}) is the number of ways to place nonattacking pawns on the black (resp. white) squares of an m × n chessboard. Thus, the original problem of finding M_{m,n} can be reduced to considering independently two shapes: that consisting of all the black squares, and the shape consisting of all the white squares. We use this idea in the proofs of the following theorem and propositions.

Theorem 7. We have that M_{2m,n} = a^{2} for some natural number a, that is M_{2m,n} is a perfect square.

Proof. Using the discussion right above this theorem, it is enough to prove that B_{2m,n} = W_{2m,n}. Indeed, on a 2m × n chessboard, the number of black squares is the same as that of white squares. Moreover, if we consider the shape that, say, the white squares form, reverse it horizontally (that is, draw the rows in reverse order), then we get exactly the same shape that the black squares form. Also, it is easy to see that a placement of pawns before the reversion is legal if and only if it is legal after the reversion. Thus, we have B_{2m,n} = W_{2m,n}.

Proposition 1. We have

M_{2,n} = (F_{n+2})^{2},

where F_{n} is the n-th Fibonacci number defined by F_{0} = F_{1} = 1, and F_{n+2} = F_{n+1} + F_{n} for n ≥ 0.

Proof. Let us draw the black squares of a 2 × n chessboard in one 1 × n row, in the order we meet these squares in the chessboard by going from left to right. Obviously, we have a legal placement of pawns on the chessboard if and only if we have no two consecutive pawns in the row, or in terms of matrices and word avoidance, the row avoids the word . The number of different legal rows is given by the (n + 2)-nd Fibonacci number, that is B_{2,n} = F_{n+2}.

Figure 4: Finding M_{2,5}.

Independently, we can make the same considerations with the white squares on the chessboard to get W_{2,n} = F_{n+2}. Thus, M_{2,n} = (F_{n+2})^{2}. For instance, Figure 4 shows that for finding M_{2,5} one can consider two rows of length 5.

Proposition 2. For all n ≥ 0, M_{3,2n+1} = (4t_{n} − 3t_{n−1})(2t_{n} − 3t_{n−1}) and M_{3,2n} = t_{n}^{2}, where

t_{n} = \frac{1}{\sqrt{13}} ((\frac{5 + \sqrt{13}}{2})^{n+1} − (\frac{5 − \sqrt{13}}{2})^{n+1}) .

Proof. Let a_{n} (resp. b_{n}) denote the number of legal placements of pawns in the first (resp. second) shape on Figure 5 defined by black squares (there are n columns in each shape). According to Observation 1, one has M_{3,n} = a_{n}b_{n}. Let us find a_{n} and b_{n}.

Figure 5: The shapes under consideration.

We consider the first shape. There are two black squares in the first column. Depending on whether or not these squares have pawns, we have four possibilities. As before, we use 1 for a square having a pawn, and 0 otherwise. Thus, the first column of the shape is either 00, or 01, or 10, or 11 when reading from top to bottom. In the first case, the first column of the shape does not affect the rest of the shape, and therefore can be removed. So, in the first case the number of placements of pawns is b_{n−1}. In the second, third and fouth cases, the black square in the second column must contain no pawn, that is 0, in order to have a legal placement. This 0 does not affect what follows to the right of it, and thus two first columns of the shape can be removed. So, the second, third and fouth cases give 3a_{n−2} placements of pawns. Thus, a_{n} = 3a_{n−2} + b_{n−1}. Similarly, one can consider the second shape to get b_{n} = a_{n−1} + b_{n−2}. Solving the equations for a_{n} and b_{n}, we have

a_{2n} = t_{n}, a_{2n+1} = 4t_{n} − 3t_{n−1}, b_{2n} = t_{n}, and b_{2n+1} = 2t_{n} − 3t_{n−1}.

This gives the desired result.

Remark 3. If a(x) and b(x) denote the generating functions for the numbers a_{n} and b_{n} respectively in the proof of Proposition 2, then

a(x) = \frac{1 + 4x − 3x^{3}}{1 − 5x^{2} + 3x^{4}} and b(x) = \frac{1 + 2x − 3x^{3}}{1 − 5x^{2} + 3x^{4}} .

Proposition 3. We have that M_{4,n} = α_{n}^{2}, where the generating function for the numbers α_{n} is given by

\frac{1 + 2x − 2x^{2}}{1 − 2x − 2x^{2} + 2x^{3}} .

Proof. Let α_{n} (resp. β_{n}, γ_{n}, δ_{n}) denote the number of legal placements of pawns in the first (resp. second, third, fouth) shape on Figure 6 defined by black squares (there are n columns in each shape). As in the proof of Theorem 7, using horisontal reverse of rows, it is easy to see that α_{n} = β_{n} and γ_{n} = δ_{n}. Now, according to Observation 1, one has M_{4,n} = α_{n}β_{n} = (α_{n})^{2}. Let us find α_{n}.

Figure 6: The shapes under consideration.

We proceed in the same way as we do in Proposition 2. If the first column of the first shape is 00 when reading the content of the black squares from top to bottom, we can remove this column since it does not affect the rest of the shape. So, in this case the number of legal placements of pawns is β_{n−1} = α_{n−1}. If instead of 00 we have 01 or 11, the content of the black squares in the second column must be 00, in which case we can remove the first two columns since they do not affect the rest of the shape. So, in this case we have 2α_{n−2} placements. The case left is when the first column is 10. In this case the top element of the second column must be 0, and we have no information concerning the second element in this column. Thus, in this case we have γ_{n−1} replacements. Therefore,

α_{n} = α_{n−1} + 2α_{n−2} + γ_{n−1}.  (4)

Now, to proceed further with finding α_{n}, we need to find γ_{n}. If the element in the first column of the third shape is 0, then we can remove this element, which gives β_{n−1} = α_{n−1} replacements of pawns. If this element is 1, then the bottom element in the second column must be 0, which obviously gives δ_{n−1} = γ_{n−1} replacements. Thus,

γ_{n} = γ_{n−1} + α_{n−1}.  (5)

Now, from Equations (4) and (5) we have

α_{n} = 2α_{n−1} + 2α_{n−2} − 2α_{n−3},

which gives the desired result.

In the way similar to that Propositions 2 and 3 are proved, on can prove the following two propositions, which we state without proof.

Proposition 4. For all n ≥ 0, M_{5,n} = α_{n}β_{n}, where the generating functions for the numbers α_{n} and β_{n} are given by

\frac{1 + 7x − 4x^{2} − 7x^{3} + 5x^{4}}{(1 + x)(1 − 2x − 6x^{2} + 10x^{3} − 4x^{4})}

and

\frac{1 + 3x + x^{2} − 5x^{3} + 4x^{4}}{(1 + x)(1 − 2x − 6x^{2} + 10x^{3} − 4x^{4})},

respectively.

Proposition 5. We have that M_{6,n} = α_{n}^{2}, where the generating function for the numbers α_{n} is given by

\frac{1 + 5x − 9x^{2} − 5x^{3} + 6x^{4}}{1 − 3x − 6x^{2} + 11x^{3} + 5x^{4} − 6x^{5}} .

References

[CW] N. Calkin, H. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math. 11 (1998) 1, 54–60.

[CH] P. Chinn, S. Heubach, Patterns arising from tiling rectangles with 1×1 and 2 × 2 squares, Congressus Numerantium 150 (2001), 173–192.

[F] I. Flores, k-Generalized Fibonacci numbers, Fib. Quart. 5 (1967), 258– 266.

[H] S. Heubach, Tiling an n-by-m area with squares of size up to k-by-k (m ≤ 5), Congressus Numerantium 140 (1999), 43–64.

[M] T. Mansour, Pawns, Maple Programming, available in <http://www.math.chalmers.se/∼toufik>.

[SP] N.J.A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York (1995).

[W] H. Wilf, The problem of the kings, Electron. J. Combin. 2 (1995), #R3.