Cuántas formas de apilar $n$ cajas de 4 colores para que ningún $2$ Las casillas azules son consecutivas.

Question

Dejemos que $X_n$ denota el número de formas de apilar cajas rojas, blancas y azules y verdes, encuentra las formas de contar las formas de apilar n cajas, sin cajas azules consecutivas.

Mi intento:

Dejemos que $X^R_n$ denota el número de formas de apilar n cajas sin azules consecutivos, que tienen un rojo encima. Lo mismo para $X^W_n, X^B_n, X^G_n$ .

Así, $X_n=X^R_n+X^W_n+X^B_n+ X^G_n$

Entonces $X^R_n=X_{n-1}$ ya que tiene una palabra de n cadenas con una última letra definida. Con la misma lógica:

$X^R_n=X^W_n=X^G_n=X_{n-1}$ .

Para $X^B_n$ tenemos que el último carácter es la B pero el carácter anterior sólo puede ser la W, la G o la R por lo que obtenemos:

$X^B_n=X^R_{n-1}+X^W_{n-1}+ X^G_{n-1}=3X_{n-2}$

$$ \therefore X_n=3X_{n-1}+3X_{n-2} $$

¿Es esto correcto?

Answer 1

Si he entendido bien la pregunta, tienes cuatro conjuntos de $n$ cajas de los colores rojo, blanco, azul y verde. Puedes apilar las cajas rojas, blancas y verdes en $$\frac {(3n)!}{(n!)^3}$$ formas, y el resto $n$ Las cajas azules pueden insertarse individualmente en el $(3n+1)$ espacios entre estas cajas (incluyendo el principio y el final) en $$\frac {(3n+1)!}{(2n+1)!n!}$$ formas. Luego se multiplican estos juntos

Answer 2

Sólo hay que distinguir entre azul y no azul.

Una pila admisible $S$ de altura $n$ tiene una caja no azul encima o una caja azul. En el primer caso $S'=S\setminus{\rm top\ box}$ es una pila admisible de altura $n-1$ y en el segundo caso $S''$ es una pila admisible de altura $n-2$ y el $(n-1)^{\rm st}$ caja no es azul. De ello se desprende que $$X_n=3X_{n-1}+3X_{n-2}\ .$$ Además, uno tiene $X_1=4$ , $X_2=4^2-1=15$ .