Número de maneras en que la sala puede ser de baldosas con $I$ en forma de e $L$ en forma de baldosas

Question

Hay una sala de dimensión $2\times 12$ unidades. Usted tiene a la teja. Hay dos tipos de fichas:

• En Forma de I - es de una dimensión $1\times 2$ unidades,
• En Forma de L - es en la forma de $L$ que tiene un área de $3$ sq. unidades.

De cuántas maneras se puede mosaico?

He estudiado algunos aspectos básicos de la permutación y combinación, pero no los puedo usar en esta pregunta.

Nota:

• El $I$ en forma de baldosas son idénticas en ambos lados.
• Puede girar las fichas en cualquier dirección si va a encajar.
• Usted tiene un suministro ilimitado de las baldosas.

Answer 1

SUGERENCIAS:

Desde la se necesita azulejo no es muy grande en todo lo que usted podría fácilmente sólo una lista de todos los apuntados (que definitivamente no es una bonita manera de solucionar el problema, pero si usted no tiene idea de cómo empezar, al menos, le da un punto de partida).

El uso de un número impar de $L$ en forma de mosaico que no tener éxito para usted directamente puede iniciar la comprobación de los casos en los que usted tiene un número par de $L$ azulejos.

El uso de $0$ de la $L$ azulejos usted será capaz de mosaico utilizando sólo el $I$ formas y esto se puede hacer sólo en $1$ manera.

El uso de $2$ de la $L$ forma de que usted tiene en $4$ de los casos,

1) están uno al lado del otro

2) tienen $2$ de la $I$ formas entre medio de ellos

3) tienen $4$ de la $I$ formas entre medio de ellos

4) tienen $6$ de la $I$ formas entre medio de ellos

Observar que en cada uno de estos casos, se obtiene un factor de $2$ en el número de soluciones ya que cada uno de estos se pueden girar alrededor de un horisontal eje.

Y así sucesivamente...

Como dije esto no es definitivamente una buena solución, la creación de una relación de recurrencia es mucho mejor aunque no estoy seguro de que si usted sabe cómo usar la recurrencia de la relación para resolver esto. Por favor, hágamelo saber si usted, en ese caso se puede trabajar algo más matemático :)

Espero que esta ayuda.

Answer 2

No estoy muy seguro de si se puede usar básica de permutación y combinación para resolver este problema.

Pero puede ser abordado de forma recursiva.

Indicar el número de maneras de colocar azulejos $2\times n$ área dada azulejos como $T(n)$, y el número de maneras de colocar azulejos $2 \times n$ zona además de un líder del bloque en la parte superior o inferior como $S(n)$

A continuación,

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

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

Tome la primera a la relación, por ejemplo. Si usted coloque la primera pieza del 'yo' y vertical, resultado en un $2\times (n-1)$ área. Si usted pone el primer mosaico 'yo' horizontalmente, usted tendrá que cubrir el área debajo de ella con otro horizontal 'yo' para cubrir completamente, usted obtener un $2\times (n-2)$ área. Si usted pone una 'L', usted lo puede hacer de dos manera válida, y por simetría, que tienen el mismo número de maneras de ser de azulejos, los nombres de $S(n-2)$.

Al resolver la relación de recurrencia, se puede obtener la respuesta a la $T(12)$, es decir, su pregunta.

Answer 3

Deje $A_n,B_n,C_n,D_n$ denotar las siguientes cuatro formas, donde a$n$ es el ancho de la forma. Deje $a_n,b_n,c_n,d_n$ el número de maneras de mosaico, respectivamente.

La parte superior derecha del campo de $A_n$ puede ser cubierto por una vertical $I$, por una horizontal $I$, por el ápice de una $L$, o por el "dedo" de un $L$. La eliminación de este tipo de recubrimiento produce la forma $A_{n-1}$, $D_n$, $B_{n-1}$o $C_{n-1}$, respectivamente. Llegamos a la conclusión de $$\tag1a_n=a_{n-1}+d_n+b_{n-1}+c_{n-1}.$$ El de más a la derecha del campo de $B_n$ puede ser cubierto por una horizontal $I$ o por el "dedo" de un $L$. La eliminación de este tipo de recubrimiento se produce cualquiera de las $C_{n-1}$ o $A_{n-2}$, respectivamente. Llegamos a la conclusión de $$\tag2b_n=c_{n-1}+a_{n-2}.$$ El de más a la derecha del campo de $D_n$ sólo pueden ser cubiertos por una horizontal $I$. Llegamos a la conclusión de $$\tag3d_n=a_{n-2}.$$ Y por simetría, claramente tenemos $$ \tag4c_n=b_n.$$ El uso de $(3)$ e $(4)$ a eliminar la $c_n$ e $d_n$, nos encontramos con $$ a_n=a_{n-1}+a_{n-2}+2b_{n-1}$$ y $$a_{n+1}=a_n+a_{n-1}+2b_n=a_n+a_{n-1}+2(b_{n-1}+a_{n-2})$$ y a partir de estos eliminan $b_{n-1}$: $$a_{n+1}= 2a_n+a_{n-2}.$$ Esta repetición es lo suficientemente bueno para calcular rápidamente el valor deseado $a_{12}$ de la mano de la fácil de obtener a partir de los valores de $$a_0=1, \quad a_1=1, \quad a_2=2.$$ (La recursividad puede también ser utilizado para finalmente obtener una fórmula explícita para $a_n$ arbitrarias $n$)

Answer 4

Aquí está una combinatoria de prueba de la siguiente recurrencia mencionado al final de Hagen von Eitzen la respuesta. $$ a_n=2a_{n-1}+a_{n-3} $$ Para especificar un mosaico de una $2\times n$ rectángulo, empezar con un suelo de baldosas de una $2\times (n-1)$ junta, agregar una vertical $I$ azulejos para el extremo izquierdo, a continuación, hacer una de dos cosas:

• Dejarlo como está.

• Hacer cualquiera de los siguientes reemplazos es posible, donde la xs marca de la $I$ azulejo en el extremo izquierdo.

X Y    ->  X X
X Y        Y Y

X L L  -> L X X
X L       L L

X L    -> L L
X L L     L X X

X Y Y  -> L M M
X Z Z     L L M

Esto genera casi todos los $2\times n$ apuntados. Los únicos que quedan son los que terminan en

L L M
L M M,

que se explica por la $a_{n-3}$.