Relación de recurrencia en un problema de asistencia estudiantil.

Question

Estoy teniendo problemas para entender la solución a un concurso de codificación de problema.

La Asistencia De Los Estudiantes Problema

Supongamos que una asistencia del estudiante se registra como una cadena, por ejemplo,

PPAPPPPLPPPLPPLLAPPPP

donde las letras representan los Presentes, Tarde o Ausente. Una recompensa es dada para el estudiante que cumple los siguientes criterios

1. No más de una ausencia.
2. No hay triples consecutivos tardanza, por ejemplo LLL.

Dado un récord de asistencia de longitud $n$, entonces, ¿cuántos recompensado existen registros?

Por ejemplo, para $n=2$, sólo AA no será recompensado, de $3^2$ cadenas posibles, así que la respuesta es $8$.

Solución Oficial

La solución oficial de los intentos de construir una relación de recurrencia, a partir de este diagrama:

Explica: Vamos a $f[n]$ representan el número de espectacular de los casos de una cadena de longitud $n$. Vamos a dividir en dos de los casos,

1. Las cadenas terminan con L.
2. Las cadenas terminan con P. (No sé por qué dice N en el diagrama; errata, creo.)

Es fácil ver que el segundo caso es espectacular como siempre que la pieza anterior a la P, $f[n-1]$, es espectacular.

Sin embargo, el L caso debe ser dividida en cuatro piezas, como se muestra. Allí, la autora afirma que la única problemática de la pieza es el último, terminando la cadena en LLL. Sus palabras exactas son,

Fuera de las cuatro combinaciones posibles al final, la cuarta combinación, que termina con un $LL$ al final conduce a un unrewardable cadena. Pero, puesto que hemos considerado sólo recompensado cadenas de longitud $n-3$, para la última cadena ser recompensado en la longitud de la $n-3$ y unawardable en la longitud de la $n-1$, debe estar precedido por una $PP$ antes de la $LL$.

Por lo tanto, la contabilidad de la primera cadena [rama izquierda] de nuevo, todo el espectacular cadenas de longitud $n-1$, a excepción de las cadenas de longitud $n−4$, seguido por $PLL$, puede contribuir a una espectacular cadena de longitud $n$. Por lo tanto, esta cadena representa un factor de $f[n-1] - f[n-4]$$f[n]$.

Por lo tanto, la recurrente relación se convierte en:

$$f[n] = 2f[n-1] - f[n-4]$$

Estaba esperando que alguien podría poner esta explicación con sus propias palabras, porque no entiendo de este autor. Y él ha hecho varios errores en su explicación ya, así que no estoy seguro de que puedo confiar en esta explicación.

Otra cosa que no entiendo es por qué el primero de los cuatro casos no es también problemático, ya que si el $n-5$th y $n-4$th personajes eran L, entonces también tendría un unrewardable cadena.

Cualquier sugerencias como para desenredar la explicación del autor se agradece. Gracias.

P. S. El autor es intencionalmente ignorar A en esta etapa, para ser considerados por separado.

Answer 1

Realmente es mucho más fácil que el autor hace.

Ha $3$ posible mutuamente exclusivos y exhaustivos finales a las secuencias válidas de longitud $n$

$$(\text{valid sequence length $n-1$})\, \text{P}$$ $$(\text{valid sequence length $n-2$})\, \text{PL}$$ $$(\text{valid sequence length $n-3$})\, \text{PLL}$$

o, en otras palabras

$$f[n]=f[n-1]+f[n-2]+f[n-3]\tag{Answer 1}$$

con $f[0]=1,\, f[1]=2,\, f[2]=2^2=4$.

Pero ya

$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$

tenemos

$$f[n]=2f[n-1]-f[n-4]\tag{Answer 2}$$

con el aumento de valor inicial $f[3]=2^2+2+1=7$.

---

La respuesta global (incluyendo la posibilidad de una ausencia) será

$$f[n]+\sum_{k=1}^{n}f[k-1]f[n-k]$$

porque hay $f[n]$ válido secuencias con ninguna ausencia y $\sum_{k=1}^{n}f[k-1]f[n-k]$ secuencias con $1$ la ausencia (en ausencia de Una puede estar en las posiciones de $k=1\ldots n$ con una secuencia válida de Ps y Ls cualquiera de los lados de la Una).