Fibonacci and Catalan Numbers: An Introduction

Chapter 8

Chess Pieces on Chessboards

This time we want to use our chessboards to study how to place certain types of chess pieces in prescribed ways.

Example 8.1: In the game of chess, a king can move (when positioned on a standard 8 × 8 chessboard) one space to the left or right, or one space north or south, or one space in one of the four diagonal directions: northeast, southeast, northwest, or southwest. If an opponent has a chess piece in any of these (possibly) eight neighboring positions, then the king can take that piece.

Here we shall restrict ourselves to a 1 × n chessboard where n is a positive integer. Our objective is to count the number of ways one can place nontaking kings on such a chessboard. For example, in the case of n = 5, we can label the squares of the chessboard from 1 to 5, as shown in Fig. 8.1(a). In Fig. 8.1(b), we find four of the ways we can place nontaking kings on this chessboard. By simply listing the labels of the squares where we can place the nontaking kings, we find the following possibilities:

Figure 8.1

So there are 13(= F₇) ways in which we can place nontaking kings on a 1 × 5 41 chessboard. If we let k_n count the number of ways we can do this for a 1 × n chessboard, we could derive the recurrence relation for k_n as we did earlier in many ...