Número de formas de reordenar una línea de $n$ mármoles

Question

Mi amigo me retó a que resolviera el siguiente problema, y después de pensarlo durante mucho tiempo y no poder encontrar la respuesta, decidí abandonar. Su explicación que siguió no fue muy clara, y ya he olvidado la respuesta, pero sigo teniendo curiosidad. El problema es el siguiente:

Tienes a tu disposición canicas verdes, azules y rojas, y te gustaría ordenarlas en una sola línea de $n$ canicas de largo. Las canicas verdes nunca se pueden poner al lado de las otras. Las otras sí. ¿De cuántas maneras diferentes puedes reorganizar una línea de 10 canicas de largo?

También me gustaría conocer la fórmula general de las posibilidades de una línea de $n$ canicas de largo. Se agradecería una explicación.

Gracias de antemano.

Answer 1

La línea de longitud $n$ puede comenzar R o B seguido de una línea de longitud $n-1$ o GR o GB seguido de una línea de longitud $n-2$ . Si $S(k)$ cuenta el número de líneas de longitud $k$ tenemos

$$S(n)=2S(n-1)+2S(n-2)$$

con $S(1)=3$ y $S(2)=8$ . ¿Puedes seguir a partir de ahí?