-1
$\begingroup$

The Question is from DP tiling a 2xN tile with L shaped tiles and 2x1 tiles? I want an explanation about this question or theory

$\endgroup$
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I suggest you look at cs.stackexchange.com/questions/tagged/tiling and cs.stackexchange.com/tags/dynamic-programming/info. $\endgroup$ – D.W. May 26 at 4:42
  • $\begingroup$ cs.stackexchange.com/q/85611/755 $\endgroup$ – D.W. May 26 at 4:44
  • 1
    $\begingroup$ Please credit the source for all copied material. $\endgroup$ – D.W. May 26 at 4:46
  • 1
    $\begingroup$ By removing the majority of your question, you have caused some problems for my answer since it refers to the picture and some terms used in there. The moderator asked you to credit/reference your source, not to remove everything ... $\endgroup$ – Glorfindel May 26 at 13:38
  • $\begingroup$ My bad, I just want to insert a credit but fail to delete all of the content $\endgroup$ – Anon May 26 at 16:02
3
$\begingroup$
  • Let $f[m]$ be the number of ways to cover the shape shown below, an $m$ by $2$ rectangle. Our ultimate goal is $f[n]$.
     ┌───────────┐
   2 │           │ 
     └───────────┘
          m
  • Let $g[m]$ be the number of ways to cover the first shape shown below, an $m$ by $2$ rectangle with an extra 1x1 square at the top-right corner. By symmetry, $g[m]$ is also the number of ways to cover the second shape shown below.
           m+1                     m
     ┌─────────────┐        ┌───────────┐
   2 │           ┌─┘      2 │           └─┐
     └───────────┘          └─────────────┘
          m                        m+1

To find the recurrence relation, try covering the space at the rightmost boundary of the above shapes in all possible ways.

Consider $f[m]$. We have the following 4 ways to cover the rightmost space.

              ┌─────────┬─┐     ┌──────┬────┐     ┌───────┬───┐     ┌─────────┬─┐
              │         │ │     │      ├────┤     │       └─┐ │     │       ┌─┘ │
              └─────────┴─┘     └──────┴────┘     └─────────┴─┘     └───────┴───┘
What is left:   (m-1)x2         (m-2)x2            (m-2)x2+1         (m-2)x2+1

So, we have $\quad\quad f[m] = f[m - 1] + f[m - 2] + g[m - 2] \cdot 2 $ for $m\ge2$.

Consider $g[m]$. We have the following 2 ways to cover the rightmost space of the first shape.

                     m+1                 m+1
               ┌─────────┬───┐     ┌─────────┬───┐
               │         │ ┌─┘     │         └─┬─┘
               └─────────┴─┘       └───────────┘
 What is left:   (m-1)x2              (m-1)x2+1

So we have $\quad\quad g[m] = f[m - 1] + g[m-1]$ for $m\ge1$.

Applying the above two recurrence equations, we can compute all $f[m]$ and $g[m]$, in order of increasing $m$, starting from $m=2$, given the initial conditions, $f[0]=1$, $f[1]=1$, $g[0]=0$ and $g[1]=1$.

# Python program to compute the first n+1 values of f 
def show_number_of_ways(n):
    f = [0] * (n+1)
    g = [0] * (n+1)
    f[0] = f[1] = g[1] = 1
    g[0] = 0
    for m in range(2, n+1):
        f[m] = f[m - 1] + f[m - 2] + 2 * g[m - 2]
        g[m] = f[m - 1] + g[m - 1]
    print(f)

show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255] 

Here is a way to derive a simpler recurrence relation that involves $f$ only.

Glorfindel's answer explains how to compute the number of patterns by "cutting the rightmost elementary block." To recap, there are one elementary block of size $1\times2$, one elementary block of $2\times2$ and two elementary blocks of $n\times2$ for $n\ge3$. Let $f(n)$ be the number of patterns for $2\times n$. we have the following base cases and recurrence relation, $$f(0)=1,\ f(1)=1,\ f(2)=2,$$ $$f(n)=f(n-1)+f(n-2)+2f(n-3)+2f(n-4)+\cdots+2f(0),\text{ for }n\ge3 $$

The above formulas leads to an algorithm that computes $f(n)$ with $O(n^2)$ time-complexity and $O(n)$ space-complexity.

We can do better. Replacing $n$ with $n-1$, we have $$f(n-1)=f(n-2)+f(n-3)+2f(n-4)+2f(n-5)+\cdots+2f(0),\text{ for }n\ge4 $$

Subtracting the above two equations, we get $$f(n)-f(n-1)=f(n-1)+f(n-3)$$ So we have for $n\ge4$, $$f(n)=2f(n-1)+f(n-3)\tag{simple}$$ Since $f(3)=5=2f(2)+f(0)$, the above recurrence relation holds for all $n\ge3$. This leads to an algorithm that computes $f(n)$ with $O(n)$ time-complexity and $O(1)$ space-complexity.

# Python program to compute the first n+1 values of f
def show_number_of_ways(n):
    f = [0] * (n+1)
    f[0] = f[1] = 1
    f[2] = 2
    for i in range(3, n+1):
        f[i] = 2 * f[i - 1] + f[i - 3]
    print(f)

show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255] 

We can also derive the simple recurrence relation directly from the first two mutual recursive relations between $f$ and $g$.

The equality $g[m] = f[m - 1] + g[m-1]$ tells us $f[m-1] = g[m]-g[m-1]$, and, hence, $f[m] = g[m+1]-g[m]$ and $f[m-2] = g[m-1]-g[m-2]$. Applying them to eliminate $f$ away in $f[m] = f[m - 1] + f[m - 2] + g[m - 2] \cdot 2$, we get $g[m+1]=2g[m]+g[m-2]$.

Since $f[m]$ is a linear combination of $g[m+1]$ and $g[m]$, $f$ satisfies the same kind of recurrence relation, i.e., $f[m]=2f[m-1]+f[m-3]$. Checking the valid range of the index $m$, we see that it is value for all $m\ge3$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

One way to think of it would be elementary blocks, i.e. blocks that cannot be split by cutting them vertically.

  • There's one elementary block of size 1x2 (one vertical B).
  • There's one elementary block of size 2x2 (two horizontal Bs).
  • There are two elementary blocks of size 3x2 (the last two shown in your figure, Example I).
  • There are two elementary blocks of size 4x2 (they both appear in the final pattern of Example II).
  • In general, there are two elementary blocks of size $n \times 2$, $n \ge 3$.

Now, an $n \times 2$ rectangle can be divided into two smaller blocks by cutting the rightmost elementary block. (This includes the case where the elementary block is the entire rectangle).

  • A 0x2 rectangle can be tiled in 1 way.
  • From a 1x2 rectangle, we can cut the rightmost elementary block (we have 1 of them) and we're left with a 0x2 rectangle, so it can be tiled in 1 way.
  • From a 2x2 rectangle, we can either cut a 2x2 block (1 way) or cut a 1x2 block and be left with a 1x2 rectangle (1 * 1 = 1 way), for a total of 2 ways.
  • From a 3x2 rectangle:
    • cut a 3x2 block (2 ways)
    • cut a 2x2 block (1 way) and be left with a 1x2 rectangle (1 way)
    • cut a 1x2 block (1 way) and be left with a 2x2 rectangle (2 ways)
    • Total: 2 + 1 * 1 + 1 * 2 = 5 ways.

This way, you can work all the way to 10x2.

After computing a few terms, I found the sequence is A052980 in The On-Line Encyclopedia of Integer Sequences:

a(n) is the number of possible tilings of a 2 X n board, using dominos and L-shaped trominos. - Michael Tulskikh, Aug 21 2019

so the final answer is 1255 for $n=10$.

| cite | improve this answer | |
$\endgroup$

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