Создание прямоугольника размера NX2 с Dominos и L-образными тромминами [дубликат]

Question

<в сторону CLASS="S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль= «Статус»>

Этот вопрос уже имеет ответ здесь :

Домино и Тромино Комбинированное плитка (1 ответ)

Закрыто 4 месяца назад .

Answer 1

.
• Пусть $ f [m] $ - количество способов покрытия формы, показанной ниже, $ m $ по $ 2 $ прямоугольник. Наша конечная цель - $ f [n] $ .

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

.

.
• Пусть $ g [m] $ - количество способов покрытия первой формы, показанной ниже, $ m $ по $ 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] $ . У нас есть следующие 2 способа покрыть крайнее пространство первой формы.

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

.

Итак, у нас есть $ \ Quad \ Quad g [m]= f [m - 1] + g [m - 1] $ для $ 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 \ turs2 $ , один элементарный блок $ 2 \ Times2 $ И два элементарных блока $ n \ turs2 $ для $ n \ ge3 $ . Пусть $ f (n) $ - количество шаблонов для $ 2 \ RUE N $ . У нас есть следующие базовые случаи и рецидива, $$ f (0)= 1, \ f (1)= 1, \ f (2)= 2, $$ $$ f (n)= f (n - 1) + f (n-2) + 2f (N-3) + 2F (N-4) + \ CDOT + 2F ( 0), \ Text {for} n \ ge3 $$

Вышеуказанные формулы приводят к алгоритму, который вычисляет $ f (n) $ с $ O (n ^ 2) $ Сложность времени и $ O (n) $ Space-сложность.

Мы можем сделать лучше. Замена $ 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) $ space-сложность.

# 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 $ AULL в $ 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 $ удовлетворяет

Один и тот же тип рецидивов, то есть, $ f [m]= 2f [M - 1] + f [m-3] $ .Проверка действительного диапазона индекса $ m $ , мы видим, что это значение для всех $ m \ ge3 $ .

Answer 2

Один из способов подумать о том, что он будет элементарными блоками, то есть блоки, которые нельзя разделить, резка их вертикально.

.
• есть один элементарный блок размера 1x2 (один вертикальный b).
• есть один элементарный блок размера 2x2 (два горизонтальных BS).
• Есть два элементарных блока размера 3x2 (последние два, показанные на вашем рисунке, пример I).
• Есть два элементарных блока размера 4x2 (они оба появляются в финальном рисунке примера II).
• В общем, есть два элементарных блока размера $ n \ Times 2 $ , $ n \ ge 3 $ $ .

Теперь, $ n \ Times 2 $ Rectangle можно разделить на два меньших блока, резком направляющему правый элементарный блок. (Это включает в себя случай, когда элементарный блок является весь прямоугольник).

.
• прямоугольник 0x2 может быть чередуется в 1 путь .
• Из прямоугольника 1x2 мы можем резать самый правый элементарный блок (у нас есть 1 из них), и мы остались с прямоугольником 0x2, поэтому его можно чередуться в 1 WINT .
• от прямоугольника 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 способов .

Таким образом, вы можете работать до 10х2.

После вычисления нескольких терминов я обнаружил, что последовательность - a052980 в онлайн-энциклопедии целочисленных последовательностей :

A (n) - это количество возможных наклон доски 2 x n, используя домино и L-образные тройцы. - Майкл Тулских, 21 августа 2019 г.

Так что окончательный ответ 1255 для $ n= 10 $ .