Problem
COM-B1-M10-P020 Tiles of Length \(1\), \(2\), \(3\)
#20
★★★☆☆ Level 3 of 5
In how many ways can a \(1\times8\) strip be tiled by tiles of length \(1\), \(2\), and \(3\)?
This is the same recurrence as compositions with parts \(1,2,3\).
Let \(a_n\) be the number of tilings. The last tile has length \(1\), \(2\), or \(3\), so \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). With \(a_0=1\), \(a_1=1\), \(a_2=2\), we get \(a_8=81\).
Connection between tilings and compositions.