15. How many sequences of $0 \mathrm{~s}$ and $1 \mathrm{~s}$ are there of length 10 such that there are no three 0s or 1 s consecutively anywhere in the sequence?
Solution: We can have blocks of either 1 or $20 \mathrm{~s}$ and $1 \mathrm{~s}$, and these blocks must be alternating between 0s and 1s. The number of ways of arranging blocks to form a sequence of length $n$ is the same as the number of omino tilings of a 1-by- $n$ rectangle, and we may start each sequence with a 0 or a 1 , making $2 F_{n}$ or, in this case, 178 sequences.