Mosaico 3 por 2n rectángulo con fichas de dominó

Question

Yo estoy buscando para averiguar si hay alguna forma fácil de calcular el número de maneras de baldosa $3 \times 2n$ rectángulo con las fichas de dominó. Yo era capaz de hacerlo con los dos co-dependientes de las recurrencias

f(0) = g(0) = 1
f(n) = f(n-1) + 2g(n-1)
g(n) = f(n) + g(n-1)

donde $f(n)$ es la respuesta real y $g(n)$ es un auxiliar de la función que representa el número de maneras de baldosa $3 \times 2n$ rectángulo con dos plazas en la final (de la misma como una $3 \times 2n+1$ rectángulo falta una plaza).

Mediante la combinación de estos y hacer un poco de álgebra, de la que fue capaz de reducir este a

f(n) = 4f(n-1) - f(n-2)

que se muestra de la secuencia de A001835, lo que confirma que esta es la manera correcta de recurrencia.

El número de maneras de baldosa $2 \times n$ rectángulo es de los números de Fibonacci porque cada rectángulo termina con un verticle domino o dos horizontales, que da la exacta recurrencia que los números de Fibonacci hacer. Mi pregunta es, ¿hay una similar sencilla explicación para esta recurrencia para el revestimiento de un $3 \times 2n$ rectángulo?

Answer 1

Aquí está mi mejor tiro en el tipo de explicación que estás pidiendo, aunque no es tan claro como el de la $2 \times n$ de los casos. El signo negativo hace que la combinatoria de las pruebas difíciles, así que vamos a reorganizar esto como:

$$f(n) + f(n-2) = 4f(n-1)$$

Entonces usted quiere mostrar que el número de $n$-apuntados, más el número de $(n-2)$-apuntados, es cuatro veces el número de $(n-1)$-apuntados. ("N-mosaico" es un mosaico de una $3 \times 2n$ rectángulo por fichas de dominó.)

En bijective términos, entonces, queremos un bijection entre el conjunto de $n$-y embaldosados $(n-2)$-y embaldosados el conjunto de $(n-1)$-apuntados, donde el $(n-1)$-apuntados se etiqueta con el número de $1, 2, 3,$ o $4$.

Dado un $(n-1)$-suelo de baldosas, hay tres "obvio" maneras de obtener un $n$-mosaico de ella, es decir, mediante la adición de uno de los tres $1$-apuntados en el extremo derecho. Estos generan embaldosados que tienen una línea vertical que pasa a través de todo el camino, dos unidades desde el extremo derecho; llamar a estos "fallo" apuntados, y aquellos que no tienen una línea vertical en la posición "impecable".

Por lo que es suficiente para mostrar que el número de impecable $n$-apuntados, más el número de $(n-2)$-apuntados, es el número de $(n-1)$-apuntados. Es fácil ver que el número de impecable $n$-apuntados es $2g(n-2)$; un impecable apuntados debe tener una horizontal domino que cubre la segunda y tercera plazas de la derecha en algunas fila, y esta suposición fuerzas de la colocación de algunas otras fichas de dominó. Así que necesitamos a $2g(n-2) + f(n-2) = f(n-1)$. Cambio de los índices, necesitamos $2g(n-1) + f(n-1) = f(n)$, lo que ya ha dicho es cierto.

Answer 2

Para un determinado suelo de baldosas de $3 \times 2n$, considera el más pequeño $k\geq 1 $ tal que no es de domino que se encuentra en $k$$k+1$. Una simple comprobación de paridad muestra que $k$ debe ser par.

Para $k=2$, hay 3 maneras de mosaico de la inicial de la porción horizontal, sólo la parte superior horizontal, sólo horizontal inferior.

Para $k\geq 4$, hay 2 maneras de azulejo de la porción inicial - sólo la parte superior horizontal, sólo horizontal inferior.

Por lo tanto, esto nos da que $f(n) = 3 f(n-1) + 2f(n-2) + 2 f(n-3) + \ldots + 2 f(0)$.

Del mismo modo, $f(n-1) = 3f(n-2) + 2f(n-3) + \ldots + 2f(0)$.

Por lo tanto $f(n) - f(n-1) = 3f(n-1) - f(n-2)$, lo que da

$$ f(n) = 4 f(n-1) - f(n-2)$$