How many barcodes are there?

A barcode is made of white and black lines. A barcode always begins and ends width a black line. Each line has is of thickness 1 or 2, and the whole barcode is of thickness 12.

How many different barcodes are there (we read a barcode from left to right).

I know that I'm required to show some effort, yet I really don't have a clue about this problem. Can you give me any hints?

Solution 1:

Denote by $b_i$ the number of bars (black or white) of width $i\in\{1,2\}$. Then $b_1+2b_2=12$, hence $b_1$ is even. Since the total number of bars $b_1+b_2$ is odd it follows that $b_2$ is odd. This leaves the cases $$(b_1,b_2)\in\bigl\{(10,1),(6,3),(2,5)\bigr\}\ .$$ The total number of admissible arrangements then comes to $${11\choose 1}+{9\choose 3}+{7\choose 2}=116\ .$$

Solution 2:

Lets create an additional variable $k > 6$ denoting the number of bars. It is necessarily an odd number, as black and white bars must alternate. It is larger that $6$ because of your condition on thickness of bars to be $\le 2$.

Having this number, we can calculate the total number of barcodes with $k$ bars.

Let each of this bars has thickness $1$. Then we have $12- k$ additional places for an increasing of thickness of any of the existing bars. So, we can choose $12 - k$ bars and enlarge them. We can do this by $C_{k}^{12-k}$ variants, so the answer will be

$$\sum_{k=7,9,11}C_{k}^{12-k}$$

Solution 3:

Here is variant with some combinatorial algebra.

• We encode the thickness $1$ and $2$ of the black lines as $x^1+x^2$, the exponent indicating the thickness, the $+$ indicating the alternatives.

• We do the same for the white lines and get $y^1+y^2$.

The length of a barcode starting and ending with black lines can therefore be encoded as \begin{align*} (x+x^2)(y+y^2)(x+x^2)\cdots (x+x^2)\tag{1} \end{align*}

Note that beginning and end of this expression is $x+x^2$ since we start and end a barcode with black lines.

A barcode with $k$ white lines has necessarily $k+1$ black lines and is encoded as expression \begin{align*} (x+x^2)^{k+1}(y+y^2)^{k}\tag{2} \end{align*}

We are not interested in differentiating black and white lines. So, we count them all using one variable $z$ and obtain instead of (2) \begin{align*} (z+z^2)^{2k+1}\tag{3} \end{align*}

Since a barcode may consist of one or more black lines and we are interested in barcodes of length $12$ we add up all expressions of the form (3) and select the coefficient of $z^{12}$.

We use the notation $[z^n]$ to denote the coefficient of $z^n$ in a series.

We obtain this way \begin{align*} [z^{12}]\sum_{k\geq 0}(z+z^2)^{2k+1} &=[z^{12}]\sum_{k\geq 0}z^{2k+1}(1+z)^{2k+1}\tag{4}\\ &=\sum_{k=0}^{5}[z^{11-2k}](1+z)^{2k+1}\tag{5}\\ &=\sum_{k=3}^5\binom{2k+1}{11-2k}\tag{6}\\ &=\binom{7}{5}+\binom{9}{3}+\binom{11}{1}\\ &=116 \end{align*}

Comment:

• In (4) we factor out $z^{2k+1}$.

• In (5) we use the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$ and restrict the sum with upper limit $k=5$, since the exponent $11-2k$ is non-negative.

• In (6) we select the coefficient of $z^{2k-1}$ and start with index $k=3$ since the other binomial coefficients with $k<3$ are zero.