Number of different ways of filling $N \times 4$ rectangle with Dominoes [duplicate]

Given a Nx4 (width = N and height = 4) rectangle. How many different ways are there to fill with Dominoes (2x1 or 1x2)?

I have found an OEIS sequence http://oeis.org/A005178 for this.

The recurrence given in the link is a(n) = a(n-1)+5*a(n-2)+a(n-3)-a(n-4).

Any combinatorial proof? or how to get the recurrence?

marked as duplicate by Ross Millikan, vonbrand, user127.0.0.1, user61527, mathematics2x2lifeFeb 6 '14 at 1:17

• $\text{height} = 4 \implies 4$ rows. The notation will not be $N \times 4$ but $4 \times N$ rectangle (or matrix). sorry for repeated edits. – hjpotter92 Sep 3 '13 at 11:57
• I get $f(3)=11$. – Barry Cipra Sep 3 '13 at 12:23
• Once you can agree on the first few values, look it up in the Online Encyclopedia of Integer Sequences. The problem has been much studied. The $3\times n$ problem is discussed at stackoverflow.com/questions/4803805/… and $4\times n$ at stackoverflow.com/questions/14295754/… – Gerry Myerson Sep 3 '13 at 12:27
• The problem is solved in The American Mathematical Monthly, Vol. 114, No. 6 (Jun. - Jul., 2007), pp. 554-556. Also solved in Klarner and Pollack, Domino tilings of rectangles with fixed width, Discrete Mathematics Volume 32, Issue 1, 1980, Pages 45–52, which may be available at sciencedirect.com/science/article/pii/0012365X80900989 – Gerry Myerson Sep 3 '13 at 12:34
• A recurrence is derived by Ronald C Read in A note on tiling rectangles with dominos, Fibonacci Quarterly, Feb. 1980, 24-27, freely available at mathstat.dal.ca/FQ/Scanned/18-1/read.pdf – Gerry Myerson Sep 3 '13 at 12:41

I posted this as an answer to another question, but since there is still no answer, I thought I would give you a general approach that allows to derive such recursive expressions for any tiling problem $m\times n$.

First, I wanted to consider a slightly different problem: how many "connected" tilings on $m\times n$. By "connected" I mean the ones so that every two consecutive columns are connected by at least one tile. Let's call us this function $g(n)$.

We want to consider $g(n)$ mainly for two reasons:

1. It should be much easier to derive, partly due to the fact that initial tiles will determine the rest of the tiling, and partly due to the second point.

2. It is going to be periodic, i.e. there is some non-periodic part $g(1),\dots,g(N)$, and then there is a periodic "tail": for $k\ge 1$: $g(N+k)=g(N+k+T)$ for some fixed $T$.

The second property allows us to derive $f$ easily from $g$. Indeed, for every tiling let $k\ge 1$ be the maximum number so that the first $k$ columns are connected. Then, for every $k$ every possible tiling can be constructed as a connected tiling on the first $k$ columns, and then any tiling on the rest. In other words, for every $m,n$: $$f(n)=g(1)f(n-1)+g(2)f(n-2)+\dots+g(n)f(0) \tag{1}$$ where $f(0)=1$.

Now, if $g$ has a non-zero periodic tail, then the expression (1) will grow with $n$, but we can consider (1) for two values $n$ and $n-T$, and by subtracting one from the other we will obtain an expression with fixed finite number of terms. We can even write down this expression explicitly, where $g()$ has $N$ non-periodic terms and period $T$: $$f(n)=g(1)f(n-1)+\dots+g(T-1)f(n-T+1)+[g(T)+1]f(n-T)+[g(T+1)-g(1)]f(n-T-1)+\dots+[g(T+N)-g(N)]f(n-T-N) \tag{2}$$.

Let's look at how it works for different smaller values of $m$.

Tiles on $1\times n$: $m=1$. The number of connected tilings on $1\times n$ ($g(n)$) equals: $0,1,0,0,0,\dots$. Here $N=2$, $T=1$, but the tail is all zeros, so we do not need (2) to eliminate the tail. (1) gives us: $f(n)=f(n-2)$ with two initial terms $f(0)=1,f(1)=0$.

Tiles on $2\times n$: $m=2$. $g(n\ge 1)$ equals: $1,1,0,0,0,\dots$. Indeed, there are no connected tilings on $2\times n$ for $n\ge 3$. Once again, $N=2$ and $T=1$ with zero tail. (1) gives us $f(n)=f(n-1)+f(n-2)$ with initial terms $f(0)=1,f(1)=1$. This is just Fibonacci numbers. BTW, if we used (2), we would obtain another recursive sequence for Fibonacci numbers: $f(n)=2f(n-1)-f(n-3)$ with initial terms $f(0)=1,f(1)=1,f(2)=2$.

Tiles on $3\times n$: $m=3$. Here where it gets interesting, because it is the first time we will have a non-zero $g$-tail. $g(n)=0$ for odd $n$. $g(2)=3$: ⨅ ⨆ and ≡. $g(4)=g(6)=\dots=2$ (assume first that horizontal tile connecting the first two columns is top or bottom and construct the rest of connected tiling in unique way). So, $g(n)$ is $0,3,0,2,0,2,\dots$. Now, $N=2$ and $T=2$ and we have to use (2): $f(n)=4f(n-2)-f(n-4)$.

Finally, tiles on $4\times n$: $m=4$. First, we need to show that $g(n)$ for $n\ge 1$ equals $1,4,2,3,2,3,\dots$. The first two values (non-periodic part) is given (among 5 tilings of $4\times 2$ only one is disconnected). For $n>2$ consider three possible combinations of horizontal/vertical tiles covering the first column:

|    --   --
|    |    --
--   |    |
--   --   |


and show that each leads to a unique connected covering, and only two of them work for odd $n$. In this case (2) gives us: $f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$.