La generación de una relación de recurrencia

Question

Suponga que tiene una de las colecciones más extensas de la red 1x2 azulejos, azul 1x2 azulejos y verde 1x2 azulejos. Para $n\ge 0$, vamos a $t_n$ el número de maneras de utilizar estas exactamente a cubrir las plazas de un 2xn de tablero de ajedrez (sin superposición de los azulejos). Los azulejos pueden ser lugares en el consejo, ya sea en vertical o en horizaontally. Determinar el $t_0 t_1 t_2 t_3$ y una recurrencia de la relación, y la condición inicial para $t_n$

Esto es lo que tengo:

$t_0 = 0$

$t_1 = 3$

$t_2 = (3)(3)+(3)(3) = 18$ $t_3 = (3)(3)(3)+(3)(3)(3)+(3)(3)(3) = 81$

No estoy seguro de si esto es correcto, y cómo obtener una relación de recurrencia

Answer 1

La relación de recurrencia es $t_n=3t_{n-1}+9t_{n-2}$. Aquí es cómo me encontré con esto:

Considere la posibilidad de una $2\times n$ tablero de ajedrez. ($2$ filas y $n$ columnas) Mirando en la parte superior izquierda de baldosas. Hay exactamente $2$ posiciones para colocar una pieza aquí. Ya sea vertical u horizontalmente.

Caso 1: colocación Vertical. En este caso, después de poner el azulejo, estamos realmente viendo cómo muchas maneras de colocar las baldosas en un $2\times (n-1)$ junta. Ya tenemos $3$ colores para este tipo de recubrimiento, tenemos $3t_{n-1}$ posibilidades.

Caso 2: ubicación Horizontal. En este caso, después de poner en la ventana, sólo puede haber una posición para colocar el azulejo directamente debajo de la primera baldosa. Después de estos $2$ azulejos, estamos realmente viendo cómo muchas maneras de colocar las baldosas en un $2\times (n-2)$ junta. Ya tenemos $3$ colores para la primera baldosa y $3$ para el segundo icono. Por lo tanto, para este arreglo, tenemos $(3)(3)t_{n-2}=9t_{n-2}$ posibilidades.

En total, sólo tenemos que añadir el resultado de la $2$ de los casos para obtener el resultado deseado.