4xN多米诺骨牌砖的组合数

4xN多米诺骨牌砖的组合数

解决一个更普遍的问题。找到在顶部行中的某些位置可能会被占用的4×N网格的平铺方法。将每个位置的2的幂次幂与最左端的1，第二个2，第三个4，最右端的8相关联。设

T(N,k)

4×N网格的平铺数，其中

k

与上一行相对应的位置已被占用。

k== 0

表示没有位置被占用，

k == 6

表示两个中间位置被占用（6 = 2 + 4）等。

然后，在填充第一行的其余部分时找到过渡，下一行中的哪些模式可以通过几种方式访问​​？

例如，如果居中的两个位置被占用，则填充顶行其余部分的唯一方法是将多米诺骨牌垂直放置在最左边和最右边的位置，从而导致

|xx||  |

和一种结构，其中的下一行中的两个最外侧位置都被占用，则对应于

1+8 = 9

，所以

T(N,6) = T(N-1,9)

。对于

k ==9

，我们从外观开始

|  |

我们有两种可能性，

|==|     ||||          ||

我们可以通过水平放置一个多米诺骨牌，使下一排完全自由，或者垂直放置两个多米诺骨牌，占据下一排的两个中间位置来填补空白。

T(N,9) = T(N-1,0) + T(N-1,6)

使用这些转换来构建的表

T(n,k)

。

您要查找的值是

T(N,0)

。