Quantas maneiras existem para colocar$15$pedaços de tamanho$1 \times 2$dentro de$3 \times 10$retângulo? [duplicado]

Question

Quantas maneiras existem para colocar$15$pedaços de tamanho$1 \times 2$dentro de$3 \times 10$retângulo? (girar e inverter são considerados maneiras diferentes)

Acho que essa questão pode ser resolvida por recursão. Eu tentei dividir cada coluna para$(2,1)$e divida cada linha em grupos de números pares. Mas os grupos de coluna e linha às vezes não podem ser satisfeitos ao mesmo tempo.

Qualquer ajuda ou dica é apreciada. Muito obrigado.

Answer 1

Recursão: estamos lado a lado da esquerda para a direita. Digamos que já tenhamos lado a lado alguma parte do retângulo incluindo de alguma forma o quadrado mais à esquerda, então nos restam 7 possibilidades de como os quadrados mais à esquerda (cinza) se parecem:

  1 2 3 4 5 6 7

vamos denotar$f_k(n)$o número de maneiras que podemos ladrilhar$k$º caso com$n$cheio ($=$até)$3\times 1$blocos após o mais à esquerda (parcialmente lado a lado como em 1-6 ou até como em 7), então estamos interessados ​​em$f_7(9)$.

nós 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$então$\mathbf{f}(n+1)=A\mathbf{f}(n)$Onde$$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}$$e$\mathbf{f}(1)=(1,0,0,1,0,0,3,0)^T$. O resto (fatoração de$A$em$SDS^{-1}$e computação$(0,0,0,0,0,0,1,0)SD^8S^{-1}\mathbf{f}(1)$partimos para WolframAlpha ) e a resposta é$571$.

Aliás, pesquisando a sequência A001835 verifica-se que o problema tem uma solução mais curta:

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

Você pode encontrá-lo? )