PUMaC 2011 · 组合（A 组） · 第 2 题

PUMaC 2011 — Combinatorics (Division A) — Problem 2

[ 3 ] A set of n dominoes, each colored with one white square and one black square, is used to cover a 2 × n board of squares. For n = 6, how many different patterns of colors can the board have? (For n = 2, this number is 6.)

解析

Let c denote the number of such colorings. If the rightmost column of two squares have the n same color (2 ways), then those two squares cannot be occupied by the same domino, so each must be covered by a horizontal domino. Then, the previous column must be two squares of the opposite color, and the rest of the 2 × ( n − 2) board can be colored in c ways. If n − 2 they have two different colors (2 ways), then one can suppose that the rightmost column is covered by a vertical domino, so that the rest of the 2 × ( n − 1) board can be colored in c n − 1 ways: this is only because if the rightmost column is covered by two horizontal dominos, then we can rotate those two dominos and result in a configuration where the rightmost column is covered by a vertical domino, and we still have the same coloring. Hence we have the recursion c = 2 c + 2 c with c = 2 , c = 6, and we compute that c = 328 . n n − 1 n − 2 1 2 6 Challenge: What if instead we have an infinite supply of two types of dominoes, one of which has one white square and one black square, and the other which has two black squares?