algorithm - 用 2x1 多米诺骨牌拼贴 3xn 矩形有多少种方法？

Question

每天我都在与算法问题作斗争，并尝试在这里问我无法回答的问题。对不起，如果我引起任何头痛。总之，

这是 problem来自滑铁卢大学 ACM 编程竞赛。

In how many ways can you tile a 3xn rectangle with 2x1 dominoes?

必杀技:闻起来像递归精神

Answer 1

只是对 taskinoor 的回答中隐含给出的方程式的显式解:

或者

f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) + 
     (1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3]) 

如果有人关心。

让我们展示 10 个值(对于奇数 n 没有解决方案){n,f[n]}:

{6, 41.},   
{12, 2131.},   
{18, 110771.},   
{24, 5.75796*10^6},   
{30, 2.99303*10^8},   
{36, 1.5558*10^10}, 
{42, 8.08717*10^11},  
{48, 4.20377*10^13}, 
{54, 2.18515*10^15}, 
{60, 1.13586*10^17}