MathDB

8

Part of 2016 Canadian Mathematical Olympiad Qualification

Problems(1)

Tiling chipped boards, generating functions, and recursion

Source: Canada Repêchage 2016/8

6/19/2016
Let n≥3n \geq 3 be a positive integer. A chipped nn-board is a 2×n2 \times n checkerboard with the bottom left square removed. Lino wants to tile a chipped nn-board and is allowed to use the following types of tiles:

[*] Type 1: any 1×k1 \times k board where 1≤k≤n1 \leq k \leq n
[*] Type 2: any chipped kk-board where 1≤k≤n1 \leq k \leq n that must cover the left-most tile of the 2×n2 \times n checkerboard.

Two tilings T1T_1 and T2T_2 are considered the same if there is a set of consecutive Type 1 tiles in both rows of T1T_1 that can be vertically swapped to obtain the tiling T2T_2. For example, the following three tilings of a chipped 77-board are the same:
http://i.imgur.com/8QaSgc0.png
For any positive integer nn and any positive integer 1≤m≤2n−11 \leq m \leq 2n - 1, let cm,nc_{m,n} be the number of distinct tilings of a chipped nn-board using exactly mm tiles (any combination of tile types may be used), and define the polynomial Pn(x)=∑m=12n−1cm,nxm.P_n(x) = \sum^{2n-1}_{m=1} c_{m,n}x^m.
Find, with justification, polynomials f(x)f(x) and g(x)g(x) such that Pn(x)=f(x)Pn−1(x)+g(x)Pn−2(x)P_n(x) = f(x)P_{n-1}(x) + g(x)P_{n-2}(x) for all n≥3n \geq 3.
combinatoricsalgebrapolynomialgenerating functionsrecursionfunction