¿De cuántas maneras puede un mosaico [matemático] 2 × n [/ matemático] estar en mosaico por cuadrados unitarios y dominó?
Hice esto con lápiz y papel el domingo, pero luego no pude encontrar la pregunta para responder. Ahora veo que ya hay una muy buena respuesta que concuerda con la mía. Como ya hice el trabajo, compartiré mi enfoque, que finalmente da el mismo resultado, para la posteridad.
Primero, decidí que era una forma sistemática de construir un rectángulo [matemático] 2 \ veces n [/ matemático] usando cuadrados y fichas de dominó. Para hacer esto, pensé que una forma es construir agregando 1 cuadrado o dominó a la vez desde el extremo izquierdo del rectángulo, siempre agregando una nueva pieza (llamaré a un cuadrado o dominó una “pieza”) en la posición más a la izquierda disponible y Si hay una opción de dos posiciones más a la izquierda, agregue la nueva pieza en la parte superior de las dos.
Al construir de esta manera, vemos que solo hay 4 formas finales diferentes posibles después de colocar una pieza en cualquier momento durante la construcción
- ¿Cómo un par [matemáticas] n [/ matemáticas] personas con ingresos variables de la mejor manera?
- ¿Por qué se usa la base para representar problemas que se pueden resolver en tiempo exponencial el entero 2?
- ¿Cómo saber si una pregunta matemática es una ‘n!’ pregunta o una pregunta ‘n ^ n’
- ¿Por qué necesitamos la fórmula de interpolación para ajustar curvas?
- Si ya conozco la respuesta de una pregunta de algoritmo en una entrevista técnica, ¿cómo pretendo pensar que estoy pensando en resolver la pregunta?
El último es imposible ya que requeriría la colocación de un dominó horizontal en la fila inferior cuando hay una fila superior disponible. Es fácil ver que cualquier forma de extremo que sobresalga más de 2 bloques también es imposible.
La cantidad de formas de construir las formas anteriores están etiquetadas [matemáticas] t_n, \, u_n, \, v_n, \, w_n [/ matemáticas].
Se puede agregar cada una de las formas finales para formar otra como se muestra a continuación
Observe, por ejemplo, que [math] v_n [/ math] solo se puede formar a partir de [math] u_ {n-1} [/ math] debido a nuestra regla de construcción más a la izquierda. El sistema de recurrencias es
[matemáticas] t_n = t_ {n-1} + u_n + v_n + w_n [/ matemáticas]
[matemáticas] u_n = t_ {n-1} + v_ {n-1} + w_n [/ matemáticas]
[matemáticas] v_n = u_ {n-1} [/ matemáticas]
[matemáticas] w_n = t_ {n-2} [/ matemáticas]
Usar los dos últimos en el segundo da
[matemáticas] u_n = t_ {n-1} + t_ {n-2} + u_ {n-2} [/ matemáticas]
y luego [math] v_n [/ math], [math] w_n [/ math] y [math] u_n [/ math] en la primera recurrencia da
[matemáticas] t_n = 2t_ {n-1} + 2t_ {n-2} + u_ {n-1} + u_ {n-2} [/ matemáticas]
pero entonces
[matemáticas] t_ {n-1} = 2t_ {n-2} + 2t_ {n-3} + u_ {n-2} + u_ {n-3} [/ matemáticas]
así que resta
[matemáticas] t_n-t_ {n-1} = 2t_ {n-1} -2t_ {n-3} + u_ {n-1} -u_ {n-3} [/ matemáticas]
pero también
[matemáticas] u_ {n-1} = t_ {n-2} + t_ {n-3} + u_ {n-3} [/ matemáticas]
[math] \ Rightarrow u_ {n-1} -u_ {n-3} = t_ {n-2} + t_ {n-3} [/ math]
Reemplazar esto en nuestra expresión para [matemáticas] t_n-t_ {n-1} [/ matemáticas] da
[matemáticas] t_n-t_ {n-1} = 2t_ {n-1} + t_ {n-2} -t_ {n-3} [/ matemáticas]
o
[matemáticas] t_n = 3t_ {n-1} + t_ {n-2} -t_ {n-3} \ qquad \ blacksquare [/ math]
Los valores iniciales son [matemática] t_0 = 1, \, t_1 = 2, \, t_2 = 7 [/ matemática] como se puede ver en la imagen a continuación
Usando esta recurrencia en Excel, generé los primeros 15 valores para [math] t_n [/ math].
Disculpas por el tamaño de las imágenes, no estoy seguro de cómo personalizar eso.