Is there a standard recurrence relation to solve this? 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 ? 
 A: 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.
A: 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!
