¿Cuántas formas hay de colocar$15$piezas de tamaño$1 \times 2$en un$3 \times 10$¿rectángulo? [duplicar]

Aug 15 2020

¿Cuántas formas hay de colocar$15$piezas de tamaño$1 \times 2$en un$3 \times 10$¿rectángulo? (girar y voltear se consideran formas diferentes)

Creo que esta pregunta podría resolverse por recursividad. Traté de dividir cada columna para$(2,1)$y divida cada fila en grupos de números pares. Pero los grupos de columna y fila a veces no se pueden satisfacer al mismo tiempo.

Cualquier ayuda o sugerencia es apreciada. Muchísimas gracias.

Respuestas

2 AlexeyBurdin Aug 15 2020 at 13:12

Recursividad: estamos mosaico de izquierda a derecha. Digamos que ya hemos colocado mosaicos en alguna parte del rectángulo al incluir de alguna manera el cuadrado hasta la izquierda, entonces nos quedan 7 posibilidades de cómo se ven los cuadrados hasta la izquierda (grises):

  1 2 3 4 5 6 7
denotemos$f_k(n)$el número de maneras en que podemos teselar$k$el caso con$n$completo ($=$hasta que)$3\times 1$bloques después del más a la izquierda (parcialmente en mosaico como en 1-6 o en mosaico como en 7), por lo que estamos interesados ​​en$f_7(9)$.

denotamos$\mathbf{f}(n)=(f_1(n),f_2(n),f_3(n),f_4(n),f_5(n),f_6(n),f_7(n),f_7(n-1))^T$después$\mathbf{f}(n+1)=A\mathbf{f}(n)$dónde$$A=\begin{pmatrix} 0&0&0&0&0&1&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&1&0&0&1&0\\ 0&0&1&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 1&0&0&0&0&0&1&0\\ 0&0&1&0&0&1&0&1\\ 0&0&0&0&0&0&1&0\\ \end{pmatrix}$$y$\mathbf{f}(1)=(1,0,0,1,0,0,3,0)^T$. El resto (factorización de$A$dentro$SDS^{-1}$y computación$(0,0,0,0,0,0,1,0)SD^8S^{-1}\mathbf{f}(1)$nos fuimos a WolframAlpha ) y la respuesta es$571$.

Por cierto, buscando la secuencia A001835 resulta que el problema tiene una solución más corta:

$a(n) = 4\cdot a(n-1) - a(n-2)$, con$a(0) = 1,\, a(1) = 1.$

¿Puedes encontrarlo? )