Math Tutoring Service

See my Mathematics Tutoring Service on Thumbtack

Tri-Color chessboards

When coloring a checkerboard, the basic requirement is that squares that are full-neighbors (horizontally or vertically) have different colors. Clearly, there are exactly two ways of coloring an n x n checkerboard with two colors (black and red, say). Once a color has been selected for the lower left corner, all remaining square colors are forced. I wondered how many different ways one could color an n x n checkerboard with three colors. This led me to consider two problems:

(1) How many ways are there to color an n x n checkerboard, using at most 3 colors?

(2) How many ways are there to color a 3k x 3k checkerboard, using equal numbers of red, blue, and white squares?

Bridget Tenner of dePaul University immediately came up with the answer to problem (1) by searching in Neal Sloane's wonderful Online Encyclopedia of Integer Sequences, using "3-color" as a search string. The answer is given here as a special case of A078099 (for m x n checkerboards), which is defined recursively. The sequence grows very quickly: it is 3 times a sequence beginning 1, 6, 82, 2604, 193662, 33865632, 13956665236.

A sequence to answer question (2) does not seem to appear in OEIS, so this may be an open question.

No comments: