¿Cuántas formas hay de cubrir un $2\times 16$ rectángulo con $2\times 2,$ $2\times 3$ y $2\times 4$ ¿Rectángulos?

Question

¿Cuántas formas hay de cubrir un $2\times 16$ rectángulo con $2\times 2,$ $2\times 3$ y $2\times 4$ ¿Rectángulos?

Ya traté un problema similar, que es el de cuántas formas hay de cortar un $1\times 8$ rectángulo en $1\times 1$ y $1\times 2$ rectángulos. La respuesta a este problema se puede calcular utilizando el número de formas de dividir $1\times k$ tira para $3\le k\le8$ secuencialmente, para llegar a $34$ . Sin embargo, este problema es completamente diferente. ¿Cómo puedo resolver este problema?

Answer 1

Si tiene un $2 \times n$ rectángulo, entonces llame a $a_n$ el número de formas de cubrir ese rectángulo con $2\times p$ ( $p\in \{2,3,4\}$ ) rectángulos.

Si empiezas con $2\times 2$ entonces te enfrentarás al problema $a_{n-2}$ pero si empiezas con $2\times 3$ encontrará el problema $a_{n-3}$ y finalmente si se empieza con $2\times 4$ te enfrentarás a $a_{n-4}$ entonces tienes

$$a_{n}=a_{n-2}+a_{n-3}+a_{n-4}$$

y

$$a_2=1\\ a_3=1\\ a_4=2$$

y también necesitamos definir $a_1=0$ .

ahora puedes avanzar y encontrar $a_{16}$ .

Answer 2

Se trata de un $2 \times 16$ de la rejilla. La primera columna de dos celdas puede ser llenada por un $2 \times 2$ , a $2 \times 3$ o un $2 \times 4$ de la rejilla. Llamemos $f(n)$ el número de formas de llenar un $2 \times n$ de la rejilla. Entonces tenemos:

$$f(n) = f(n-2) + f(n-3) + f(n-4), n \geq 4$$

También sabemos que:

$$f(0) = 1$$ $$f(1) = 0$$ $$f(2) = 1$$ $$f(3) = 1$$

A forma cerrada no es sencillo, pero lo encontramos:

$$f(4) = 2$$ $$f(5) = 2$$ $$f(6) = 4$$ $$f(7) = 5$$ $$f(8) = 8$$ $$f(9) = 11$$ $$f(10) = 17$$ $$f(11) = 24$$ $$f(12) = 36$$ $$f(13) = 52$$ $$f(14) = 77$$ $$f(15) = 112$$ $$f(16) = 165$$