【問題】骨牌拼3xn長方形的方法

[夢境的行旅 10]

在這篇文章的 #11 樓回文中，howt 指出用1x2 的骨牌排 2 x n 的方法數G(n) = F(n-1)

其中F(n) 是費氏數列。我遇過的另一個問題是拼3 x n長方形，是某數學競賽考古題。在建立遞迴關係的時候發現想法不充分(也就是說「我不會」)，希望能聽聽各位的想法。

=============================================================================

先說目前(失敗)的作法

明顯3 x n 的面積要是偶數，也就是n是偶數才能用面積2的骨牌排滿

＃ 3 x 2 的排法一共有左邊三種 f(2)=3

＃ 3 x 4 的排法可以拆成兩個3 x 2 = 9種，或者像圖左邊的形狀一樣，一共正反兩種。f(4)=11

我把左圖稱為「全相連 - 4」，注意到不管是3 x 6 、 3 x 8 ......都只有2種「全相連」的排法，不能變化，例如將中間兩個淺綠色骨牌變成直立，就和2 + 2 中的一種圖形相同

＃ 3 x 6 的狀況可以窮舉

2 + 2 + 2 , 2 + 4- 全連 , 6- 全連 一共

f(2) ^3 + 2 x f(2) x 2 + 2 = 27 + 12 + 2 = 41種排法

＠＠ 有了以上的基礎，能不能把 f (6) 利用 f (2) 和 f (4) 表達出來，得到遞迴關係呢？

單純一點，可以想成由長方型左邊開始取，可以寫成 f(6)=f(2) x f(4) + f(4) x f(2) + 2 (兩種全部相連排法)

計算一下發現 上式得到排法卻是 68種 。多出了27種 !!! 為什麼會出錯呢???

那是因為有種情形被重複計算了兩次 2 + 2 + 2 同時在 f(2) x f(4) 和 f(4) x f(2) 的子情形出現了。因此這種遞迴式失敗。

然後就卡關了。 根據窮舉，接下來的 f (8) = 153 f (10) = 535 不知道對你的解題有沒有幫助？

[howt 10]

恕刪

令F(n)=f(2n)

這邊用遞迴的方式

是考慮長2n時，把所有可能的方法都從某一邊開始看，

先"恰"分成 2與2n-2，2的有3種方法，因此此時有3*F(n-1)種

再考慮"恰"分成 4與2n-4來看，4的僅2種(不包含分成2與2，因為這與上面重複)

因此此時有2*F(n-2)種

同理 6與 2n-6 有 2*F(n-3)種

以此類推

可得 F(n) = 3*F(n-1)+2*F(n-2)+2*F(n-3)+2*.......+2，F(1)=3與F(2)=11視為初始值

(最後的+2即是你所指的全相連)

F(2) - F(1) = 2F(1) + 2

F(3) - F(2) = 2F(2) + [ 2F(1) + 2] = 3F(2) -F(1)

F(4) - F(3) = 2F(3) + [2F(2)+2F(1)+2] = 3F(3) - F(2)

F(5) - F(4) = 2F(4)+ [ 2F(3)+2F(2)+2F(1)+2] = 3F(4) - F(3)

.........

F(n+1) = 4F(n)-F(n-1)，F(1)=3，F(2)=11

解上述遞迴即可得 F(n) ，從而得f(n)

若有誤請指正

另外： f (10) 應該是571 ，我沒用窮舉驗算，麻煩你了 -...-

[夢境的行旅 10]

一般式是(1/2 +√3/6) * (2+√3)^n + (1/2 -√3/6) * (2-√3)^n

也就是 (1+√3/3) * (2+√3)^n 的整數係數