Problem

Source: Canada Repêchage 2016/8

Tags: combinatorics, algebra, polynomial, generating functions, recursion, function



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: 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$.