※ 引述《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://www.ptt.cc/bbs/Math/M.1699566672.A.90E.html