Counting barcodes

Question

This certain problem is related to different combinations of strips in a barcode.

The question is that how many different codes are possible in a barcode, reading from left to right, according to these rules:

• barcode should be composed of alternate strips of black and white
• barcode should always be beginning and ending with a black strip
• each strip (of either colour) has the width 1 or 2
• the total width of the barcode is 12

For example, this barcode is one of the many which conform to the rules.

---

I approached this problem by representing the four different strips by

• b1 (black of width 1)
• b2 (black of width 2)
• w1 (white of width 1)
• w2 (white of width 2)

Then all codes would have this pattern

• b1 ...... b1 (width so far: 2)
• b2 ...... b2 (width so far: 4)
• b1 ...... b2 (width so far: 3)
• b2 ...... b1 (width so far: 3)

since they always begin and end with black.

Next step was the 2nd and 2nd last strips of white color.

Again the pattern would be:

• w1 ...... w1 (width so far: 4)
• w2 ...... w2 (width so far: 8)
• w1 ...... w2 (width so far: 6)
• w2 ...... w1 (width so far: 6)

with all the four patterns of black mentioned above.

This seemed to get automated but the width was hinderance in deriving a formula. Then the question is that should all of this be done manually or does MATH offer a solution?

Answer 1

You can have anywhere from $4$ to $6$ black strips: With $3$ there would be only $5$ strips in total, so the total width would be less than $12$, and with $7$ there would be $13$ strips in total, so the total width would be greater than $12$.

So you just need to add the numbers for these three cases. With $n$ black strips, there are $n-1$ white strips, for a total of $2n-1$ strips, so $12-(2n-1)=13-2n$ of them are $2$s and the others are $1$s. You can choose the $2$s arbitrarily, so the total number of possibilities is

$$\sum_{n=4}^6\binom{2n-1}{13-2n}=\binom{7}{5}+\binom{9}{3}+\binom{11}{1}=21+84+11=116\;.$$