Brick wall with maximum height 3

Question

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.

Answer 1

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.