Quanti modi ci sono per posizionare$15$pezzi di dimensioni$1 \times 2$in un$3 \times 10$rettangolo? [duplicare]

Question

Quanti modi ci sono per posizionare$15$pezzi di dimensioni$1 \times 2$in un$3 \times 10$rettangolo? (la rotazione e il capovolgimento sono considerati modi diversi)

Penso che questa domanda potrebbe essere risolta dalla ricorsione. Ho provato a dividere ogni colonna in$(2,1)$, e dividi ogni riga in gruppi di numeri pari. Ma i gruppi di colonne e righe a volte non possono essere soddisfatti contemporaneamente.

Qualsiasi aiuto o suggerimento è apprezzato. Grazie mille.

Answer 1

Ricorsione: stiamo affiancando da sinistra a destra. Diciamo che abbiamo già piastrellato una parte del rettangolo includendo in qualche modo il quadrato senza fine più a sinistra, quindi ci rimangono 7 possibilità di come appaiono i quadrati senza fine più a sinistra (grigi):

  1 2 3 4 5 6 7

Indichiamo$f_k(n)$il numero di modi in cui possiamo tessere$k$esimo caso con$n$completo ($=$fino a)$3\times 1$blocchi dopo il più a sinistra (parzialmente affiancati come in 1-6 o fino a quando non si è come in 7), quindi ci interessa$f_7(9)$.

Denotiamo$\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$poi$\mathbf{f}(n+1)=A\mathbf{f}(n)$dove$$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$. Il resto (fattorizzazione di$A$in$SDS^{-1}$e informatica$(0,0,0,0,0,0,1,0)SD^8S^{-1}\mathbf{f}(1)$siamo partiti per WolframAlpha ) e la risposta è$571$.

A proposito, guardando la sequenza A001835 risulta che il problema ha una soluzione più breve:

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

Puoi trovarlo? )