Brick wall with maximum height 3 Given n same-sized rectangular bricks. We want to build a wall with these constraints:

*

*All bricks should be horizontal.

*We can put a brick on two other bricks, such that the middle of the top brick is on the border of two other bricks.

*The maximum height of the wall should be 3.

*Bricks on the first row (the ground) should stick together.

For example, if we have 4 bricks, we can build the wall in 3 ways. If we have 6 bricks, we can make the wall in 9 ways.
Some examples of this recursive function are:
$f(1) = {0 \choose 0} = 1$
$f(2) = {1 \choose 1} = 1$
$f(3) = {2 \choose 0} + {1 \choose 1} = 1 + 1 = 2$
$f(4) = {3 \choose 0} + {2 \choose 1} = 1 + 2 = 3$
$f(5) = {4 \choose 0} + {3 \choose 1} + {2 \choose 2} = 1 + 3 + 1 = 5$
$f(6) = {5 \choose 0} + {4 \choose 1} + {3 \choose 2} + {2 \choose 2}{1 \choose 1} = 1 + 4 + 3 + 1 = 9$
This is the illustration of how we can build the wall using 6 bricks:

I tried to find a recurrence relation for this problem, but I didn't succeed.
 A: This is only a partial answer, deriving a sixth-order linear recurrence.
A wall with $k$ bricks in the bottom row can be decomposed into $k$ diagonals with slope $-1$. The first diagonal contains only the leftmost brick in the bottom row. After that each diagonal can be at most one brick longer than the previous one, up to a maximum length of $3$ bricks. Thus, we are in effect counting the sequences $\langle a_1,\ldots,a_k\rangle$ such that

*

*$a_i\in\{1,2,3\}$ for $i=1,\ldots,k$,

*$a_1=1$,

*$a_{i+1}-a_i\le 1$ for $i=1,\ldots,k-1$, and

*$a_1+\ldots+a_k=n$.

Let $b_n$ be the number of such sequences, and for $i=1,2,3$ let $b_{n,i}$ be the number of such sequences ending in $i$. Then
$$\begin{align*}
b_{n,3}&=b_{n-3,2}+b_{n-3,3}=b_{n-3}-b_{n-3,1}\\
b_{n,2}&=b_{n-2}\\
b_{n,1}&=b_{n-1}\,,
\end{align*}$$
so
$$\begin{align*}
b_{n}&=b_{n,1}+b_{n,2}+b_{n,3}\\
&=b_{n-1}+b_{n-2}+b_{n-3}-b_{n-3,1}\\
&=b_{n-1}+b_{n-2}+b_{n-3}-b_{n-4}\,,
\end{align*}$$
with initial values $b_0=1$, $b_1=1$, $b_2=1$, $b_3=2$, $b_4=3$, and $b_5=5$. The next few values are easily computed:
$$\begin{array}{rcc}
n:&0&1&2&3&4&5&6&7&8&9&10\\
b_n:&1&1&1&2&3&5&9&15&26&45&77
\end{array}$$
By the way, if the height were limited to $2$, we would simply be getting the Fibonacci numbers.
