Encuentra el número de cadenas de longitud n que contiene al menos 2 instancias de p, 1 de r y 1 de e.

Aquí hay un enfoque de inclusión-exclusión. Las cuatro propiedades a evitar son$p_0$,$p_1$,$r_0$, y$e_0$, donde el subíndice indica el número de veces que aparece la letra en la cadena.

$$\begin{matrix} \text{Properties} & \text{String count} & \text{Contribution} \\ \hline \emptyset & 26^n & (-1)^0 26^n \\ p_0 & 25^n & (-1)^1 25^n \\ p_1 & n 25^{n-1} & (-1)^1 n 25^{n-1} \\ r_0 & 25^n & (-1)^1 25^n \\ e_0 & 25^n & (-1)^1 25^n \\ p_0, r_0 & 24^n & (-1)^2 24^n \\ p_0, e_0 & 24^n & (-1)^2 24^n \\ r_0, e_0 & 24^n & (-1)^2 24^n \\ p_1, r_0 & n 24^{n-1} & (-1)^2 n 24^{n-1} \\ p_1, e_0 & n 24^{n-1} & (-1)^2 n 24^{n-1} \\ p_0, r_0, e_0 & 23^n & (-1)^3 23^n \\ p_1, r_0, e_0 & n 23^{n-1} & (-1)^3 n 23^{n-1} \\ \hline \end{matrix}$$ Al sumar la tercera columna se obtiene el conteo deseado.

Puedes definir$f(n, a, b, c)$ser el número de longitud$n$cadenas que contienen$a$PD,$b$e's y$c$r's (es fácil generalizar para más caracteres). Lo que estás tratando de encontrar es entonces$f(n, 2, 1, 1)$. Ahora imagina que tienes$n$ranuras _ _ ... _y considere la primera ranura. Si contiene un$p$, el resto solo requerirá$(1, 1, 1)$p, e, r respectivamente, por lo que este caso corresponde a$f(n - 1, 1, 1, 1)$. Trabajando para los otros casos donde la primera letra es e, r u otros caracteres, obtenemos

$$f(n, 2, 1, 1) = f(n - 1, 1, 1, 1) + f(n - 1, 2, 0, 1) + f(n - 1, 2, 1, 0) + 23f(n - 1, 2, 1, 1)$$

En general, tenemos$f(n, a, b, c) = f(n - 1, a - 1, b, c) + f(n - 1, a, b - 1, c) + f(n - 1, a, b, c - 1) + 23f(n - 1, a, b, c)$, dónde$a - 1$es reemplazado por$0$si$a = 0$, etc.

---

Ahora, para ampliar las recurrencias anteriores, permítanme escribir la abreviatura$f_{abc}$representar$f(n, a, b, c)$a la izquierda, y$f(n - 1, a, b, c)$A la derecha. Entonces,

$f_{211} = f_{111} + 2f_{210} + 23f_{211}$,$f_{111} = 3f_{110} + 23f_{111}$,$f_{110} = 2f_{100} + 24f_{110}$,$f_{100} = f_{000} + 25f_{100}$,$f_{210} = f_{110} + f_{200} + 24f_{210}$,$f_{200} = f_{100} + 25f_{200}$.

Esto significa que podemos escribir las recurrencias lineales como una gran matriz

$$\begin{pmatrix} 23 & 1 & 2 & 0 & 0 & 0 & 0 \\ 0 & 23 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 24 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 25 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 24 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 25 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 26 \end{pmatrix} \begin{pmatrix} f(n - 1, 2, 1, 1) \\ f(n - 1, 1, 1, 1) \\ f(n - 1, 2, 1, 0) \\ f(n - 1, 2, 0, 0) \\ f(n - 1, 1, 1, 0) \\ f(n - 1, 1, 0, 0) \\ f(n - 1, 0, 0, 0) \end{pmatrix} = \begin{pmatrix} f(n, 2, 1, 1) \\ f(n, 1, 1, 1) \\ f(n, 2, 1, 0) \\ f(n, 2, 0, 0) \\ f(n, 1, 1, 0) \\ f(n, 1, 0, 0) \\ f(n, 0, 0, 0) \end{pmatrix}$$

Donde las condiciones iniciales son$\vec{f}(0, a, b, c) = (0, 0, 0, 0, 0, 0, 1)$.

Por ejemplo, tenemos

$$\begin{pmatrix} 23 & 1 & 2 & 0 & 0 & 0 & 0 \\ 0 & 23 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 24 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 25 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 24 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 25 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 26 \end{pmatrix}^{30} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} = \begin{pmatrix} 408298312495180146737959753848343345105980 \\ 904661966989667522499666243022416746553180 \\ 611123311067817274112032976724465487015472 \\ 905003077710258115405504100084874108632001 \\ 1333356301461700027474470378150973559137502 \\ 1945837163296342372052658788920018151600751 \\ 2813198901284745919258621029615971520741376 \end{pmatrix}$$

Así que la primera fila da la respuesta.$408298312495180146737959753848343345105980$para$n = 30$(recuerda que tratamos de encontrar$f(n, 2, 1, 1)$).

---

Si de alguna manera todavía no está satisfecho, puede encontrar el polinomio de características de la matriz y hacer algunas locuras con él. Omitiré el cálculo y daré el resultado:

$$f(n) = 26^n - 3\cdot 25^n + 3\cdot 24^n - 23^n - n\cdot 23^{n - 1} + 2n\cdot 24^{n - 1} - n\cdot 25^{n - 1}$$

¡Espero que esto ayude!