¿Número de cadenas de longitud 8 con ABCDEF que contienen ABC?

Question

Aquí está mi intento de calcular el número de cadenas de longitud $8$ utilizando $6$ caracteres (ABCDEF) que contienen "ABC". Básicamente quería ver si mi enfoque es correcto o si hay una mejor manera de calcular esto.

Básicamente consideramos el ABC como un elemento por sí mismo, y puede ir:

ABC X X X X X

X ABC X X X X

X X ABC X X X

X X X ABC X X

X X X X ABC X

X X X X X ABC

Donde la X representa otro carácter. Así que tenemos $6$ filas y en cada fila hay $6^5$ posibilidades (puede elegir entre $6$ y tienen $5$ puntos), por lo que tenemos $6^6$ combinaciones.

Sin embargo, hay repeticiones, que son los siguientes casos:

ABC ABC X X

ABC X ABC X

ABC X X ABC

X ABC ABC X

X ABC X ABC

X X ABC ABC

Así que restamos estas posibilidades que son $6^3$ ( $6 \cdot 6^2$ porque hay $6$ filas y $2$ puntos para $6$ caracteres en cada fila)

Así que terminamos con $6^6 - 6^3$ .

Gracias de antemano.

Answer 1

Su resultado es correcto. Este cálculo por fuerza bruta lo confirma :D:

var count = 0;
for (let a0=0; a0<6; a0++)
for (let a1=0; a1<6; a1++)
for (let a2=0; a2<6; a2++)
for (let a3=0; a3<6; a3++)
for (let a4=0; a4<6; a4++)
for (let a5=0; a5<6; a5++)
for (let a6=0; a6<6; a6++)
for (let a7=0; a7<6; a7++) {
    let s =  a0+""+a1+""+a2+""+a3+""+a4+""+a5+""+a6+""+a7;
    if (s.indexOf("012")>=0) count++;
}
console.log(count);

46440

Otra forma de hacerlo es considerar la máquina de estados que comprueba si una cadena contiene la subsecuencia "ABC":

Podemos usar esto para calcular la probabilidad de que una palabra de 8 letras contenga la subsecuencia "ABC". Equivale a si llegamos al estado "ABC" partiendo del vacío en 8 pasos. La matriz es

$$\left [ \begin{array}\\ \frac{5}{6} & \frac{1}{6} & 0 & 0 \\ \frac{4}{6} & \frac{1}{6} & \frac{1}{6} & 0 \\ \frac{4}{6} & \frac{1}{6} & 0 & \frac{1}{6} \\ 0 & 0 & 0 & 1 \\ \end{array} \right ]$$

El elemento superior derecho de su octava potencia da la respuesta

(1/6[[5, 1, 0, 0], [4, 1, 1,0], [4, 1, 0, 1], [0,0,0,6]])^8

$$\frac{46440}{6^8}$$