MathDB

Let

n \geq 3

be a positive integer. A chipped

n

-board is a

2 \times n

checkerboard with the bottom left square removed. Lino wants to tile a chipped

n

-board and is allowed to use the following types of tiles:

[*] Type 1: any

1 \times k

board where

1 \leq k \leq n

[*] Type 2: any chipped

k

-board where

1 \leq k \leq n

that must cover the left-most tile of the

2 \times n

checkerboard.

Two tilings

T_1

and

T_2

are considered the same if there is a set of consecutive Type 1 tiles in both rows of

T_1

that can be vertically swapped to obtain the tiling

T_2

. For example, the following three tilings of a chipped

7

-board are the same:
http://i.imgur.com/8QaSgc0.png
For any positive integer

n

and any positive integer

1 \leq m \leq 2n - 1

, let

c_{m,n}

be the number of distinct tilings of a chipped

n

-board using exactly

m

tiles (any combination of tile types may be used), and define the polynomial

P_n(x) = \sum^{2n-1}_{m=1} c_{m,n}x^m.

Find, with justification, polynomials

f(x)

and

g(x)

such that

P_n(x) = f(x)P_{n-1}(x) + g(x)P_{n-2}(x)

for all

n \geq 3

Problem Statement