Número de cadenas de bits de longitud 8, que no contienen "$100$"?

Question

Estoy pensando en el número total de posibles cadenas de es $2^8$ y el número de cadenas con $100$ al principio iba a ser $2^8 - 2^3 = 2^5$. Ahora "$100$" puede cambiar a través de la cadena de $5$ veces a la derecha. Es la respuesta, a continuación,$2^8 - 2^5 \times 5$?

Answer 1

Como se discute en los comentarios, la recta hacia adelante enfoque como el propuesto en la pregunta no va a funcionar porque se multiplican cuenta el mal cadenas en el que $100$ aparece más de una vez (de hecho, se la considera mala cadenas de una vez para cada aspecto de $100$).

Para cadenas cortas (como la longitud de la $8$) más cuidadoso recuento a través del principio de Inclusión/Exclusión no es imposible pero no es exactamente fácil y, como la longitud aumenta, este método se hace más difícil y más difícil. Creo que es más fácil para atacar el problema de forma recursiva. Hacia ese fin, a definir algunos de los sub-tipos de la "buena" cadenas de longitud $n$. Específicamente, deje $A_n$ denotar esas buenas cadenas que terminan en $1$ y deje $B_n$ denotar aquellos que terminan en $10$. Tenga en cuenta que el total $T_n$ es el dado por $$T_n=A_n+B_n+1$$ where the $1$ comes from the good string $0^n$ which ends in neither $1$ nor $10$.

Recursiva, se nota que $$A_n=A_{n-1}+B_{n-1}+1=T_{n-1}$$ since you get a good string of length $n$ by appending a $1$ to any good string of length $n-1$. Similarly $$B_n=A_{n-1}=T_{n-2}$$ Thus $$T_n=T_{n-1}+T_{n-2}+1$$

Es fácil ver que $A_1=1$, $A_2=2$, $B_1=0$, $B_2=1$ de dónde $$\{T_n\}=\{2,4,7,12,20,33,54,88,\cdots\}$$

Verificación de consistencia: Vamos recuento $T_4,\;T_5,\;T_6$ directamente. Hay $16$ cadenas de longitud $4$ y los malos son $x100$$100x$, por lo tanto no se $4$ mala cadenas para $T_4=16-4=12$ como se desee. Del mismo modo el mal cadenas de longitud $5$ $100xx$, $x100x$, $xx100$ por lo $T_5=32-12=20$ como se desee. Para contar la mala cadenas de longitud $6$ tenemos que ser un poco cuidadoso...los patrones son $100xxx$, $x100xx$, $xx100x$, $xxx100$ pero tenemos que volver a agregar $1$ para el cómputo doble de la cadena de $100100$. Por lo tanto $T_6=64-8\times 4+1=33$ como se desee.

La inducción muestra que, de hecho, $T_n=F_{n+3}-1$ donde $F_i$ indica los números de Fibonacci $\{F_i\}_{i=1}^{\infty}=\{1,1,2,3,5,8,13,21,\cdots\}$

Answer 2

El uso de funciones de generación con $z$ cero y $w$ para aquellos que tenemos la generación de la función

$$(1+z+z^2+\cdots) \left(\sum_{q\ge 0} ((w+w^2+w^3+\cdots) z)^q\ \ derecho) (1+w+w^2+\cdots).$$

Este rendimientos

$$\frac{1}{1-z}\left(\sum_{q\ge 0} z^q \frac{w^p}{(1-w)^p}\right) \frac{1}{1-w} \\ = \frac{1}{1-z}\frac{1}{1-w} \frac{1}{1-wz/(1-w)} \\ = \frac{1}{1-z} \frac{1}{1-w-wz}.$$

Como sólo estamos interesados en el conteo nos puede caer la distinción entre los ceros y los unos, llegar

$$\frac{1}{1-z} \frac{1}{1-z-z^2} = \frac{2+z}{1-z-z^2} - \frac{1}{1-z}.$$

La extracción de coeffcients de este rendimiento en términos de números de Fibonacci

$$2F_{n+1} + F_n - 1 = F_{n+1} + F_{n+2} - 1 = F_{n+3} - 1.$$

Podemos confirmar estos resultados utilizando la DFA el método que produce

> GFNC([[1,0,0]], 2,true);
 [[1, 0, 0]]

 P[], 0, Q[]

 P[], 1, Q[1]

 P[1], 0, P[1, 0]

 P[1], 1, Q[1]

 P[1, 0], 0, P[1, 0, 0]

 P[1, 0], 1, Q[1]

 Q[1, 0, 0], 0, P[1, 0, 0]

 Q[1, 0, 0], 1, P[1, 0, 0]

1
--------------------
2
 (z - 1) (z + z - 1)

Este enlace incluye una explicación de la Goulden-Jackson de clúster método por @MarkusScheuer.

Mediante la inclusión-exclusión que tenemos para la ubicación de la prohibida el patrón cuando $n=8$ las posibilidades de $(1),(2),(3),\ldots,(6)$ y $(1,4),(2,5),(3,6)$ $(1,5),(2,6)$ $(1,6).$ obtenemos así

$$2^8 - 6\times 2^5 + 6\times 2^2 = 88.$$

Podemos generalizar la inclusión-exclusión en el argumento. Supongamos que ha $q$ instancias del patrón en la $q\le\lfloor n/3\rfloor.$ Este hojas de $n-3q$ ranuras libres que deben ser distribuidas en el $q+1$ espacios entre / rodea a los patrones. Por las estrellas y las barras de esto se puede hacer en el siguiente número de maneras:

$${n-3q+q\choose q} = {n-2q\choose q}.$$

De este modo, obtener por medio de la inclusión-exclusión de la forma cerrada

$$\sum_{q=0}^{\lfloor n/3\rfloor} {n-2t\elegir q} (-1)^q 2^{n-3t}.$$

Podemos evaluar esto con el Egorychev método. Introducir

$${n-2t\elegir q} = {n-2t\elegir n-3t} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-3t+1}} (1+z)^{n-2t} \; dz.$$

Observar que este se desvanece al$3q\gt n$, por lo que podemos ampliar el rango de de $q$ hasta el infinito, para la suma

$$\frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \sum_{q\ge 0} \frac{z^{3t}}{(1+z)^{t2}} (-1)^q 2^{-3t} \; dz \\ = \frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \frac{1}{1+2^{-3}z^3/(1+z)^2} \; dz \\ = \frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+2} \frac{1}{1+2z+z^2+2^{-3}z^3} \; dz.$$

Ahora pon $z/(1+z) = w$, de modo que $z = w/(1-w)$ y $1+z = 1/(1-w)$ $dz = 1/(1-w)^2 \; dw$ y

$A$1+2z+z^2+2^{-3}z^3 = \frac{1}{8} \frac{(w-2)(w^2+2w-4)}{(1-w)^3}$$

que los rendimientos de la integral

$$\frac{2^n}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{8(1-w)^3}{(w-2)(w^2+2w-4)} \frac{1}{(1-w)^2} \; dw \\ = \frac{2^n}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{8}{(w-2)(w^2+2w-4)} \; ps.$$

Este es

$$2^n [w^n] \frac{8}{(w-2)(w^2+2w-4)} = [w^n] \frac{8}{(2w-2)(4a^2+4a-4)} \\ = [w^n] \frac{1}{(w-1)(w^2+w-1)} \\ = [w^n] \frac{1}{(1-w)(1-w-w^2)}.$$

Esta es la misma generación de funcionar como lo que hemos obtenido anteriormente y el argumento es la conclusión.

Adenda. Wilf también sucede aquí. Tenemos la generación de la función

$$\sum_{n\ge 0} z^n 2^n \sum_{q=0}^{\lfloor n/3\rfloor} {n-2t\elegir n-3t} (-1)^q 2^{-3t} = \sum_{q\ge 0} 2^{-3t} (-1)^q \sum_{n\ge 3t} z^n 2^n {n-2t\elegir n-3t} \\ = \sum_{q\ge 0} 2^{-3t} (-1)^q \sum_{n\ge 0} z^{n+3t} 2^{n+3t} {n+q\elegir n} = \sum_{q\ge 0} z^{3t} (-1)^q \sum_{n\ge 0} z^{n} 2^{n} {n+q\elegir n} \\ = \sum_{q\ge 0} z^{3t} (-1)^q \frac{1}{(1-2z)^{q+1}} = \frac{1}{1-2z} \frac{1}{1+z^3/(1-2z)} \\ = \frac{1}{1-2z+z^3}.$$

Esta es la misma generación de funcionar como antes, de hecho.

Answer 3

Una buena técnica es la denominada Goulden-Jackson Clúster Método que es un método conveniente para derivar una generación de función para problemas de este tipo.

Tenemos en cuenta las palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{0,1\}$$ and the set $\mathcal{B}=\{100\}$ de malas palabras que no pueden ser parte de las palabras que estamos buscando.

Que se derivan de una función de $F(x)$ con un coeficiente de $x^n$ el número de ganas de palabras de longitud $n$. Según el periódico (p.7) la generación de la función $F(x)$ es \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} con $d=|\mathcal{V}|=2$, el tamaño de las letras del alfabeto y con el peso numerador $\mathcal{C}$ con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[100]) \end{align*}

Calculamos de acuerdo con el documento \begin{align*} \text{weight}(\mathcal{C}[100])&=-x^3 \end{align*}

De la siguiente manera:

Una generación de función $F(x)$ para el número de palabras construido a partir de $\{0,1\}$ que no contienen la subword $100$ es \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x+x^3}\\ &=1+2x+4x^2+7x^3+12x^4+20x^5\\ &\qquad+33x^6+54x^7+88x^8+143x^9+232x^{10}+\cdots\tag{1} \end{align*}

La última línea (1) se calculó con Wolfram Alpha y vemos que el coeficiente de $x^8$$88$.

Llegamos a la conclusión: de $2^8=256$ cadenas binarias de longitud $8$ no son, precisamente, $88$ palabras que no contienen la subcadena $100$.

Por supuesto, también podemos calcular el resultado en la mano por la expansión de la generación de la función como series geométricas y extraer el coeficiente de $x^8$.

Para ello es conveniente utilizar el coeficiente de operador $[x^j]$ para denotar el coeficiente de $x^j$ de una serie.

Obtenemos \begin{align*} [x^8]\frac{1}{1-2x+x^3}&=[x^8]\sum_{n=0}^\infty(2x-x^3)^n\tag{2}\\ &=[x^8]\sum_{n=0}^\infty x^n\sum_{j=0}^n\binom{n}{j}(-x^2)^j2^{n-j}\tag{3}\\ &=\sum_{n=0}^8[x^{8-n}]\sum_{j=0}^n\binom{n}{j}(-1)^j2^{n-j}x^{2j}\tag{4}\\ &=\binom{4}{2}(-1)^22^{4-2}+\binom{6}{1}(-1)^12^{6-1}+\binom{8}{0}(-1)^02^{8-0}\tag{5}\\ &=6\cdot 4-6\cdot 32+1\cdot 256\\ &=88 \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (2) expandir la serie geométrica.

• En (3) nos factor $x^n$ y ampliar la binom usando la fórmula de $$(a-b)^n=\sum_{j=0}^n\binom{n}{j}(-b)^ja^{n-j}$$

• En (4) utilizamos la linealidad del coeficiente de operador y aplicar la fórmula $$[x^p]x^qA(x)=[x^{p-q}]A(x)$$ Since the exponent of $x^{8-n}$ is non-negative we restrict the upper limit of the sum with $8$.

• En (5) seleccionamos los coeficientes de $x^{8-n}$. Desde $0\leq j\leq n$ y el exponente de $x^{2j}$ es aún, sólo necesitamos considerar $n\in\{4,6,8\}$.

Answer 4

Considere la posibilidad de 4 exclusivas de los estados de una cadena puede ser en :

• (A) La cadena contiene 100
• (B) Los extremos de una cuerda de 10, pero no contienen 100
• (C) La cadena termina en 1, pero no contienen 100
• (D) Ninguna de las Anteriores

Ahora considere una matriz que representa las transiciones de los 4 estados. Por ejemplo, si una cadena está en el estado (B), y el siguiente bit es 0, entonces el siguiente estado de la cadena es (Una). Las transiciones si el siguiente bit es 0 están dadas por:

$$M_0 = \begin{array} {c|cccc} & A & B & C & D \\ \hline A & 1 & 0 & 0 & 0 \\ B & 1 & 0 & 0 & 0 \\ C & 0 & 1 & 0 & 0 \\ D & 0 & 0 & 0 & 1 \\ \end{array}$$

Y las transiciones si el siguiente bit es un 1 :

$$M_1 = \begin{array} {c|cccc} & A & B & C & D \\ \hline A & 1 & 0 & 0 & 0 \\ B & 0 & 0 & 1 & 0 \\ C & 0 & 0 & 1 & 0 \\ D & 0 & 0 & 1 & 0 \\ \end{array}$$

Y, en principio, la cadena está vacía, así que está en estado (D):

$$V = \begin{array} {cccc} A & B & C & D \\ \hline 0 & 0 & 0 & 1 \end{array}$$

Los estados alcanzables desde la cadena de longitud $n$ está dada por:

$$V(M_0 + M_1)^n$$

Así, por ejemplo, las cadenas de una longitud de 8 tendrá los estados:

$$V(M_0 + M_1)^8 = \begin{array} {cccc} A & B & C & D \\ \hline 168 & 33 & 54 & 1 \end{array}$$

168 cadenas contendrá 100, 33 terminará en 10, pero no contienen 100, 54 terminará en 1, pero no contienen 100, y habrá más de 1 cadena (la cadena que contiene todos los ceros). Así que hay $2^8 - 168 = 33 + 54 + 1 = 88$ las cadenas que no contienen 100.

Answer 5

No formales de las matemáticas, pero pensé que el post porque puede ayudar a usted o alguien de todos modos.

Esta es una pequeña función en el lenguaje de programación Python que da el número de length-bit cadenas binarias que no contiene el binario subcadena substring.

def notContaining(length, substring):
"""
Gives the number of 'length'-bit strings not containing 'substring'.
"""
n = 2**length # number of 'length'-bit strings

for i in range(0, 2**length): # for every number having (maximal) 'length' bits
    if str(substring) in i: # if the substring is in the i-th 'length'-bit binary string
        n -= 1

return n

Para length = 1 y substring = '100' devuelve 88:

>>> notContaining(8, '100')
88

Si alguien me avisos de cometer un error aquí, estaría agradecido de saber.