5-tuplas Opciones

[12321]

Cada coordenada de una 5-tupla es 1,2 o 3. De cuantas formas pueden formarse si 1 y 3 no estan juntos?

[mmmjuy]

Espero no estar meando fuera del tiesto:

Asignando valores a la 5-tupla de izquierda a derecha, la primera coordenada sólo puede ser 1 de una forma,
2 de una forma y 3 de una forma. Si llamamos Pk(n) a la cantidad de maneras en que la k-ésima coordenada de
la 5-tupla puede tomar el valor n, lo anterior se puede expresar como:

P1(1)=1
P1(2)=1
P1(3)=1

Por ejemplo, para la segunda coordenada tenemos que puede ser 1 tanto si la primera coordenada es 1 como
si es 2; es decir podemos "tomar dos caminos" para que la segunda coordenada tenga el valor 1.
Esto se puede expresar como: P2(1) = P1(1) + P1(2)

Es fácil ver que esto se puede generalizar como: Pk+1(1) = Pk(1) + Pk(2).

Asimismo vemos que:

Pk+1(2) = Pk(1) + Pk(2) + Pk(3)
Pk+1(3) = Pk(2) + Pk(3)

Finalmente resolver el problema equivaldría a encontrar la cantidad de formas en que
la última coordenada puede ser 1, 2 o 3.

Es decir debemos calcular P5(1) + P5(2) + P5(3)

Lo cual con unas locas iteraciones me da 99.