Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
We are provided with a large empty box of dimension $2 \times 2 \times n$ units.
Also , we have an object of volume $1 \times 1 \times 2$ units . We can thus place $2 n$ such objects in the large box.
Now, we can arrange these objects in any way - either vertically or horizontally , so as to fill the large box completely .
We need to tell the number of distinct ways we can fill it .
As we shall see it is sufficient to consider $T_n$-towers, which are completed $2\times2\times n$ towers, and $L_n$-towers which are full $2\times2\times n$ towers with two vertical bricks sticking out one unit at the top. Denote by $T_n$, resp. $L_n$ the number of these towers as well. Direct counting gives $$T_0=1,\quad T_1=2,\quad T_2=9\ .\tag{1}$$
Note that vertical bricks can only be placed in aligned pairs.
Consider a $T_n$ tower. From above we can see one of the following:
(a) The top faces of four vertical bricks standing on a $T_{n-2}$. Remove these.
(b) Two horizontal bricks lying on a $T_{n-1}$ (two possibilities). Remove these.
(c) The top faces of two vertical bricks and one horizontal brick lying on an $L_{n-1}$ (four possibilities). Remove the horizontal brick.
Consider an $L_n$ tower. Remove the two vertical bricks sticking out. We are either (a) left with an $L_{n-1}$ tower or (b) left with a $T_{n-1}$ tower with a horizontal brick lying on top. Remove the latter as well to obtain a proper $T_{n-1}$ tower.
From the last two paragraphs it follows that the $T_n$ and the $L_n$ satisfy the following recursion: $$T_n=T_{n-2}+2T_{n-1}+4L_{n-1},\qquad L_n=L_{n-1}+T_{n-1}\qquad(n\geq2)\ .\tag{2}$$ Eliminating the $L_n$ from $(2)$ we obtain $$T_n-3T_{n-1}-3T_{n-2}+T_{n-3}=0\qquad(n\geq3)\ .$$ The characteristic values of this recursion are $$\lambda_1=2+\sqrt{3}, \quad \lambda_2=2-\sqrt{3}, \quad \lambda_3=-1\ .$$ Using the values $(1)$ we finally obtain $$T_n={1\over6}(2+\sqrt{3})^n+{1\over3}(-1)^n+{1\over6}(2-\sqrt{3})^n\ ,$$ whereby the last summand can safely be ignored when $n\geq1$. This leads to the sequence $$1,2,9,32,121,450,\ldots\quad.$$
First some definitions:
For any $n > 0$, let $\mathcal{B}_n$ be the collection of covering of boxes of dimension $2 \times 2 \times n$.
For any $B_1 \in \mathcal{B}_p$, $B_2 \in \mathcal{B}_q$, we can "join" them together to obtain a $B_1B_2 \in \mathcal{B}_{p+q}$.
For any $B \in \mathcal{B}_n$, we call it irreducible if $B \ne B_1B_2$ for any $B_1 \in \mathcal{B}_p, B_2 \in \mathcal{B}_q$ where $0 < p, q \le n$.
Let $\mathcal{C}_n \subset \mathcal{B}_n$ be the collection of irreducible coverings of boxes of dimension $2 \times 2 \times n$.
It is easy to see there are three types of irreducible coverings.
there are two ways to place two dominoes to complete a single layer.
(counting from left to right, the $1^{st}$ and $2^{nd}$ figures in picture below)
there are four ways to place one domino into first layer.
After you do this, you place two domino vertically which stick out into second
layer. You can either use one more domino to complete the second layer
or place two more vertically which stick out into the third layer.
This process repeat, you obtain four irreducible coverings in each $\mathcal{B}_n$ for $n \ge 2$.
(the $3^{rd}$, $4^{th}$ and $5^{th}$ figures in picture)
$\hspace1in$ 
Combine this, we see
$$|\mathcal{C}_n| = \begin{cases} 2, & n = 1,\\ 5, & n = 2,\\ 4, & n > 2. \end{cases}$$
Translate this to generating function, the OGF for irreducible covering is
$$\text{OGF}_{\mathcal{C}}(z) \stackrel{def}{=} \sum_{n=1}^\infty |\mathcal{C}_n| z^n = 2z + \frac{4z^2}{1-z} + z^2$$
Since we can obtain any covering in $\mathcal{B}_?$ by joining coverings in $\mathcal{C}_?$ in a unique manner, the OGF for all coverings is
$$\begin{align} \text{OGF}_{\mathcal{B}}(z) \stackrel{def}{=} 1 + \sum_{n=1}^\infty |\mathcal{B}_n| z^n &= 1 + \sum_{k=1}^\infty \text{OGF}_{\mathcal{C}}(z)^k = \frac{1}{1 - \text{OGF}_{\mathcal{C}}(z)}\\ &= \frac{1}{1 - \left(2z + 4\frac{z^2}{1-z} + z^2\right)} = \frac{1-z}{1-3z-3z^2+z^3}\\ \end{align}$$
Let $\alpha = 2+\sqrt{3}$ and $\beta = 2-\sqrt{3}$, we can simplify RHS as
$$\frac{1-z}{(1+z)(1-4z+z^2)} = \frac{1-z}{(1+z)(1-\alpha z)(1-\beta z)} = \frac16\left(\frac{\alpha}{1-\alpha z} + \frac{\beta}{1-\beta z}\right) + \frac{1}{3(1+z)}$$
Expanding as a power series of $z$, we get
$$1 + \sum_{n=1}^\infty |\mathcal{B}_n| z^n = \text{OGF}_{\mathcal{B}}(z) = 1 + \sum_{n=1}^\infty \left[\frac16(\alpha^{n+1}+\beta^{n+1}) + \frac13 (-1)^n\right] z^n$$
This leads to
$$|\mathcal{B}_n| = \frac16 (\alpha^{n+1}+\beta^{n+1}) + \frac13(-1)^n\quad\text{ for } n \ge 1$$
Notice $|\beta | < 1$ implies $\left|\frac16\beta^{n+1} + \frac13(-1)^n\right| < \frac12$, above formula reduces to $$|\mathcal{B}_n| = \verb/NearestInteger/\left( \frac16 (2+\sqrt{3})^{n+1} \right)$$
Compute first few numbers of $|\mathcal{B}_n|$ explicitly, we have
$$|\mathcal{B}_1|, |\mathcal{B}|_2, \ldots = 2, 9, 32, 121, 450, 1681, 6272, 23409, \ldots$$
An OEIS search will lead you to OEIS A006253. Look at references there for more information.
Call the number of fillings of size $2 \times 2 \times n$ $T_n$. You can complete this to $n +1$ in 2 ways, and if there is a vertical box in the last layer when going to $n+ 2$, in 5 ways. Thus $T_{n + 2} = 2 T_{n + 1} + 5 T_n$. Add values for $T_0 = 1$ and $T_1 = 2$.
You can find a set of coupled recurrences. The trick is to make sure you count each configuration once. Imagine you are building a $2 \times 2 \times n$ brick with the $n$ direction vertical. Number the available positions $1$ to $4$. Require that each domino added fill the lowest number position in the lowest available layer. You can define a set of coupled recurrences for the number of ways to have $n$ full layers plus each possible configuration above the full layers. For example $a(n)$ is the number of ways to exactly fill $n$ layers. $b(n)$ is the number of ways to fill $n$ full layers plus positions $1$ and $2$ in the next layer. $c(n)$ is the number of ways to fill $n$ full layers plus two high in position $1$. I find twelve different possible configurations, so you will have twelve coupled recurrences. Many of them can be removed by substitution. According to OEIS, it is the closest integer to $(2+\sqrt 3)^n/6$ It will get much more complicated in more dimensions.
Here are my recurrences. The first column is the letter for the configuration. The next picture shows the height of that configuration above the last filled layer. The last column shows the recurrences between them. I numbered the cells starting with the upper left and going clockwise, so in configuration A you have to fill the upper left. There are three ways to do that, which take you to B, C, and H without filling a layer, so each of those has a term $A(n)$ in the recurrence. Similarly, if you are in B you can put a block lying down and get to A with one more full layer or put a block vertical and get to D, so D has a term $B(n)$ and A has a term $B(n-1)$. This matches OEIS A006253.
