Find the number of ways to pave a 1x7 rectangle by 1x1, 1x2, 1x3 blocks, assuming that blocks of the same size are indistinguishable.
My Attempts:
I tackled the problem in this way. I thought about the number of ways to partition the number 7 into 1's, 2's and 3's. But manually counting all of them and then permuting was turning out to be tedious. So is there a quicker more systematic way?
Let $a_n$ be the number of ways of paving a $1\times n$ rectangle with $1\times1$, $1\times2$, and $1\times3$ blocks. Then $a_0=1$, $a_1=1$, $a_2=2$, and $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ for $n\ge3$. This recurrence makes it easy to find $a_4,a_5,a_6$ and then $a_7$.