Problem
COM-B1-M10-P011 Strip of \(9\) Cells
#11
★★☆☆☆ Level 2 of 5
In how many ways can a \(1\times9\) strip be tiled by \(1\times1\) and \(1\times2\) tiles?
The last tile has length \(1\) or \(2\).
Let \(a_n\) be the number of tilings. Then \(a_n=a_{n-1}+a_{n-2}\), with \(a_0=1\), \(a_1=1\). We get \(a_9=55\).
Same idea in one dimension.