13
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ By this way there are many cases. Because we don't have any fix width of white and black lines. $\endgroup$ – Amar Mar 11 '17 at 13:07
  • 1
    $\begingroup$ The question boils down to finding the number of odd sums made entirely out of $1$ and $2$, whose result is $12$. $\endgroup$ – b00n heT Mar 11 '17 at 13:15
10
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
7
$\begingroup$

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}$$

| cite | improve this answer | | | | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
4
$\begingroup$

Let $1$ denote a black line & $0$ denote a white line. A barcode is then a sequence of $1$'s & $0$'s that starts & ends with $1$ and avoids $000$ &$111$. So your problem is to find the number of binary words of length $12$ that start and end with $1$ and avoid $000$ & $111$.

Let $a_n$ denote the number of binary words that start with $1$ and end $11$ (& satisfy the $000$, $111$ condition). Let $A(x)$ denote the generating function for $a_n$. Define B(x) similarly to $A$ to end $01$. Define C(x) similarly to $A$ to end $00$.Define D(x) similarly to $A$ to end $10$. These functions are related by the following recurrence relations. \begin{eqnarray*} A=x^2+xB \\ B=x(C+D) \\ C=xD \\ D=x^2+x(A+B) \end{eqnarray*} Now solve these and find the coefficients $x^{12}$ in $A$ & $B$. Add these value.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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