# Number of ways to arrange small boxes of particular dimension in the large box

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.$$

• This seems somewhat difficult to understand . Can you please explain a bit more ? I apologise for my lack of knowledge . Jan 10, 2016 at 10:17
• There are many more shapes to consider. You can have more ragged shapes in between the ends. Jan 11, 2016 at 4:39
• @Ross Millikan: Above is a full solution along the proposed lines. I think I got it right. Jan 11, 2016 at 10:23
• @ChristianBlatter thanx :) Is there an easy way to extend this concept to 5 dimensional space ? I mean if we have empty box of (2*2*2*2*n) units, and objects of (1*1*1*1*2) units such that (8*n) objects are to be filled .. Then is there a generalised approach? Jan 11, 2016 at 17:28

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)

• there are one extra way to place four domino vertically to complete a double layer.
(the rightmost figure in picture)

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$$

$$|\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$$

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$.
• This does not take care of the case when you, e.g. , put a horizontal block in the first layer, then only vertical blocks for another $25$ layers, and finally close with a last horizontal block. Jan 10, 2016 at 19:35
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. 