Combination of $2\times 1\times 1$ cubes inside a $3\times 3\times n$ cube I came along this question in my math book and I can't seem to figure it out.
I searched for packing problems, but i couldn't find the answer.
You have a block with a width of $3$, depth of $3$ and a height $n$
Given height $n$, in how many ways can you fill this block with smaller blocks of $2 \times 1 \times 1$?
 A: Consider the cross-section $S_r$ at height $r\geq0$ of your $3\times3\times n$-tower. Assume you have built the tower up to height $r$. Some of the $2\times1\times1$-sticks filling the first $r$ layers  will cross the level $S_r$ and protrude into the $r+1$st layer of the tower. These sticks determine a certain subset $A$ of the $9$ squares of $S_r$. The set ${\cal P}$ of all these subsets has cardinality $2^9=512$. For each $A\in{\cal P}$  you have to determine all possibilities to lie further sticks horizontally into the $r+1$st layer (this can be done once and for all), and for each of these possibilities you have to put vertical sticks at all empty spaces in the $r+1$st layer, creating a new pattern $A'$ of protruding sticks in $S_{r+1}$.
Denote by $P_r(A)$ $\>(r\geq0)$ the number of possible arrangements up to $S_r$ with protruding pattern $A$. Then $P_0(\emptyset)=1$ and $P_0(A)=0$ for all $A\ne\emptyset$. The counting work you have done now allows you to set up a linear recursion scheme
$$P_{r+1}(A')=\sum\nolimits_{A\in{\cal P}} c_{A A'} P_r(A)\ ,$$
where the $512\times512$ coefficients $c_{A A'}\in{\mathbb N}_{\geq0}$ have been determined in the counting process described above.
