14
$\begingroup$

After solving this problem from SPOJ (count the ways to fill a 4xn board with 2x1 dominoes) I found a different solution while searching on internet.

This solution uses the recurrence relation $f(n) = f(n-1)+5f(n-2)+f(n-3)-f(n-4)$ where $f(n)$ denotes the number of ways to fill the $4\times n$ board with $2 \times 1$ dominoes.

I don't fully understand how someone gets that kind of relation (I don't know almost anything of combinatorics or recurrence relations) but I think I understand something. The $f(n-1)$ term comes from observing that there is an unique way to fill the last column and the $5f(n-2)$ term comes from observing there are 5 different ways to fill the last two columns.

5 different ways

But i don't get where the terms $f(n-3)-f(n-4)$ come from. So I have two questions, the first one is where these terms come from and second I'd like to ask you for a reference to learn combinatorics and recurrence relations.

May you help me? Thanks in advance.

-edit-

For my solution I used a binary number to represent what configurations of the i-th column was valid. For example 1001 represent that rows 1 and 4 are blocked in the i-th row because in the (i-1)th there is an horizontal domino in that positions. I calculated all the valid transitions such binary numbers could go to (I did this by hand for all the binary numbers from 0000 to 1111). Then I got a function which I programmed using dynamic programming and a technique called bitmask to represent the binary numbers as integers. The function is:

$f(i,mask) = \begin{cases} 0 &\mbox{if } i = n, mask \neq 0 \\ 1 & \mbox{if } i = n, mask = 0. \\ \sum f(i+1,mask') &\mbox{else} \end{cases}$

Where mask' is taken from the set of all valid masks from where mask could transition to, also i=n means the first column outside the board as I considered 0-indexing. The code for that is here (this is not actually mine, it's from a mate but it's the exactly same idea).

$\endgroup$
  • $\begingroup$ Can you post your solution? I think the equation is simplified from something else $\endgroup$ – qwr Feb 5 '14 at 3:23
  • $\begingroup$ By the way, it's really great that you explain in your question what you'd done so far to solve the problem! Your explanation of the number 5 is almost spot on. The only thing is that tilings that end in the last pattern you drew contain the "only unique way to fill the last column", so you counted them already in $f(n-1)$. You'll see in my solution below that the fact that there are 5 $2\times 4$ patterns and that the recursion includes $5f(n-2)$ is a slight coincidence. It comes from the 4 patterns you didn't count in $f(n-1)$, and the fifth $f(n-2)$ comes into the formula from elsewhere. $\endgroup$ – Steve Kass Feb 5 '14 at 5:31
  • $\begingroup$ @Cybuster, Can you add code link ? Given link is broken , $\endgroup$ – T.J. Apr 9 '17 at 13:06
21
$\begingroup$

There are eight ways in which a $4\times n$ tiling can begin, shown and named in the picture below. We'll count the number with each kind of beginning configuration and add the results up to get $f(n)$.

enter image description here

Types A through E are easy. Any $4\times (n-1)$ tiling can extend A to give a $4\times n$ tiling, and there are no other ways to get a "type A" $4\times n$ tiling. So there are $f(n-1)$ "type A" $4\times n$ tilings. Similarly, there are $f(n-2)$ type B $4\times n$ tilings, and $f(n-2)$ as well of each of the types C, D, and E. That's $f(n-1)+4f(n-2)$ so far.

Tilings with starting configurations F, G, and H are a little harder to count. First define some helpful notation.

Let $f_T(k)$ represent the number of $4\times k$ tilings of type T, where T is a set of starting configurations. That lets us say from what we have above that $$f(n)=f(n-1)+4f(n-2)+f_{\{F,G,H\}}(n)\textrm.$$ We just have to figure out $f_{\{F,G,H\}}(n)$ in terms of $f$.

Clearly $f_{\{F,G,H\}}(n)=f_{\{F\}}(n)+f_{\{G\}}(n)+f_{\{H\}}(n)$; we'll compute each term separately. Also take note of the fact that $f(k)=f_{\{A,B,C,D,E,F,G,H\}}(k)$.

Now on to the counting. We'll look at type F first.

A "type F" $4\times (n)$ tiling is always configuration F extended by a "type B" or "type F" $4\times (n-2)$ tiling that has its center left domino removed. So $f_F(n)$ is exactly the number of $4\times (n-2)$ "type B" or "type F" tilings, that is, $f_F(n)=f_{\{B,F\}}(n-2)$. (The type B and F tilings are exactly the ones that have a center left domino to remove.)

A "type G" tiling is G extended by a tiling of type A, C, or G, with the lower left domino removed, so $f_G(n)=f_{\{A,C,G\}}(n-2)$. (A, C, and G are the tiling types with a lower left domino.)

A "type H" tiling is H extended by a tiling of type A, D, or H, with the upper left domino removed. So $f_H(n)=f_{\{A,D,H\}}(n-2)$. (A, D, and H are the tiling with an upper left domino.)

Substituting these last three expressions into the previous displayed equation yields

$\begin{align*} f(n)&=f(n-1)+4f(n-2)+f_{\{B,F\}}(n-2)+f_{\{A,D,H\}}(n-2)+f_{\{A,C,G\}}(n-2)\\ &=f(n-1)+4f(n-2)+f_{\{A,B,C,D,F,G,H\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+4f(n-2)+f(n-2)-f_{\{E\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+5f(n-2)+f_{\{A\}}(n-2)-f_{\{E\}}(n-2) \end{align*}$

Fortunately, A and E are the simplest patterns, and we know from our initial calculations (which we did before adopting the subscript notation on $f$) that $f_{\{A\}}(n-2)= f(n-3)$ and $f_{\{E\}}(n-2)= f(n-4)$. These final calculations give the recurrence relation you asked about: $$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)\textrm.$$

I'll let someone else suggest good references for learning these techniques and just say experience helps. The hundredth one is a lot quicker to figure out than the first one!

$\endgroup$
  • $\begingroup$ I spend some time thinking how you got the f_F, f_G and f_H and I think now I got it, thanks! $\endgroup$ – Cybuster Feb 5 '14 at 6:18
  • $\begingroup$ I'd omitted the words or "type F" in explaining how to figure out $f_{\{F\}}(n)$. The intermediate calculations were right, but the explanation missed mentioning a term. Fixed now. $\endgroup$ – Steve Kass Feb 5 '14 at 6:30
  • $\begingroup$ Very nice solution $\endgroup$ – qwr Feb 5 '14 at 21:02
  • 1
    $\begingroup$ I think that the reasoning for type G and type H are swapped: type G is extending on the lower side, so it would be extended by A, C, G with the lower left removed. $\endgroup$ – thesamet Jul 9 '18 at 6:59
  • 1
    $\begingroup$ Thanks, @thesamet. I think I fixed the error. $\endgroup$ – Steve Kass Jul 9 '18 at 18:26
3
$\begingroup$

I am not sure I can intuitively explain this recursive formula by itself (and don't think there is an easy explanation without going into numerous cases), but I wanted to 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)$.

$\endgroup$
1
$\begingroup$

The answer is here: A127864 or A077917.

The actual formula is: $f(n) = f(n-1) + 4 f(n-2) + 2 f(n-3)$. The sequence is: $1, 5, 11, 33, \dots$.

$\endgroup$
  • 1
    $\begingroup$ It's actually this one: oeis.org/A005178 (note the 4th term is 36) $\endgroup$ – apnorton Oct 22 '16 at 0:31
  • $\begingroup$ the 4th term cannot be 36. Here I draw all the 33 variants for F(4). Look. "uploads.ru/AORLC.jpg". If I missed something, please, let me know. $\endgroup$ – Roman Zinchenko Dec 4 '16 at 12:16
  • $\begingroup$ @apnorton Here is a clickable link: link $\endgroup$ – Roman Zinchenko Dec 5 '16 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.