Is there a standard recurrence relation to solve this?

Question

I have infinite supply of $m\times 1$ and $1\times m$ bricks.I have to find number of ways I can arrange these bricks to construct a wall of dimensions $m\times n$.

My problem is how can I approach the question? Is there a recurrence relation to describe the problem ?

Answer 1

To make the solution simpler, consider two simultaneous recurrence relations. Let $a_n$ be the number of possible walls of dimension $m \times n$ with the last position having a $m\times 1$ brick. Let $b_n$ be the number of possible walls of dimension $m \times n$ with the last $m$ positions having $1\times m$ bricks.

Then, the recurrences are: \begin{align*} a_n &= a_{n-1}+b_{n-1}\\ b_n &= a_{n-m}+b_{n-m} \end{align*} with initial conditions: \begin{align*} a_0&=a_1 =a_2=\cdots = a_{m-1}=1\\ b_0&=b_1 =b_2=\cdots = b_{m-1}=0 \end{align*} and the total number of ways to build the wall is given by $a_n+b_n$ Then we can work on combining the recurrences to a single relation, get a generating function etc.

As an example, when $m=3$, the sequence we get is:

$1 , 1 , 1 , 2 , 3 , 4 , 6 , 9 , 13 , 19 , 28 , 41 , 60 , 88 , 129 , 189 , 277 , 406 , 595 , 872, \ldots$

and taking it to oeis gives A000930, which is indeed the required sequence.

Answer 2

Hint. A recurrence relation would be a good idea.

• Place an $m\times1$ brick along the side of length $m$. What do you now have to do to complete the construction of the wall?

• Are there any other ways that you could have started?

Good luck!