Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards

Richard M. Low and Ardak Kapbasov Department of Mathematics San Jose State University San Jose, CA 95192 USA

                     richard.low@sjsu.edu
                   ardak.kapbasov@yahoo.com

Abstract In this paper, we count the number of non-attacking bishop and king positions on the regular and cylindrical m×n (where m = 1, 2, 3) chessboards. This is accomplished through the use of scientific computing, recurrence relations, generating functions and closed-form formulas.

1 Introduction

Stevens [4] gave a nice combinatorial proof of the Fibonacci identity F_{n}^{2} = 2(F_{n−1}^{2} + F_{n−2}^{2}) − F_{n−3}^{2}. This was accomplished by enumerating the non-attacking bishop positions on a 2 × n chessboard in two different ways. Inspired by his result, we sought to generalize his method to an m × n chessboard and hoped to establish other combinatorial identities. As it turned out, this was not so easy to do. In pursuing our original goal, we had to count the number of non-attacking bishop and king positions on various types of chessboards. This is the focus of our paper.

2 Regular chessboards

Let n ≥ 1. Clearly, there are 2^{n} non-attacking bishop positions on a 1 × n chessboard. Stevens [4] pointed out that the number of non-attacking bishop positions on a 2 × n chessboard is F_{n+2}^{2} (where F_{0} = 0, F_{1} = 1 and F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2). Let us count the non-attacking bishop positions on a 3 × n chessboard. Each non-attacking bishop position (on a 3×n chessboard) can be associated with a string of length n (using the digits 0 through 7) as described in Figure 1.

Figure 1:

The length n strings that we are interested in do not contain the following substrings:

• 12, 13, 16, 17, 21, 23, 24, 25, 26, 27, 31, 32, 33, 34, 35, 36, 37, 42, 43, 46, 47, 52, 53, 56, 57, 61, 62, 63, 64, 65, 66, 67, 71, 72, 73, 74, 75, 76, 77.

• 104, 105, 106, 107, 114, 115, 144, 145, 154, 155, 304, 305, 306, 307, 401, 403, 405, 407, 411, 415, 441, 445, 451, 455, 501, 503, 504, 505, 506, 507, 511, 514, 515, 541, 544, 545, 551, 554, 555, 601, 603, 605, 607, 701, 703, 704, 705, 706, 707.

\begin{matrix}n & b(n) & w(n) & B_{3}(n) \\ 0 & 1 & 1 & 1 \\ 1 & 4 & 2 & 8 \\ 2 & 5 & 5 & 25 \\ 3 & 10 & 7 & 70 \\ 4 & 15 & 15 & 225 \\ 5 & 34 & 22 & 748 \\ 6 & 49 & 49 & 2401 \\ 7 & 108 & 71 & 7668 \\ 8 & 157 & 157 & 24649 \\ 9 & 348 & 228 & 79344 \\ 10 & 505 & 505 & 255025 \end{matrix}

Table 1: The number of non-attacking bishop positions on a 3 × n chessboard, where n ≥ 0.

Throughout this paper, we assume that the chessboard has a black square in the upper left-hand corner. A chessboard is viewed as being fixed in position and orientation. Let B_{3}(n) denote the number of non-attacking bishop positions on a 3 × n chessboard. Let b(n) and w(n) denote the number of non-attacking bishop positions on the black and white squares of a 3×n chessboard, respectively. For the degenerate case where n = 0, we set b(0) = w(0) = 1 and B_{3}(0) = b(0) · w(0) = 1. A computer program was created and calculated the values found in Table 1. We note that the sequences b(n), w(n) and B_{3}(n) do not appear in [3].

The computations were performed on the following platform: Intel Q9400 @ 2.6 GHz with 8 GB RAM. The program was written in C. For n = 1, 2, …, 8, the computational runtimes were nearly instantaneous. However, approximately four minutes were required for the n = 9 case and 30 minutes for the n = 10 case. Although this computational approach works, it is clear that it does not scale well as n gets large. We now use a combinatorial approach to gain better insight on this enumeration problem.

For odd n ≥ 1, a truncated 3 × n chessboard has a missing black square in the lower righthand corner of the board. Let b_{T} (n), for odd n ≥ 1, denote the number of non-attacking bishop positions on the black squares of a truncated 3 × n board. Clearly, b_{T} (1) = 2.

Lemma 1. For n ≥ 1, b_{T} (2n+1) = b(2n)+b_{T} (2n−1) = b(2n)+b(2n−2)+⋯+b(2)+b_{T} (1).

Proof. We establish the claim using strong mathematical induction. Let P (n) be the statement: b_{T} (2n + 1) = b(2n) + b_{T} (2n − 1) = b(2n) + b(2n − 2) + ⋯ + b(2) + b_{T} (1).

• Base Case. Note that b_{T} (3) = 7 = 5 + 2 = b(2) + b_{T} (1). Thus, P (1) is true.

• Inductive Step. Assume P (n) is true, for all n ≤ k. Now, consider b_{T} (2(k + 1) + 1), the number of non-attacking bishop positions on the black squares of a truncated 3 × (2(k + 1) + 1) chessboard. Any such position either has no bishop or a bishop on the black square of the last column of the truncated chessboard. See Figure 2. Thus,

b_{T} (2(k + 1) + 1) = b(2(k + 1)) + b_{T} (2(k + 1) − 1)
= b(2(k + 1)) + b_{T} (2k + 1)
= b(2(k + 1)) + b(2k) + b(2k − 2) + ⋯ + b(2) + b_{T} (1)

= b(2(k + 1)) + b(2(k + 1) − 2) + b(2(k + 1) − 4) + ⋯ + b(2) + b_{T} (1).

Hence, P (n) is true, for all n ≥ 1.

Figure 2: The two possible cases for a non-attacking bishop position on the black squares of a truncated 3 × (2(k + 1) + 1) chessboard, where k ≥ 1.

\begin{matrix}n & b_{T} (n) \\ 1 & 2 \\ 3 & 7 \\ 5 & 22 \\ 7 & 71 \\ 9 & 228 \\ 11 & 733 \end{matrix}

Table 2: The number of non-attacking bishop positions on the black squares of a truncated 3 × n chessboard, where n ≥ 1 and odd.

For odd n ≥ 1, the sequence b_{T} (n) (\underline{A030186}) is found in [3]. See Table 2. There, we see the sequence described in the following way:

a_{k} = 3a_{k−1} + a_{k−2} − a_{k−3}, for k ≥ 3, and a_{0} = 1, a_{1} = 2, a_{2} = 7.

\begin{matrix}k & a_{k} \\ 0 & 1 \\ 1 & 2 \\ 2 & 7 \\ 3 & 22 \\ 4 & 71 \\ 5 & 228 \end{matrix}

Table 3: Some values of a_{k}.

Its generating function is

A(x) = \frac{1 − x}{1 − 3x − x^{2} + x^{3}} = ∑_{k=0}^{∞} a_{k}x^{k}.

Lemma 2. For n ≥ 2, b(2n + 1) = b(2n) + b_{T} (2n − 1) + b_{T} (2n − 1) + b(2n − 2).

Proof. Let n ≥ 2. Every non-attacking bishop position on the black squares of a 3×(2n+1) chessboard is in one of several cases: there is no bishop, one bishop or two bishops in the last column of the chessboard. See Figure 3. Thus, b(2n + 1) = b(2n) + b_{T} (2n − 1) + b_{T} (2n − 1) + b(2n − 2).

Figure 3: The possible cases for a non-attacking bishop position on the black squares of a 3 × (2n + 1) chessboard, where n ≥ 2.

Lemma 3. For n ≥ 2, b(2n) = b(2n − 1) + b(2n − 2) and w(2n) = b(2n). Furthermore, B_{3}(2n) = (b(2n − 1) + b(2n − 2))^{2}.

Proof. Let n ≥ 2. Every non-attacking bishop position on the black squares of a 3 × 2n chessboard is in one of two cases: there is no bishop or one bishop in the last column of the chessboard. See Figure 4. Thus, b(2n) = b(2n − 1) + b(2n − 2). On a 3 × 2n chessboard, the configuration of white squares is identical to the configuration of black squares. Hence, w(2n) = b(2n). Since bishops on white squares cannot attack bishops on black squares, B_{3}(2n) = (b(2n − 1) + b(2n − 2))^{2}.

Figure 4: The possible cases for a non-attacking bishop position on the black squares of a 3 × 2n chessboard, where n ≥ 2.

Lemma 4. For n ≥ 0, w(2n + 1) = b_{T} (2n + 1) = a_{n+1}.

Proof. Note that w(1) = b_{T} (1) = 2 = a_{1}. Let n ≥ 1. From Figure 5 and Lemma 3, we see that

w(2n + 1) = w(2n) + w(2n − 1)
= b(2n) + w(2n − 1).

Through iteration, one obtains w(2n+1) = b(2n)+b(2n−2)+⋯+b(2)+b_{T} (1). By Lemma 1, this yields w(2n + 1) = b_{T} (2n + 1) = a_{n+1}.

Figure 5: The possible cases for a non-attacking bishop position on the white squares of a 3 × (2n + 1) chessboard, where n ≥ 1.

For even n ≥ 2, a truncated 3 × n chessboard has a missing white square in the lower righthand corner of the board. Let w_{T} (n), for even n ≥ 2, denote the number of nonattacking bishop positions on the white squares of a truncated 3 × n board. For example, w_{T} (2) = 3. Note that for the degenerate case (where n = 0), we set w_{T} (0) = 1.

Lemma 5. For n ≥ 2, w_{T} (2n) = w(2n − 1) + w_{T} (2n − 2) = w(2n − 1) + w(2n − 3) + ⋯ + w(3) + w_{T} (2).

Proof. We establish the claim using strong mathematical induction. Let P (n) be the statement: w_{T} (2n) = w(2n − 1) + w_{T} (2n − 2) = w(2n − 1) + w(2n − 3) + ⋯ + w(3) + w_{T} (2).

• Base Case. From Figure 6, we see that w_{T} (4) = w(3) + w_{T} (2). Thus, P (2) is true.

Figure 6: The possible cases for a non-attacking bishop position on the white squares of a truncated 3 × 4 chessboard.

• Inductive Step. Assume P (n) is true, for all n ≤ k. Now, consider w_{T} (2(k + 1)), the number of non-attacking bishop positions on the white squares of a truncated 3 × 2(k + 1) chessboard. Any such position either has no bishop or a bishop on the white square of the last column of the truncated chessboard. Thus,

w_{T} (2(k + 1)) = w(2(k + 1) − 1) + w_{T} (2(k + 1) − 2)
= w(2(k + 1) − 1) + w_{T} (2k)

= w(2(k + 1) − 1) + w(2k − 1) + w(2k − 3) + ⋯ + w(3) + w_{T} (2)

= w(2(k + 1) − 1) + w(2(k + 1) − 3) + w(2(k + 1) − 5) + ⋯
+ w(3) + w_{T} (2).

Hence, P (n) is true, for all n ≥ 2.

\begin{matrix}n & w_{T} (n) \\ 0 & 1 \\ 2 & 3 \\ 4 & 10 \\ 6 & 32 \\ 8 & 103 \\ 10 & 331 \end{matrix}

Table 4: The number of non-attacking bishop positions on the white squares of a truncated 3 × n chessboard, where n ≥ 0 and even.

The sequence w_{T} (2n) (\underline{A033505}) is found in [3]. See Table 4. There, we see that w_{T} (2n) = ∑_{i=0}^{n} a_{i}, for n ≥ 0. Its generating function is

W_{T} (x) = \frac{1}{1 − 3x − x^{2} + x^{3}} = ∑_{k=0}^{∞} w_{T} (2k)x^{k}

and hence,

W_{T} (x^{2}) = \frac{1}{1 − 3x^{2} − x^{4} + x^{6}} = ∑_{k=0}^{∞} w_{T} (2k)x^{2k}.

Lemma 6. For n ≥ 2, w(2n) = w(2n − 1) + w_{T} (2n − 2) + w_{T} (2n − 2) + w(2n − 3) = w(2n − 1) + w(2n − 3) + 2 ∑_{i=0}^{n−1} a_{i}. Also, w(2) = 5.

Proof. It is clear that w(2) = 5. Let n ≥ 2. From Figure 7, we see that w(2n) = w(2n − 1) + w_{T} (2n − 2) + w_{T} (2n − 2) + w(2n − 3). By remarks preceding this Lemma, we have w_{T} (2n − 2) = w_{T} (2(n − 1)) = ∑_{i=0}^{n−1} a_{i}. Thus, the claim is established.

Using the results above, we have the following systems of recurrence relations:

System for b(k): For n ≥ 3,

b(2n + 1) = b(2n) + 2a_{n} + b(2n − 2),
b(2n) = b(2n − 1) + b(2n − 2),
a_{n} = 3a_{n−1} + a_{n−2} − a_{n−3},

where a_{0} = 1, a_{1} = 2, a_{2} = 7, b(1) = 4, b(2) = 5, b(3) = 10, b(4) = 15 and b(5) = 34.

Figure 7: The possible cases for a non-attacking bishop position on the white squares of a 3 × 2n chessboard, where n ≥ 2.

This can be written as the piecewise-defined recurrence relation

b(k) = \begin{cases}b(k − 1) + 2a_{\frac{k−1}{2}} + b(k − 3), & if k is odd; \\ b(k − 1) + b(k − 2), & if k is even, \end{cases}

for k ≥ 3, and b(0) = 1, b(1) = 4 and b(2) = 5. System for w(k): For n ≥ 3,

w(2n + 1) = b_{T} (2n + 1) = a_{n+1},
a_{n} = 3a_{n−1} + a_{n−2} − a_{n−3},

where a_{0} = 1, a_{1} = 2, a_{2} = 7, w(1) = 2, w(3) = 7 and w(5) = 22.

We now find generating functions for these systems of recurrence relations. For k odd, we have b(k) = b(k − 1) + 2a_{\frac{k−1}{2}} + b(k − 3). Set k = 2t + 1. Then, 2a_{t} = b(2t + 1) − b(2t) − b(2t − 2). Substituting this into 2a_{k} = 3 · 2a_{k−1} + 2a_{k−2} − 2a_{k−3} yields

b(2k + 1) − b(2k) − b(2k − 2) = 3(b(2k − 1) − b(2k − 2) − b(2k − 4)) +

(b(2k − 3) − b(2k − 4) − b(2k − 6)) − (b(2k − 5) − b(2k − 6) − b(2k − 8)).

Thus,

b(2k + 1) = b(2k) + b(2k − 2) + 3b(2k − 1) − 3b(2k − 2) −
3b(2k − 4) + b(2k − 3) − b(2k − 4) − b(2k − 6) −
b(2k − 5) + b(2k − 6) + b(2k − 8).

Hence,

b(2k + 1) = b(2k) + 3b(2k − 1) − 2b(2k − 2) + b(2k − 3) −
4b(2k − 4) − b(2k − 5) + b(2k − 8).

For k even, we have b(k) = b(k − 1) + b(k − 2). Thus, b(2t) = b(2t − 1) + b(2t − 2).

Now, set g(k) = b(2k) and h(k) = b(2k + 1). Then,

g(k) = b(2k) = h(k − 1) + g(k − 1),

and

h(k) = b(2k + 1) = g(k) + 3h(k − 1) − 2g(k − 1) + h(k − 2) −
4g(k − 2) − h(k − 3) + g(k − 4).

Using Maple, we obtain the generating functions

G(x) = \frac{1 + 2x − x^{2}}{1 − 3x − x^{2} + x^{3}} = ∑_{k=0}^{∞} g(k)x^{k} = ∑_{k=0}^{∞} b(2k)x^{k},

and

H(x) = \frac{4 − 2x}{1 − 3x − x^{2} + x^{3}} = ∑_{k=0}^{∞} h(k)x^{k} = ∑_{k=0}^{∞} b(2k + 1)x^{k}.

Thus,

B(x) = G(x^{2}) + xH(x^{2}) = \frac{1 + 4x + 2x^{2} − 2x^{3} − x^{4}}{1 − 3x^{2} − x^{4} + x^{6}} = ∑_{n=0}^{∞} b(n)x^{n}.

We also have the generating function

J (x) = \frac{1}{x} · (\frac{1 − x}{1 − 3x − x^{2} + x^{3}} − 1) = \frac{2x + x^{2} − x^{3}}{x − 3x^{2} − x^{3} + x^{4}} = ∑_{k=0}^{∞} w(2k + 1)x^{k}.

Thus,

W(x) = G(x^{2}) + xJ (x^{2}) = \frac{1 + 2x + 2x^{2} + x^{3} − x^{4} − x^{5}}{1 − 3x^{2} − x^{4} + x^{6}} = ∑_{n=0}^{∞} w(n)x^{n}.

Using Doron Zeilberger’s powerful Cfinite Maple package [5] to calculate the Hadamard product B(x) ⊙ W(x), we obtain the generating function for B_{3}(n), namely

𝔹_{3}(x) = \frac{−1 − 5x − x^{2} + 7x^{3} + 5x^{4} − x^{5} + x^{6} − x^{7}}{−1 + 3x + 2x^{3} + 4x^{4} − 10x^{5} − 2x^{6} − x^{8} + x^{9}} = ∑_{n=0}^{∞} B_{3}(n)x^{n}.

Theorem 7. For n ≥ 0, the number of non-attacking bishop positions on a 3 × n chessboard is B_{3}(n) = b(n) · w(n). The generating function for B_{3}(n) is the Hadamard product 𝔹_{3}(x) = B(x) ⊙ W(x).

Proof. Bishops on white squares cannot attack bishops on black squares.

We now shift our focus to counting the non-attacking king positions on an m × n chessboard, where m = 1, 2 and 3. The Fibonacci sequence is described by the recurrence relation: F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2}, for all n ≥ 2. For all n ≥ 1, the number of nonattacking king positions on a 1 × n chessboard is known to be F_{n+2} [1, p. 510, Exercise 26]. Let K_{2}(n) denote the number of non-attacking king positions on a 2 × n chessboard. For the degenerate case (n = 0), we set K_{2}(0) = 1. Clearly, K_{2}(1) = 3.

Lemma 8. For n ≥ 2, K_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 2), where K_{2}(0) = 1 and K_{2}(1) = 3.

Proof. Let n ≥ 2. Every non-attacking king position on a 2 × n chessboard is in one of two cases: there is no king or one king in the last column of the chessboard. See Figure 8. Thus, K_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 2).

Figure 8: The possible cases for a non-attacking king position on a 2 × n chessboard, where n ≥ 2.

The sequence K_{2}(n) appears as a subsequence of (\underline{A001045}) in [3]. See Table 5. There, we see the generating function

K_{2}(x) = \frac{x}{1 − x − 2x^{2}} = x + x^{2} + 3x^{3} + 5x^{4} + 11x^{5} + 21x^{6} + 43x^{7} + 85x^{8} + ⋯

\begin{matrix}n & K_{2}(n) \\ 0 & 1 \\ 1 & 3 \\ 2 & 5 \\ 3 & 11 \\ 4 & 21 \\ 5 & 43 \end{matrix}

Table 5: The number of non-attacking king positions on a 2 × n chessboard, where n ≥ 0.

Thus, the generating function for K_{2}(n) is

𝕂_{2}(x) = \frac{1}{x^{2}} · (\frac{x}{1 − x − 2x^{2}} − x) = \frac{1 + 2x}{1 − x − 2x^{2}} = ∑_{n=0}^{∞} K_{2}(n)x^{n}.

Theorem 9. For n ≥ 0, the number of non-attacking king positions on a 2 × n chessboard is K_{2}(n) = \frac{1}{3}(2^{n+2} − (−1)^{n}).

Proof. Using Lemma 8, we will establish the claim with strong mathematical induction. Let P (n) be the statement: K_{2}(n) = \frac{1}{3}(2^{n+2} − (−1)^{n}) is a solution to the recurrence relation K_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 2), where K_{2}(0) = 1 and K_{2}(1) = 3.

• Base Case. Note that 1 = K_{2}(0) = \frac{1}{3}(2^{0+2} − (−1)^{0}). Thus, P (0) is true.

• Inductive Step. Assume P (n) is true, for all n ≤ k. Then,

K_{2}(k + 1) = K_{2}(k) + 2 · K_{2}(k − 1)

= \frac{1}{3}(2^{k+2} − (−1)^{k}) + \frac{2}{3}(2^{k+1} − (−1)^{k−1})

= \frac{1}{3} · 2^{k+2} − \frac{1}{3}(−1)^{k} + \frac{2}{3} · 2^{k+1} − \frac{2}{3}(−1)^{k−1}

= \frac{1}{3} · 2^{k+2} + \frac{1}{3} · 2^{k+2} + \frac{1}{3}(−1)^{k+1} − \frac{2}{3}(−1)^{k+1}

= \frac{1}{3}(2 · 2^{k+2} + (−1)^{k+1} − 2(−1)^{k+1})

= \frac{1}{3}(2^{(k+1)+2} − (−1)^{k+1}).

Hence, P (n) is true, for all n ≥ 0.

For n ≥ 1, an extended 3 × n chessboard has an extra square attached (in the horizontal direction) to the lower righthand corner of the board. Let K_{E}(n) denote the number of nonattacking king positions on an extended 3 × n chessboard. We set K_{E}(0) = 2. Furthermore, let K_{3}(n) denote the number of non-attacking king positions on a 3 × n chessboard. We set K_{3}(0) = 1. A direct calculation yields K_{3}(1) = 5.

Lemma 10. For n ≥ 1, K_{E}(n) = K_{3}(n) + K_{E}(n − 1).

Proof. Let n ≥ 1. Every non-attacking king position on an extended 3 × n chessboard is in one of two cases: there is either no king or a king on the extended square of the chessboard. See Figure 9. Thus, K_{E}(n) = K_{3}(n) + K_{E}(n − 1).

Figure 9: The two cases for a non-attacking king position on an extended 3 × n chessboard, where n ≥ 1.

Lemma 11. For n ≥ 2, K_{3}(n) = K_{3}(n − 1) + 2 · K_{3}(n − 2) + 2 · K_{E}(n − 2).

Proof. Let n ≥ 2. Every non-attacking king position on a 3×n chessboard is in one of several cases: there is either no king, one king or two kings in the last column of the chessboard. See Figure 10. Thus, K_{3}(n) = K_{3}(n − 1) + 2 · K_{3}(n − 2) + 2 · K_{E}(n − 2).

Figure 10: The possible cases for a non-attacking king position on a 3 × n chessboard, where n ≥ 2.

The sequence K_{E}(n) appears as a subsequence of (\underline{A046672}) in [3]. See Table 6. There, we see the generating function

K_{E}(x) = \frac{1}{1 − 2x − 3x^{2} + 2x^{3}} = 1 + 2x + 7x^{2} + 18x^{3} + 53x^{4} + 146x^{5} + ⋯

Thus, the generating function for K_{E}(n) is

𝕂_{E}(x) = \frac{1}{x} · (\frac{1}{1 − 2x − 3x^{3} + 2x^{3}} − 1) = \frac{2 + 3x − 2x^{2}}{1 − 2x − 3x^{2} + 2x^{3}} = ∑_{n=0}^{∞} K_{E}(n)x^{n}.

\begin{matrix}n & K_{E}(n) \\ 0 & 2 \\ 1 & 7 \\ 2 & 18 \\ 3 & 53 \\ 4 & 146 \\ 5 & 415 \end{matrix}

Table 6: The number of non-attacking king positions on an extended 3×n chessboard, where n ≥ 0.

The sequence K_{3}(n) appears as a subsequence of (\underline{A054854}) in [3]. See Table 7.

\begin{matrix}n & K_{3}(n) \\ 0 & 1 \\ 1 & 5 \\ 2 & 11 \\ 3 & 35 \\ 4 & 93 \\ 5 & 269 \end{matrix}

Table 7: The number of non-attacking king positions on a 3 × n chessboard, where n ≥ 0.

There, we see the generating function

K_{3}(x) = \frac{1 − x}{1 − 2x − 3x^{2} + 2x^{3}} = 1 + x + 5x^{2} + 11x^{3} + 35x^{4} + 93x^{5} + ⋯

Thus, the generating function for K_{3}(n) is

𝕂_{3}(x) = \frac{1}{x} · (\frac{1 − x}{1 − 2x − 3x^{3} + 2x^{3}} − 1) = \frac{1 + 3x − 2x^{2}}{1 − 2x − 3x^{2} + 2x^{3}} = ∑_{n=0}^{∞} K_{3}(n)x^{n}.

Theorem 12. For n ≥ 0, the number of non-attacking king positions on a 3 × n chessboard is the coefficient of the x^{n}-th term in 𝕂_{3}(x).

3 Cylindrical chessboards

Let a cylindrical m×n chessboard be represented by identifying the left and right edges with each other. Hence, n is even. We assume that a black square is in the upper left-hand corner of the board and that the board is fixed in position and orientation. Let \overline{K}_{1}(n) denote the number of non-attacking king positions on a cylindrical 1×n chessboard. For the degenerate case (n = 0), we set \overline{K}_{1}(0) = 1.

Recall the Fibonacci sequence described by the recurrence relation: F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2}, for all n ≥ 2.

Lemma 13. For even n ≥ 2, \overline{K}_{1}(n) = F_{n−1} + F_{n+1}.

Proof. Let K_{1}(n) denote the number of non-attacking king positions on a regular 1 × n chessboard. For all n ≥ 1, it is known that K_{1}(n) = F_{n+2} [1, p. 510, Exercise 26]. Now, let n ≥ 2 and even. Every non-attacking king position on a cylindrical 1 × n chessboard is in one of two cases. See Figure 11. Thus,

\overline{K}_{1}(n) = K_{1}(n − 3) + K_{1}(n − 1)
= F_{n−3+2} + F_{n−1+2}
= F_{n−1} + F_{n+1}.

Figure 11: The possible cases for a non-attacking king position on a cylindrical 1 × n chessboard, where n ≥ 2 and even.

The sequence \overline{K}_{1}(n) is connected to (\underline{A219233}) in [3]. See Table 8. Let us find the generating function for \overline{K}_{1}(n), where n ≥ 0 is even. Mathematica 11 gives the generating function

F(x) = \frac{1 − x}{1 − 3x + x^{2}} = ∑_{k=0}^{∞} F_{2k+1}x^{k}.

\begin{matrix}n & \overline{K}_{1}(n) \\ 0 & 1 \\ 2 & 3 \\ 4 & 7 \\ 6 & 18 \\ 8 & 47 \\ 10 & 123 \end{matrix}

Table 8: The number of non-attacking king positions on a cylindrical 1×n chessboard, where n ≥ 0 and even.

Then,

F(x^{2}) = \frac{1 − x^{2}}{1 − 3x^{2} + x^{4}} = ∑_{k=0}^{∞} F_{2k+1}x^{2k}.

Also,

x^{2}F(x^{2}) = \frac{x^{2}(1 − x^{2})}{1 − 3x^{2} + x^{4}} = ∑_{k=0}^{∞} F_{2k+1}x^{2k+2}.

Thus,

\overline{𝕂}_{1}(x) = F(x^{2}) + x^{2}F(x^{2})
= ∑_{k=0}^{∞} F_{2k+1}x^{2k} + ∑_{k=0}^{∞} F_{2k+1}x^{2k+2}
= [F_{1}x^{0} + F_{3}x^{2} + F_{5}x^{4} + ⋯] + [F_{1}x^{2} + F_{3}x^{4} + F_{5}x^{6} + ⋯]
= ∑_{k=0}^{∞} \overline{K}_{1}(2k)x^{2k} = \frac{1 − x^{4}}{1 − 3x^{2} + x^{4}} .

Theorem 14. For even n ≥ 0, the number of non-attacking king positions on a cylindrical 1 × n chessboard is the coefficient of the x^{n}-th term in \overline{𝕂}_{1}(x).

For even n ≥ 0, let \overline{B}_{2}(n) denote the number of non-attacking bishop positions on a cylindrical 2 × n chessboard. For the degenerate case (n = 0), we set \overline{B}_{2}(0) = 1. Using the Cfinite Maple package [5], we calculate the Hadamard product \overline{𝕂}_{1}(x) ⊙ \overline{𝕂}_{1}(x). This gives the generating function for \overline{B}_{2}(n), namely

\overline{𝔹}_{2}(x) = \frac{1 + x^{2} − 15x^{4} + 3x^{6}}{1 − 8x^{2} + 8x^{4} − x^{6}} = ∑_{k=0}^{∞} \overline{B}_{2}(2k)x^{2k}.

Theorem 15. For even n ≥ 0, the number of non-attacking bishop positions on a cylindrical 2 × n chessboard is \overline{B}_{2}(n) = (F_{n−1} + F_{n+1})^{2}. The generating function for \overline{B}_{2}(n) is the Hadamard product \overline{𝔹}_{2}(x) = \overline{𝕂}_{1}(x) ⊙ \overline{𝕂}_{1}(x).

Proof. The configuration of the black squares is completely symmetric to the configuration of the white squares. Bishops on white squares cannot attack bishops on black squares. The result follows immediately from Lemma 13.

\begin{matrix}n & \overline{B}_{2}(n) \\ 0 & 1 \\ 2 & 9 \\ 4 & 49 \\ 6 & 324 \\ 8 & 2209 \\ 10 & 15129 \end{matrix}

Table 9: The number of non-attacking bishop positions on a cylindrical 2 × n chessboard, where n ≥ 0 and even.

We note that the sequence \overline{B}_{2}(n) does not appear in [3]. See Table 9.

Let \overline{B}_{3}(n) denote the number of non-attacking bishop positions on a cylindrical 3 × n chessboard, for even n ≥ 2. We set \overline{B}_{3}(0) = 1. For odd n ≥ 3, a doubly truncated 3 × n chessboard has missing black squares in the lower lefthand and lower righthand corners of the board. Let b_{DT} (n), for odd n ≥ 3, denote the number of non-attacking bishop positions on the black squares of a doubly truncated 3 × n chessboard. In the degenerate case where n = 1, we set b_{DT} (1) = b_{T} (1) = 2.

Lemma 16. For odd n ≥ 3, b_{DT} (n) = w_{T} (n − 1) + b_{DT} (n − 2).

Proof. Let n ≥ 3 and odd. Any non-attacking bishop position on the black squares of a doubly truncated 3 × n chessboard is in one of two cases: there is either no bishop or a bishop in the last column of the chessboard. See Figure 12. Thus, b_{DT} (n) = w_{T} (n − 1) + b_{DT} (n − 2).

The sequence b_{DT} (n) does not appear in [3]. See Table 10. From Lemma 16, we see that b_{DT} (n) = 2+w_{T} (2)+w_{T} (4)+⋯+w_{T} (n−1), for odd n ≥ 3. Using this, along with W_{T} (x^{2}), we obtain the generating function for b_{DT} (n), namely Figure 12: The possible cases for a non-attacking bishop position on the black squares of a doubly truncated 3 × n chessboard, where n ≥ 3 and odd.

\begin{matrix}n & b_{DT} (n) \\ 1 & 2 \\ 3 & 5 \\ 5 & 15 \\ 7 & 47 \\ 9 & 150 \\ 11 & 481 \end{matrix}

Table 10: The number of non-attacking bishop positions on the black squares of a doubly truncated 3 × n chessboard, where n ≥ 1 and odd.

B_{DT} (x) = x (\frac{W_{T} (x^{2})}{1 − x^{2}} + \frac{1}{1 − x^{2}} − 2) + 2x
= \frac{−2x + 3x^{3} + x^{5} − x^{7}}{−1 + 4x^{2} − 2x^{4} − 2x^{6} + x^{8}} = ∑_{k=0}^{∞} b_{DT} (2k + 1)x^{2k+1}.

For even n ≥ 2, let \overline{b}_{3}(n) denote the number of non-attacking bishop positions on the black squares of a cylindrical 3 × n chessboard. We set \overline{b}_{3}(0) = 1. Note that \overline{b}_{3}(2) = 1 (zero bishops) + 3 (one bishop) = 4. For \overline{b}_{3}(4), there are two cases to examine. There is either no bishop or a bishop on the black square in the “last” column of a cylindrical 3 × 4 board. See Figure 13. Thus, \overline{b}_{3}(4) = b(2) + 2 + 2 + 1 (no bishop) + 2 (one bishop) = 12.

Lemma 17. For even n ≥ 6, \overline{b}_{3}(n) = b(n − 2) + w(n − 3) + w(n − 5) + 2 · b_{DT} (n − 3).

Proof. Let n ≥ 6 and even. Any non-attacking bishop position on the black squares of a cylindrical 3 × n chessboard is in one of two cases: there is either no bishop or a bishop in the “last” column of the chessboard. See Figure 14. Thus, \overline{b}_{3}(n) = b(n − 2) + w(n − 3) + w(n − 5) + 2 · b_{DT} (n − 3).

Figure 13: The possible cases for a non-attacking bishop position on the black squares of a cylindrical 3 × 4 chessboard.

The sequence \overline{b}_{3}(n) does not appear in [3]. See Table 11. Using Lemma 17, along with G(x), J (x) and B_{DT} (x), we obtain the generating function for \overline{b}_{3}(n), namely

\overline{b}_{3}(x) = x^{2}G(x^{2}) + x^{3} · xJ (x^{2}) + x^{5} · xJ (x^{2}) + 2x^{3}B_{DT} (x) + x^{4} + 3x^{2} + 1
= \frac{−1 + 2x^{4} + 4x^{6} − 3x^{8}}{−1 + 4x^{2} − 2x^{4} − 2x^{6} + x^{8}} = ∑_{k=0}^{∞} \overline{b}_{3}(2k)x^{2k}.

Using the Cfinite Maple package [5], we calculate the Hadamard product \overline{b}_{3}(x) ⊙ \overline{b}_{3}(x). This gives the generating function for \overline{B}_{3}(n), namely

\overline{𝔹}_{3}(x) =

\frac{−1 − 2x^{2} + 45x^{4} + 252x^{6} − 1090x^{8} + 644x^{10} + 802x^{12} − 740x^{14} + 35x^{16} + 86x^{18} − 15x^{20}}{−1 + 14x^{2} − 35x^{4} − 48x^{6} + 198x^{8} − 112x^{10} − 78x^{12} + 72x^{14} − 5x^{16} − 6x^{18} + x^{20}} .

Theorem 18. For even n ≥ 0, the number of non-attacking bishop positions on a cylindrical 3 × n chessboard is \overline{B}_{3}(n) = (\overline{b}_{3}(n))^{2}. The generating function for \overline{B}_{3}(n) is the Hadamard product \overline{𝔹}_{3}(x) = \overline{b}_{3}(x) ⊙ \overline{b}_{3}(x).

Figure 14: The possible cases for a non-attacking bishop position on the black squares of a cylindrical 3 × n chessboard, where n ≥ 6 and even.

Proof. The configuration of the black squares is completely symmetric to the configuration of the white squares. Bishops on white squares cannot attack bishops on black squares.

We note that the sequence \overline{B}_{3}(n) does not appear in [3]. See Table 12.

For even n ≥ 2, let \overline{K}_{2}(n) denote the number of non-attacking king positions on a cylindrical 2 × n chessboard. For the degenerate case (n = 0), we set \overline{K}_{2}(0) = 1. Clearly, \overline{K}_{2}(2) = 5.

Lemma 19. For even n ≥ 4, \overline{K}_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 3).

Proof. Let n ≥ 4 and even. Any non-attacking king position on a cylindrical 2×n chessboard is in one of two cases: there is either no king or a king in the “last” column of the chessboard. See Figure 15. Thus, \overline{K}_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 3).

The sequence \overline{K}_{2}(n) is a subsequence of (\underline{A092896}) in [3]. See Table 13.

Theorem 20. For even n ≥ 0, the number of non-attacking king positions on a cylindrical 2 × n chessboard is \overline{K}_{2}(n) = 2^{n} + 1.

Proof. Using Lemma 19 and Theorem 9, we see that

\begin{matrix}n & \overline{b}_{3}(n) \\ 0 & 1 \\ 2 & 4 \\ 4 & 12 \\ 6 & 34 \\ 8 & 108 \\ 10 & 344 \end{matrix}

Table 11: The number of non-attacking bishop positions on the black squares of a cylindrical 3 × n chessboard, where n ≥ 0 and even.

\begin{matrix}n & \overline{B}_{3}(n) \\ 0 & 1 \\ 2 & 16 \\ 4 & 144 \\ 6 & 1156 \\ 8 & 11664 \\ 10 & 118336 \end{matrix}

Table 12: The number of non-attacking bishop positions on a cylindrical 3 × n chessboard, where n ≥ 0 and even.

\overline{K}_{2}(n) = K_{2}(n − 1) + 2 · K_{2}(n − 3)

= \frac{1}{3}(2^{n−1+2} − (−1)^{n−1}) + 2(\frac{1}{3}(2^{n−3+2} − (−1)^{n−3}))

= \frac{1}{3} · 2^{n+1} − \frac{1}{3}(−1)^{n−1} + \frac{2}{3} · 2^{n−1} − \frac{2}{3}(−1)^{n−3}

= \frac{2}{3} · 2^{n} + \frac{1}{3} · 2^{n} − \frac{1}{3}(−1)^{n−1} − \frac{2}{3}(−1)^{n−3}

= 2^{n} + \frac{1}{3}(−1)^{n} + \frac{2}{3}(−1)^{n}

= 2^{n} + (−1)^{n} = 2^{n} + 1,

since n ≥ 2 is even.

For n ≥ 1, a doubly extended 3 × n chessboard has an extra square attached (in the Figure 15: The possible cases for a non-attacking king position on a cylindrical 2 × n chessboard, where n ≥ 4 and even.

\begin{matrix}n & \overline{K}_{2}(n) \\ 0 & 1 \\ 2 & 5 \\ 4 & 17 \\ 6 & 65 \\ 8 & 257 \\ 10 & 1025 \end{matrix}

Table 13: The number of non-attacking king positions on a cylindrical 2 × n chessboard, where n ≥ 0 and even.

horizontal direction) to the lower lefthand and righthand corners of the board. Let K_{DE}(n) denote the number of non-attacking king positions on a doubly extended 3 × n chessboard. We set K_{DE}(0) = 3, since a doubly extended 3 × 0 chessboard can be viewed as a regular 1 × 2 chessboard. Observe that K_{DE}(1) = 1 (zero kings) + 5 (one king) + 4 (two kings) + 1 (three kings) = 11. See Figure 16.

For even n ≥ 2, let \overline{K}_{3}(n) denote the number of non-attacking king positions on a cylindrical 3 × n chessboard. We set \overline{K}_{3}(0) = 1. Observe that \overline{K}_{3}(2) = 1 (zero kings) + 6 (one king) + 4 (two kings) = 11. See Figure 17.

Lemma 21. For n ≥ 2, K_{DE}(n) = K_{3}(n) + 2 · K_{E}(n − 1) + K_{DE}(n − 2).

Proof. Let n ≥ 2. Any non-attacking king position on a doubly extended 3×n chessboard is in one of several cases: there is either no king, one king or two kings on the extended squares of the chessboard. See Figure 18. Thus, K_{DE}(n) = K_{3}(n) + 2 · K_{E}(n − 1) + K_{DE}(n − 2).

The sequence K_{DE}(n) does not appear in [3]. See Table 14. Using Lemma 21 (and generating functions 𝕂_{3}(x) and 𝕂_{E}(x)), let us find the generating function for K_{DE}(n).

Figure 16: Non-attacking positions with two or three kings on a doubly extended 3 × 1 chessboard.

Figure 17: Non-attacking positions with two kings on a cylindrical 3 × 2 chessboard.

𝕂_{DE}(x) = ∑_{n=0}^{∞} K_{DE}(n)x^{n} = 3 + 11x + ∑_{n=2}^{∞} K_{DE}(n)x^{n}

= 3 + 11x + ∑_{n=2}^{∞}(K_{3}(n) + 2 · K_{E}(n − 1))x^{n} + ∑_{n=2}^{∞} K_{DE}(n − 2)x^{n}

= 3 + 11x + ∑_{n=2}^{∞}(K_{3}(n) + 2 · K_{E}(n − 1))x^{n} + ∑_{j=0}^{∞} K_{DE}(j)x^{j+2}

= 3 + 11x + ∑_{n=2}^{∞}(K_{3}(n) + 2 · K_{E}(n − 1))x^{n} + x^{2} · 𝕂_{DE}(x).

Solving for 𝕂_{DE}(x) yields

𝕂_{DE}(x) = \frac{1}{1 − x^{2}} · (3 + 11x + ∑_{n=2}^{∞}(K_{3}(n) + 2 · K_{E}(n − 1))x^{n}) .

Figure 18: The possible cases for a non-attacking king position on a doubly extended 3 × n chessboard, where n ≥ 2.

\begin{matrix}n & K_{DE}(n) \\ 0 & 3 \\ 1 & 11 \\ 2 & 28 \\ 3 & 82 \\ 4 & 227 \\ 5 & 643 \end{matrix}

Table 14: The number of non-attacking king positions on a doubly extended 3×n chessboard, where n ≥ 0.

Hence,

𝕂_{DE}(x) = \frac{1}{1 − x^{2}} · (3 + 11x + (𝕂_{3}(x) − 1 − 5x) + 2(x · 𝕂_{E}(x) − 2x))

= \frac{−3 − 8x − 2x^{2} + 4x^{3}}{−1 + x + 5x^{2} + x^{3} − 2x^{4}} = ∑_{n=0}^{∞} K_{DE}(n)x^{n}.

Lemma 22. For even n ≥ 4, \overline{K}_{3}(n) = K_{3}(n − 1) + 2 · K_{3}(n − 3) + 2 · K_{DE}(n − 3).

Proof. Let n ≥ 4 and even. Any non-attacking king position on a cylindrical 3×n chessboard is in one of several cases: there is either no king, one king or two kings in the “last” column of the chessboard. See Figure 19. Thus, \overline{K}_{3}(n) = K_{3}(n−1)+2·K_{3}(n−3)+2·K_{DE}(n−3).

The sequence \overline{K}_{3}(n) does not appear in [3]. See Table 15. Using Lemma 22 (and generating functions 𝕂_{3}(x) and 𝕂_{DE}(x)), let us find the generating function for \overline{K}_{3}(n).

Figure 19: The possible cases for a non-attacking king position on a cylindrical 3 × n chessboard, where n ≥ 4 and even.

\overline{𝕂}_{3}(x) = x · (𝕂_{3}(x) ⊙ \frac{x}{1 − x^{2}} ) + 2x^{3} · (𝕂_{3}(x) ⊙ \frac{x}{1 − x^{2}} ) +

2x^{3} · (𝕂_{DE}(x) ⊙ \frac{x}{1 − x^{2}} ) + 6x^{2} + 1.

Using the Cfinite Maple package [5], we see that

\overline{𝕂}_{3}(x) = \frac{1 − 27x^{4} + 42x^{6} − 12x^{8}}{1 − 11x^{2} + 27x^{4} − 21x^{6} + 4x^{8}} = ∑_{k=0}^{∞} \overline{K}_{3}(2k)x^{2k}.

Theorem 23. For even n ≥ 0, the number of non-attacking king positions on a cylindrical 3 × n chessboard is the coefficient of the x^{n}-th term in \overline{𝕂}_{3}(x).

4 Concluding remarks

The On-line Encyclopedia of Integer Sequences [3] is an invaluable resource for mathematicians working in the areas of discrete mathematics and combinatorics. During our research project, we encountered various sequences which we checked in [3], hoping to gain further insight into our combinatorics problem. Some of these sequences did not appear within [3].

\begin{matrix}n & \overline{K}_{3}(n) \\ 0 & 1 \\ 2 & 11 \\ 4 & 67 \\ 6 & 503 \\ 8 & 3939 \\ 10 & 31111 \end{matrix}

Table 15: The number of non-attacking king positions on a cylindrical 3 × n chessboard, where n ≥ 0 and even.

The sequences B_{3}(n), \overline{B}_{2}(n), \overline{B}_{3}(n) and \overline{K}_{3}(n), along with contextual information, recurrence relations and generating functions, have been submitted for entry into this dynamic database of integer sequences.

For additional information on non-attacking chess pieces and other variants, the interested reader is directed to [2].

5 Acknowledgments

The authors thank Stephen C. Locke for his thought-provoking conversations during the course of this research project. We are also grateful to the anonymous referee for his/her valuable comments and suggestions.

References

[1] R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition, Addison-Wesley, 2004.

[2] V. Kotěšovec, Non-attacking Chess Pieces, 6th Edition (digital document). Available at

   http://www.kotesovec.cz

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically

   at http://oeis.org, 2017.

[4] G. E. Stevens, The bishop’s tale: a combinatorial proof of F_{n}^{2} = 2(F_{n−1}^{2} + F_{n−2}^{2}) − F_{n−3}^{2}, Fibonacci Quart. 45 (2007), 319–321.

[5] D. Zeilberger, The C-finite ansatz, Ramanujan J. 31 (2013), 23–32.

2010 Mathematics Subject Classification: Primary 05A19. Keywords: non-attacking bishop, non-attacking king, chess.

(Concerned with sequences \underline{A001045}, \underline{A030186}, \underline{A033505}, \underline{A046672}, \underline{A054854}, \underline{A092896}, and \underline{A219233}.)

Received February 5 2017; revised version received May 22 2017. Published in Journal of Integer Sequences, June 25 2017.

Return to Journal of Integer Sequences home page.