Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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\ .$$
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}$$
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.
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.
