Número de cadenas de bits con 3 ceros consecutivos o 4 1s consecutivos

Question

Estoy intentando contar el número de cadenas de bits de longitud 8 con 3 ceros consecutivos o 4 unos consecutivos. He podido calcularlo, pero estoy contando de más. La respuesta correcta es $147$ Tengo $148$ .

Lo he calculado de la siguiente manera:

Número de cadenas con 3 ceros consecutivos = $2^5+5\times2^4 = 112$ porque los 3 ceros pueden empezar en el número de bit 1, 2, 3, , 6

Número de cadenas con 4 unos consecutivos = $2^4+4\times2^3 = 48$ utilicé el mismo razonamiento.

Ahora estoy tratando de contar el número de cadenas de bits que contienen 3 ceros consecutivos y 4 1s consecutivos. He razonado de la siguiente manera:

las cadenas pueden ser de las siguientes formas: 0001111x, 000x1111, x0001111..así hay $2+2+2 = 6$ posibilidades para las cadenas de bits en las que los 3 ceros consecutivos van primero. Simétricamente hay $6$ cadenas de bits donde los 4 consecutivos van primero.

Por lo tanto, la respuesta debería ser = $112+48-12 = 148$ .

Está claro que hay algo que no cuadra en mi razonamiento, si alguien puede señalarlo, sería genial. Gracias

Answer 1

Aquí hay una forma de conseguir el 107 y el 48 en el comentario de mjqxxxx.

Dejemos que $a_n$ sea el número de cadenas de bits de longitud $n$ con 3 ceros consecutivos. Entonces $$a_n=2a_{n-1}+2^{n-4}-a_{n-4}$$ porque se puede obtener una cadena de este tipo a partir de una cadena de este tipo de longitud $n-1$ poniendo un cero o un uno al final, o a partir de una cadena de longitud $n-4$ sin 3 ceros consecutivos añadiendo 1000 al final. Claramente $a_0=a_1=a_2=0$ y $a_3=1$ y luego se puede utilizar la recursión para encontrar $a_4=3$ , $a_5=8$ , $a_6=20$ , $a_7=47$ , $a_8=107$ .

Para las cadenas de bits con 4 unos consecutivos, la misma lógica te lleva a $$b_n=2b_{n-1}+2^{n-5}-b_{n-5}$$ y luego se procede como antes.

Answer 2

Has omitido contabilizar las cadenas que tienen dos triples ceros. Así que $00010000,00010001,00001000,00011000,10001000$ se añadieron al total dos veces. Esto no causó ningún problema en su recuento de cadenas con cuatro $1$ s, sin embargo, ya que no podemos poner cuatro $1$ s en dos lugares separados en un $8$ -bit string. Así que la unión tiene ahora $155$ elementos, y cortando los dos duplicados de cada simetría de su cálculo de intersección se convierte en $8$ para un total de $107+48-8=147$ .

Answer 3

$ \begin{array}{|l|r|l|} \hline format & N & exceptions \\ \hline 000***** & 32 & \\ 1000**** & 16 & \\ *1000*** & 16 & \\ **1000** & 16 & \\ ***1000* & 14 & 0001000* \\ ****1000 & 13 & 000*1000 , 10001000 \\ 1111**** & 13 & 1111000* , 11111000 \\ 01111*** & 7 & 01111000 \\ *01111** & 8 & \\ **01111* & 6 & 0001111* \\ ***01111 & 6 & *0001111 \\ \hline \end{array}$

Total: $147$

Answer 4

Dejemos que $n$ sea un número entero no negativo. Sea $a_n$ sea el número de cadenas de bits de longitud $n$ con al menos 3 ceros consecutivos. Claramente $a_0 = 0$ , $a_1 = 0$ , $a_2 = 0.$ Dejemos que $n \geq 3.$ Denota por $S$ el conjunto de todas las cadenas de bits de longitud $n$ con al menos 3 ceros consecutivos. El conjunto $S$ es la unión disjunta de los cuatro conjuntos siguientes:

• $S_3$ el conjunto de todas las cadenas de bits de longitud $n$ que terminan con $000$ ,
• $S_2$ el conjunto de todas las cadenas de bits en $S$ que terminan con $100$ ,
• $S_1$ el conjunto de todas las cadenas de bits en $S$ que terminan con $10$ ,
• $S_0$ el conjunto de todas las cadenas de bits en $S$ que terminan con $1$ .

Estos conjuntos tienen las siguientes cardinalidades: $|S_3| = 2^{n-3}$ , $|S_2| = a_{n-3}$ , $|S_1| = a_{n-2}$ , $|S_0| = a_{n-1}$ . Desde $|S| =a_n$ por la regla de la suma $$ a_n = 2^{n-3} + a_{n-3} + a_{n-2} + a_{n-1}. $$ Desde $a_0 = 0$ , $a_1 = 0$ , $a_2 = 0$ tenemos \begin { [ ] \\ a_4 & = 2^1 + 0 + 0 + 1 = 3 \\ a_5 & = 2^2 + 0 + 1 + 3 = 8 \\ a_6 & = 2^3 + 1 + 3 + 8 = 20 \\ a_7 & = 2^4 + 3 + 8 + 20 = 47 \\ a_8 & = 2^5 + 8 + 20 + 47 = 107. \end {align*}

Para cadenas de bits con al menos 4 unos consecutivos, el mismo razonamiento lleva a la recursión $$ b_0 = b_1 = b_2 = b_3 = 0, \quad b_n=2^{n-4}+b_{n-4}+ b_{n-3}+ b_{n-2}+ b_{n-1}, \ n\geq 4. $$