Mi pregunta es si debe ser $11C2$ o debería ser $11C1$ ?
Desde $01$ están conectados entre sí, los tomo como una sola unidad y hay $11$ diferentes posiciones en las que se pueden colocar. ¿Es la respuesta $11C1$ ?
Podría ser más fácil preguntar cuántas cadenas de bits de longitud $n$ no tienen la subcadena "01".
Pienso en la cadena de bits como una pequeña trama, así que $0100$ sería el gráfico $(0,0),(1,1),(2,0),(3,0)$ . La subcadena $01$ corresponde a un salto ascendente en el gráfico. De ello se deduce que los únicos gráficos que no tienen un salto ascendente son los de la forma $1^* 0^*$ (de la longitud adecuada, por supuesto).
Por lo tanto, el número de cadenas de bits de longitud $n$ no tienen la subcadena "01" es $n+1$ (todos los unos, todos los unos excepto el último lugar, ..., todos los ceros).
Por lo tanto, la respuesta es $2^n-(n+1)$ .
Una forma más fácil de responder a esto: hay $2^{12}$ cadenas de bits. Cuántas cadenas de bits no tienen una subcadena $01$ ? Para responder a esto: Esto significa que una cadena de bits tiene que ser todo $0$ s, todos $1$ s, o tiene $n$ líder $1$ s y $12-n$ siguiendo $0$ s. (Como $100000000000$ a través de $111111111110$ .)
Sólo hay una cadena de bits que es todo $0$ s, y sólo hay una cadena de bits que es todo $1$ s. Entonces hay $11$ cadenas de bits para la dirección- $1$ -y-que-sigue- $0$ caso. (Sólo hay que contar $100000000000$ , $11000000000$ etc., o mostrarlo aritméticamente).
Así que hay $13$ cadenas de bits que no tienen un $01$ subcadena. Así que hay $2^{12} - 13$ cadenas de bits que tienen un $01$ subcadena.
La observación crítica es que una cadena que carece de la subcadena $01$ sólo puede ser una subcadena (posiblemente vacía) de $1$ seguido de una subcadena (posiblemente vacía) de $0$ 's. Si cualquier $1$ viene después de cualquier $0$ entonces debe haber un $01$ subcadena. Por lo tanto, sólo hay $13$ diferentes cadenas de bits que no tienen una subcadena $01$ y el número total de cadenas que satisfacen la condición original es $2^{12}-13$ .
Yo atacaría este problema de izquierda a derecha:
Supongamos que mi cadena comienza con 0 entonces tenemos muchas posibilidades de que mi cadena tenga la subcadena 01 , esos son $(2^{11} - 1)$ (tenemos todos los $2^{11}$ posibilidades, excepto cuando todos los $11$ los bits que quedan son todos 0 s).
El siguiente paso que daría es suponer que mi cadena empieza por 10 , entonces tenemos otro $(2^{10} - 1)$ posibilidades, entonces suponemos que comienza con 110 y así sucesivamente...
Al final (últimos pasos), mi cadena comienza con 11111111110 ; ( $10$ 1 s), por lo que tengo $2^1 - 1=1$ posibilidad de que mi cadena tenga la subcadena 01 , que es cuando mi última parte es 1 . Entonces tendría mi cadena inicial como 11111111110 ( $11$ 1 s), y ahí tengo $2^0 - 1 = 0$ posibilidades de tener la 01 como una subcadena, y eso es obvio porque no tengo bits disponibles, y mi cadena no tiene la subcadena 01 . Y finalmente 111111111111 ( $12$ 1 s) tampoco tiene la cadena '01` como subcadena.
Así que la respuesta es
$$\begin{align} (2^{11} - 1) + (2^{10} - 1)+ & \ldots + (2^0 - 1) \\ &= (2^{11} + 2^{10} + \ldots + 2^0) - \overbrace{(1+1+ \ldots +1)}^{12 \text{ times}} \\ &= (2^{12} - 1) - 12 \\ &= 2^{12} - 13 = 4083 \end{align}$$
Sí: al final (últimos pasos), mi cadena comienza con '11111111110' (10 1's y 1 '0'), por lo que tengo 2"1 - 1 posibilidades de que mi cadena tenga la subcadena '01', es decir, 1 posibilidad (es cuando mi último bit es '1'). Entonces tendría mi cadena inicial como '11111111110' (11 1's y 1 '0'), y ahí tengo 2"1 - 1 posibilidades de tener el '01' como subcadena, y eso es obvio porque no tengo bits disponibles, y mi cadena no tiene la subcadena '01'. Y mi última cadena es '1111111111' (12 1's), y esa no tiene la cadena '01' como subcadena.
(2"11 - 1) + (2"10 - 1) + ... + (2"0 - 1) = (2"11 + 2"10 + ... + 2"0) - (1+1+1... [12 veces]) = (2"12 - 1) - 12 = 2"12 - 13 De nada :)
El número de cadenas con el primer $01$ que se produce en el $1$ posición:
El número de cadenas con el primer $01$ que se produce en el $2$ n de la posición:
El número de cadenas con el primer $01$ que se produce en el $3$ posición:
El número de cadenas con el primer $01$ que se produce en el $4$ posición:
Y así sucesivamente...
Por lo tanto, la fórmula general es $\sum\limits_{n=1}^{11}n\cdot2^{11-n}=4083$ .
Dado que el número total de cadenas es $2^{12}=4096$ Probablemente hay una forma más fácil de obtenerlo.
¡¡¡Quienquiera que haya votado en contra de esto: es lo mismo que todas las respuestas votadas en contra de arriba, así que por favor no vote en contra a menos que deje un comentario explicándolo!!!
Oye barak, he subido el voto no porque tu respuesta sea la misma, sino porque es diferente. Así que estás un poco por delante ahora :-)
@Joffan: Gracias. El resultado final es el mismo que en otras respuestas aquí, y correcto. Por eso me molestó el voto negativo irracional (de hecho, el "irracional" sería molesto incluso si el resultado fue equivocado). Además, el método de solución es efectivamente diferente, y como has insinuado (si te he entendido bien), simplemente aporta una perspectiva diferente a este post.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Sugerencia. ¿Su método da la respuesta correcta para cadenas de bits de longitud 3? Resuelve ese caso a mano y generaliza.
0 votos
Sería entonces 10C1 o 10C3. La única forma de comprobar que mi respuesta es correcta es escribir un código para ello o contarlos manualmente. Creo que debería ser 10C1. Corrígeme si me equivoco.
0 votos
Consulte cualquiera de las respuestas siguientes para obtener una respuesta...
0 votos
@user3525357 No, Ethan se refería a resolver el caso "cuántas cadenas de bits de longitud 3 tienen una subcadena 01". Esto es muy fácil de comprobar a mano.
0 votos
Gracias a todos los que han respondido.