No es trivial responder esto. Por lo general, si a un alumno no se le ha mostrado cómo responder una pregunta como esta, no podrá resolverlo.
La forma más fácil de hacer esto es mediante el uso de una relación de recurrencia. Si no está familiarizado con ellos, probablemente no entenderá esta respuesta.
Sea F (n) = el número de cadenas binarias de n dígitos que no contienen 1 consecutivos.
- ¿Qué es la función mágica en MATLAB?
- Cómo obtener una sólida base matemática
- ¿Cómo podemos demostrar que una curva de Bezier es un caso específico de una curva B-spline por la definición de B-splines?
- ¿Qué es una tabla V o una tabla virtual en C ++?
- Cómo encontrar la suma de todos los números distintos cuyo MCM es N
Para obtener una fórmula para F (n), considere una cadena binaria válida de n dígitos. (‘Válido’ significa que cumple con las condiciones que especificó). Vamos a dividirlos en dos casos.
Caso 1: el último dígito es 0. Si es así, los primeros n-1 dígitos pueden ser cualquier cadena binaria válida. Esto se debe a que puede tomar cualquier cadena válida de longitud n-1 y poner un 0 al final y obtendrá una cadena válida de longitud n. Entonces el número de tales cadenas es F (n-1).
Caso 2: el último dígito es 1. Si es así, tenga en cuenta que el segundo al último dígito debe ser un 0; de lo contrario, tendría dos 1 consecutivos. Pero entonces los primeros n-2 dígitos pueden ser cualquier cadena válida. Esto se debe a que puede tomar cualquier cadena válida de longitud n-2 y poner un 01 al final y obtendrá una cadena válida de longitud n. Entonces el número de tales cadenas es F (n-2).
Esto nos deja con la relación de recurrencia:
F (n) = F (n-1) + F (n-2) para n> = 3. Si n = 1 ambas cadenas binarias son válidas, entonces F (1) = 2. Y si n = 2, todas las cuatro cadenas binarias son válidas excepto para 11. Entonces F (2) = 3.
Esta relación de recurrencia genera la secuencia más famosa de todas: la secuencia de Fibonacci. Como la relación de recurrencia nos dice que el siguiente valor en la secuencia es la suma de los dos valores anteriores, obtenemos la secuencia,
2, 3, 5, 8, 13, 21, 34, 55, etc.
Entonces, por ejemplo, el número de cadenas binarias válidas de longitud 7 es 55.
—–
Como deseaba la probabilidad de elegir una cadena binaria de n dígitos válida, necesita saber que el número total de cadenas binarias de n dígitos. Esto es solo [matemática] 2 ^ n [/ matemática], porque cada dígito tiene dos valores posibles.
Entonces la probabilidad es [matemática] \ frac {F (n)} {2 ^ n} [/ matemática].
No pregunte por qué, pero para n> = 5 más o menos, esta probabilidad es sobre:
[matemáticas] (1.17) ({0.809} ^ {n}) [/ matemáticas].
—–
EDITAR: Me di cuenta de que no terminé mi respuesta. Calculé la probabilidad de que una cadena binaria de n dígitos no tenga dos o más 1 en una fila. Para obtener la probabilidad de que una cadena binaria de n dígitos tenga dos o más 1 seguidos, solo resta la respuesta que le di a 1.
