作者Honor1984 (奈何上天造化弄人？)
看板Math
標題Re: [其他] 請教一題離散數學
時間Fri Nov 10 05:51:10 2023
※ 引述《skyfan2008 (la..la..)》之銘言：
: 題目
: Let a_n count the number of ways to tile a 4xn chessboard using
: horizontal(1x2) dominoes which can also be used as vertival(2x1).
: Find and solves a recurrence relation for a_n.
: 若tile a 2xn chessboard
: 它的遞迴式是 a_n = a_n-1 + a_n-2
: 跪求大神
: 若tile a 4xn chessboard
: 它的遞迴式是什麼呢??
從2 x n跳到4 x n，複雜度變高很多
a_i = 4 * i的可鋪設方法數
|代表2*1，－代表1*2
從a_(n - 1)到a_n只有一種鋪設：
|
|
從a_(n - 2)到a_n不與前面重複者有1 + 3種鋪設方式：
－ －
－ 1種 和 － 3種 共 4種
－ ||
－
從a_(n - 3)、a_(n - 5)、...不與前面重複者有2種
－ －
－ － | 共2種
－ ... －
| － －
從a_(n - 4)、a_(n - 6)、...不與前面重複者有3種
－ － － － － －
－ － － 2種 和 | ＝ ... | 1種
－ ... － － －
| － |
所以對於k >= 2
a_(2k) = a_(2k-1) + 4a_(2k-2) + 3E(2k-4) + 2V(2k-3)
a_(2k-1) = a_(2k-2) + a_(2k-3) + 2E(2k-4) + 3V(2k-3)
其中
E(2k) = a_0 + a_2 + a_4 + ... + a_(2k) 當k >= 0
0 當k < 0
V(2k-1) = a_1 + a_3 + ... + a_(2k-1) 當k >= 1
0 當k < 0
a_0 = a_1 = 1
=> a_2 = a_1 + 4a_0 = 5
=> a_3 = a_2 + a_1 + 2a_0 + 3a_1 = 5 + 1 + 2 + 3 = 11
經過繁複代數整理後可以得出當k >= 2
a_(2k+2) = 6a_(2k) + 6a_(2k-1) - a_(2k-3)
a_(2k+1) = 6a_(2k-1) + 6a_(2k-2) - 4a_(2k-3) - 5a_(2k-4)
最後結果自己再驗算檢查看看。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.56.175.175 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1699566672.A.90E.html