You have a block with a width of 3, depth of 3 and a height n  

Given n, in how many ways can you fill this block with smaller blocks of 2 x 1 x 1?


if n is uneven, one 1x1x1 block will be unused. This is allowed.



Combination of 2 × 1 × 1 cubes inside a 3 × 3 × n cube
For simplicity, I'll assume $n$ is even. Each horizontal slice of the $3 \times 3 \times n$ block can have a finite number of "states". Each state consists of a packing of the $3 \times 3$ square with $2 \times 1$ blocks (in either orientation) and $1 \times 1$ blocks, where the $1 \times 1$ blocks are labelled either ``$+$ or $-$''. The lowest slice is not allowed to have any $-$, the highest slice is not allowed any $+$, and each $+$ must be paired with a $-$ in the next higher level. If there are $N$ states $1 \ldots N$, let $A$ be the
adjacency matrix: $A\_{ij} = 1$ if state $i$ in one level is compatible with
state $j$ in the next level, $0$ otherwise. Let $L$ and $H$ be the column vectors
of $0$'s and $1$'s indicating states that are possible in the lowest and highest
levels respectively. Then the number of ways is $L^T A^{n-2} H$. The eigenvectors and eigenvalues of $A$ can be used to compute this.


