用DominoS和L形Trominos构建大小Nx2的矩形[重复]

Question

这个问题已经在这里有一个答案：

Answer 1

let $ f [m] $ 是覆盖下面所示形状的方法的数量，AN $ M $ by $ 2 $ 矩形。我们的最终目标是 $ F [n] $ 。

     ┌───────────┐
   2 │           │ 
     └───────────┘
          m

.

let $ g [m] $ 是覆盖下面显示的第一个形状的方法数，一个 $ m $ by $ 2 $ 矩形，右上角有一个额外的1x1平方。通过对称性， $ g [m] $ 也是覆盖下面所示的第二形状的方法数。

           m+1                     m
     ┌─────────────┐        ┌───────────┐
   2 │           ┌─┘      2 │           └─┐
     └───────────┘          └─────────────┘
          m                        m+1

. 要找到复发关系，请尝试以所有可能的方式覆盖上述形状的最右边边界的空间。

考虑 $ f [m] $ 。我们有以下4种方式来覆盖最右边的空间。

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

.

所以，我们有 $ \ quad \ quad f [m]= f [m-1] + f [m-2] + g [m - 2] \ cdot 2 $ $ m \ ge2 $ 。

考虑 $ g [m] $ 。我们有以下两种方式来覆盖第一个形状的最右边空间。

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

. 所以我们有 $ \ quad \ quad g [m]= f [m - 1] + g [m-1] $ for $ m \ ge1 $ 。

应用上述两个复发方程式，我们可以计算所有 $ f [m] $ 和 $ g [m] $ ，按顺序增加 $ m $ ，从 $ m= 2 $ ，给定初始条件， $ f [0]= 1 $ ， $ f [1]= 1 $ ， $ g [0]= 0 $ 和 $ 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] 

.

---

这里是一种衍射更简单的复发关系的方法，它涉及 $ f $ 。

glorfindel的答案如何通过“切割最右边的小组”来计算模式数量。 要回顾，有一个基本的大小块 $ 1 \ times2 $ ， $ 2 \ time2 $ 以及 $ n \ times2 $ for $ n \ ge3 $ 的两个基本块。让 $ f（n）$ 是 $ 2 \ times n $ 的模式数。我们有以下基本案例和复发关系， $$ 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 $$

上述公式导致算法，计算 $ f（n）$ 使用 $ o（n ^ 2） $ 时间复杂度和 $ o（n）$ 空格复杂性。

我们可以做得更好。替换 $ n $ 使用 $ n-1 $ ，我们有 $$ f（n-1）= f（n-2）+ f（n-3）+ 2f（n-4）+ 2f（n-5）+ \ cdots + 2f（0），\ text {for} n \ ge4 $$

减去上述两个等式，我们得到 $$ f（n）-f（n-1）= f（n-1）+ f（n-3）$$ 所以我们有 $ n \ ge4 $ ， $$ f（n）= 2f（n-1）+ f（n-3）\ tag {simple} $$ 由于 $ F（3）= 5= 2F（2）+ F（0）$ ，上述复发关系适用于所有 $ n \ ge3 $ 。 这导致算法计算 $ f（n）$ 使用 $ o（n）$ 时间 - 复杂性和 $ O（1）$ 空间复杂性。

# 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] 

.

---

我们还可以直接从 $ f $ 和 $ g之间的前两个相互递归关系中的简单复发关系$ 。

相等 $ g [m]= f [m - 1] + g [m-1] $ 告诉我们 $ f [m-1]= g [m] -g [m-1] $ ，而且，因此， $ f [m]= g [m + 1] -g [m] $ 和 $ f [m-2]= g [m-1] -g [m-2] $ 。应用它们消除 $ f $ 离开 $ f [m]= f [m - 1] + f [m - 2] + g [m - 2] \ cdot 2 $ ，我们得到 $ g [m + 1]= 2g [m] + g [m-2] $ 。

由于 $ f [m] $ 是 $ g [m + 1] $ $ g [m] $ ， $ f $ 满意

ES同样的复发关系，即 $ f [m]= 2f [m-1] + f [m-3] $ 。检查索引 $ m $ 的有效范围，我们看到它是所有 $ m \ ge3 $ 。

Answer 2

一种思考它将是基本块，即不能通过垂直切割而拆分的块。

• 有一个基本尺寸1x2（一个垂直b）。
• 有一个基本尺寸2x2（两个水平bs）。
• 有两个大小的尺寸3x2（图中所示的最后两个块，示例一）。
• 有两个大小的尺寸4x2（它们都出现在示例II的最终图案中）。
• 一般来说，有两个基本的大小块 $ n \ times 2 $ ， $ n \ ge 3 $ 。

现在，a $ n \ times 2 $ 矩形可以通过切割最右边的小组块分成两个较小的块。 （这包括基本块是整个矩形的情况）。

• 一个0x2矩形可以在 1途中铺张，。
• 从1x2矩形中，我们可以剪切最右边的小组（我们有1个），我们留下了一个0x2矩形，因此它可以在 1路上铺张平铺。
• 从2x2矩形中，我们可以剪切2x2块（1路）或剪切1x2块，并用1x2矩形（1 * 1= 1路）留下，总共 2种方式< /强>。
• 从3x2矩形：
  • 剪切3x2块（2种方式）
  • 剪切2x2块（1路），留下1x2矩形（1路）
  • 剪切1x2块（1路），留下2x2矩形（2种方式）
  • 总计：2 + 1 * 1 + 1 * 2= 5种方式。

这样，您可以一直到10x2。

在计算几个术语后，我发现序列是 a052980 在整数序列的在线百科全书中：

a（n）是使用多米诺骨和L形trominos的2 x N板的可能倾斜的数量。 - 2019年8月21日的Michael Tulskikh

所以最终答案是 1255 $ n= 10 $ 。