Se colocan doce láminas cuadradas en fila, y cada una puede pintarse con uno de los cuatro colores Y,R,O,B. Encuentra el número de formas en que se puede hacer esto para que cada bloque de cinco hojas adyacentes contenga al menos una hoja de cada color . Lo que he intentado es que para los casos inferiores de hojas he tratado de ver el patrón para motivar una relación recursiva, pero al pasar de 7 a 8 casos y los superiores se necesita una relación recursiva que no soy capaz de generar. Como los casos inferiores (<8) no necesitan ninguna recursividad se puede resolver fácilmente.
Respuesta
¿Demasiados anuncios?
Dejemos que $n \geqslant 5$ sea el número de hojas de color, numeradas desde $1$ a $n$ . Ampliamos el sistema añadiendo una nueva hoja en la posición $0$ y desplazando las hojas hacia la derecha.
Para cualquier coloración $c$ , dejemos que el índice de repetición $r \in \left\{2 , 3 , 4 , 5\right\}$ sea el índice de la primera hoja con un color repetido. Si $r = 5$ significa que el $4$ las primeras hojas tienen colores diferentes. Se puede añadir una nueva hoja de cualquiera de los cuatro colores, da $4$ formas de extender la coloración, cuyos respectivos índices de repetición son $2 , 3 , 4 , 5$ .
Si $r < 5$ significa que sólo hay $3$ colores entre los $4$ primeras hojas y la única forma de ampliar el sistema es añadir un nuevo hoja cuyo color es el que falta entre las $3$ . El resultado es una coloración cuyo índice de repetición es $r+1$ .
Dejemos que ${X}^{\left(n\right)} = {\left({X}_{2}^{\left(n\right)} , {X}_{3}^{\left(n\right)} , {X}_{4}^{\left(n\right)} , {X}_{5}^{\left(n\right)}\right)}^{T}$ sea el número de coloraciones con índices de repetición $\left(2 , 3 , 4 , 5\right)$ para $n$ hojas. El razonamiento anterior muestra que
\begin{equation} {X}^{\left(n+1\right)} = A {X}^{\left(n\right)} = \left[\begin{array}{cccc}0&0&0&1\\ 1&0&0&1\\ 0&1&0&1\\ 0&0&1&1 \end{array} \[derecha] {X}^ {Izquierda(n-derecha)} \fin{ecuación}
En particular, el número ${C}_{n}$ de coloraciones de $n$ hojas es ${C}_{n} = U {X}^{\left(n\right)}$ donde $U = \left(1 , 1 , 1 , 1\right)$ . De ello se desprende que
\begin{equation} {C}_{n+k} = U {A}^{k} {X}^{\left(n\right)} \end{equation}
Afirmamos que $U {A}^{k} = \left({u}_{k-3} , {u}_{k-2} , {u}_{k-1} , {u}_{k}\right)$ donde la secuencia real ${u}_{k}$ satisface la relación de recurrencia
\begin{equation} \boxed{{u}_{k+1} = {u}_{k}+{u}_{k-1}+{u}_{k-2}+{u}_{k-3}} \end{equation}
De hecho, esto es una consecuencia inmediata de la relación $U {A}^{k+1} = U {A}^{k} A$ . Los valores iniciales de $u$ son
\begin{equation} {u}_{{-3}} = {u}_{{-2}} = {u}_{{-1}} = {u}_{0} = 1 \end{equation}
De ello se desprende que
\begin{equation} {C}_{n+k} = {u}_{k-3} {X}_{2}^{\left(n\right)}+{u}_{k-2} {X}_{3}^{\left(n\right)}+{u}_{k-1} {X}_{4}^{\left(n\right)}+{u}_{k} {X}_{5}^{\left(n\right)} \end{equation}
Para $n = 5$ , uno tiene ${X}^{\left(5\right)} = 4 ! \left(1 , 2 , 3 , 4\right)$ De ahí la fórmula
\begin{equation} \boxed{{C}_{5+k} = {24}\times{\left(4 {u}_{k}+3 {u}_{k-1}+2 {u}_{k-2}+{u}_{k-3}\right)}} \end{equation}
En particular ${C}_{12} = {24}\times{1129} = 27096$
Observación: hay que tener en cuenta que $A$ tiene la forma de Matriz de acompañamiento
