Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
In selecting a title, a) try to be specific and avoid general subjects like "combinatorics" that are covered by the tags, and b) avoid subjective assessments like "very complex problem", which may or may not coincide with how the problem is perceived by others. –  joriki Dec 6 '11 at 11:04
    
NB An alternative formulation is that you want to count the strings in the language $b\{b, w\}^{10}b$ which don't contain $bbb$ or $www$ as a substring. –  Peter Taylor Dec 6 '11 at 11:18
    
If you have an inventory consisting of 25,000 items and the nature of the products requires 6 spaces and 6 bars (not including the first and last) to characterize the product, then do we have any concern in the number of possible combinations falling short of the 25,000 items. Or does the bar code need more bars and spaces to cover more items –  user22980 Jan 15 '12 at 16:26
add comment

1 Answer

up vote 5 down vote accepted

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\;.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.