O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

img

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required