Problem
COM-B1-M10-P021 Squares and Dominoes
#21
★★★★☆ Level 4 of 5
A \(2\times6\) board is tiled by vertical dominoes, pairs of horizontal dominoes, and \(2\times2\) squares. How many tilings are possible?
The last block has width \(1\) or \(2\); a width \(2\) block has two types.
Let \(a_n\) be the number of tilings of \(2\times n\). The last column may be a vertical domino: \(a_{n-1}\). The last two columns may be two horizontal dominoes or one \(2\times2\) square: \(2a_{n-2}\). Hence \(a_n=a_{n-1}+2a_{n-2}\), \(a_0=1\), \(a_1=1\). Thus \(a_2=3\), \(a_3=5\), \(a_4=11\), \(a_5=21\), \(a_6=43\).
First place where a recurrence coefficient is not \(1\).