作者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/cn.aspx?n=bbs/Math/M.1699566672.A.90E.html