20. A barcode of the type shown in the two examples is composed of alternate strips of black and white, where the leftmost and rightmost strips are always black. Each strip (of either colour) has a width of 1 or 2 . The total width of the barcode is 12 . The barcodes are always read from left to right. How many distinct barcodes are possible?
20. 116 Any code will start with a black strip and a white strip followed by a shorter barcode. Let $C(m)$ be the number of distinct barcodes of width $m$.
Those codes which start with BW will be followed by a code of width $m-2$; so there will be $C(m-2)$ of these. Likewise, there will be $C(m-3)$ codes starting BBW, the same number starting BWW, and $C(m-4)$ starting BBWW; and that exhausts the possibilites. So it follows that $C(m)=C(m-2)+2 C(m-3)+C(m-4)$.
When $m \leqslant 4$, it is simple to list all possible barcodes; namely B, BB, BWB and BBWB, BWBB, BWWB. Therefore $C(1)=C(2)=C(3)=1$ and $C(4)=3$. We can now calculate $C(m)$ for $m>4$.
Thus $C(5)=C(3)+2 C(2)+C(1)=1+2+1=4$, and continuing like this, we get $C(6)=6, C(7)=11, C(8)=17, C(9)=27, C(10)=45, C(11)=72$, $C(12)=116$.