¿Cuántos códigos de barras hay?

Question

Un código de barras está formado por líneas blancas y negras. Un código de barras siempre empieza y termina con una línea negra. Cada línea tiene un grosor de 1 ó 2, y todo el código de barras tiene un grosor de 12.

Cuántos códigos de barras diferentes hay (leemos un código de barras de izquierda a derecha).

Sé que se me exige un esfuerzo, pero realmente no tengo ni idea de este problema. ¿Pueden darme alguna pista?

Answer 1

Denota por $b_i$ el número de barras (negras o blancas) de ancho $i\in\{1,2\}$ . Entonces $b_1+2b_2=12$ Por lo tanto $b_1$ está en paz. Como el número total de barras $b_1+b_2$ es impar se deduce que $b_2$ es impar. Esto deja los casos $$(b_1,b_2)\in\bigl\{(10,1),(6,3),(2,5)\bigr\}\ .$$ El número total de arreglos admisibles asciende entonces a $${11\choose 1}+{9\choose 3}+{7\choose 2}=116\ .$$

Answer 2

Vamos a crear una variable adicional $k > 6$ que denota el número de barras. Es necesariamente un número impar, ya que las barras blancas y negras deben alternarse. Es mayor que $6$ debido a su condición de grosor de las barras a ser $\le 2$ .

Teniendo este número, podemos calcular el número total de códigos de barras con $k$ bares.

Que cada una de estas barras tenga un grosor $1$ . Entonces tenemos $12- k$ plazas adicionales para un aumento del grosor de cualquiera de las barras existentes. Así, podemos elegir $12 - k$ barras y ampliarlas. Podemos hacerlo de la siguiente manera $C_{k}^{12-k}$ variantes, por lo que la respuesta será

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

Answer 3

Aquí hay una variante con algo de álgebra combinatoria.

• Codificamos el grosor $1$ y $2$ de las líneas negras como $x^1+x^2$ el exponente que indica el espesor, el $+$ indicando las alternativas.

• Hacemos lo mismo con las líneas blancas y obtenemos $y^1+y^2$ .

Por lo tanto, la longitud de un código de barras que comienza y termina con líneas negras puede codificarse como \begin{align*} (x+x^2)(y+y^2)(x+x^2)\cdots (x+x^2)\tag{1} \end{align*}

Tenga en cuenta que el principio y el final de esta expresión es $x+x^2$ ya que empezamos y terminamos un código de barras con líneas negras.

Un código de barras con $k$ líneas blancas tiene necesariamente $k+1$ líneas negras y se codifica como expresión \begin{align*} (x+x^2)^{k+1}(y+y^2)^{k}\tag{2} \end{align*}

No nos interesa diferenciar las líneas blancas y negras. Por lo tanto, las contamos todas utilizando una sola variable $z$ y obtener en lugar de (2) \begin{align*} (z+z^2)^{2k+1}\tag{3} \end{align*}

Dado que un código de barras puede estar formado por una o varias líneas negras y que nos interesan los códigos de barras de longitud $12$ sumamos todas las expresiones de la forma (3) y seleccionamos el coeficiente de $z^{12}$ .

Utilizamos la notación $[z^n]$ para denotar el coeficiente de $z^n$ en una serie.

Obtenemos así \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*}

Comentario:

• En (4) se factoriza $z^{2k+1}$ .

• En (5) utilizamos la regla $[z^p]z^qA(z)=[z^{p-q}]A(z)$ y restringir la suma con límite superior $k=5$ ya que el exponente $11-2k$ es no negativo.

• En (6) seleccionamos el coeficiente de $z^{2k-1}$ y comenzar con el índice $k=3$ ya que los otros coeficientes binomiales con $k<3$ son cero.

Answer 4

Dejemos que $1$ denotan una línea negra & $0$ denotan una línea blanca. Un código de barras es entonces una secuencia de $1$ 's & $0$ que empieza y termina con $1$ y evita $000$ & $111$ . Así que tu problema es encontrar el número de palabras binarias de longitud $12$ que comienzan y terminan con $1$ y evitar $000$ & $111$ .

Dejemos que $a_n$ denotan el número de palabras binarias que empiezan por $1$ y terminar $11$ (& satisfacer la $000$ , $111$ condición). Sea $A(x)$ denotan la función generadora de $a_n$ . Defina B(x) de forma similar a $A$ para terminar $01$ . Defina C(x) de forma similar a $A$ para terminar $00$ Defina D(x) de forma similar a $A$ para terminar $10$ . Estas funciones están relacionadas por las siguientes relaciones de recurrencia. \begin{eqnarray*} A=x^2+xB \\ B=x(C+D) \\ C=xD \\ D=x^2+x(A+B) \end{eqnarray*} Ahora resuelve esto y encuentra los coeficientes $x^{12}$ en $A$ & $B$ . Añade estos valores.