※ 引述《shingai (吸收正能量)》之銘言：
: 在網路上看到錯列數列的兩個形式
: (型I)
: d_n = (n-1)*[d_(n-1)+d_(n-2)] , n>=3
: d_1=0, d_2=1
: _________________________________________
: (型II)
: d_n = n*d_(n-1)+(-1)^n , n>=3
: d_1=0, d_2=1
: _____________________________________________
: 如果要以d_n的closed form 來看此二遞迴容易驗
: 但想了解一下形式一與形式二 如何互推
: 或是 「組合論點」 的解釋...(其實這是游森棚教授寫的文章拋出來的問題)
: 詳見: http://case.ntu.edu.tw/hs/wordpress/?p=18046
: 懇請分享賜教，謝謝 !!
型I
{1 ~ n} 排進 {a_1 ~ a_n}，i不能排到ai
a_1位置有n-1種放法
剩下的位置 {a_2 ~ a_n} 排入 {2 ~ n} ∪ {1} \ {s}
s 是被選中放進 a_1 的數字
如果 1 排到 a_s，有 d_(n-2)種排法
如果 1 不排到 a_s, 有d_(n-1)種放法
所以 d_n = (n-1)*[d_(n-1)+d_(n-2)]
--
√￣≡～├╞≦≧∩∪ˇ∫∮㏒㏑≠≒±╳×→∞⊥
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.164.175.142
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1428336941.A.805.html