推 iamwjy :Thank You !!! 05/11 21:38
※ 引述《iamwjy (醉翁之意)》之銘言：
: 設 a_n 表示 n 封信裝進 n 個信封，全部裝錯的方法數。
: a_1 = 0 , a_2 = 1 , a_(n) = (n-1)(a_(n-1)+a(n-2)).
: 請問各位高手這是怎麼推出來的？
: 謝謝。
只有1封信不可能裝錯 所以a_1 = 0
兩封互裝在另一個信封 => a_2 = 1
當有n封信
先看第1封信 因為不能放入第1個信封 所以只能放入2~n這n-1個信封選一個
假設選到2好了
則第2封信若放入第1個信封 就是剩下的n-2封信亂序 也就是a_n-2
但如果第2封信不放入第1個信封
則就可以當成沒有第1封信 然後把"第2封信"看成第1封信不能擺入第1個信封
如此一來 就變成 2~n 這n-1個信封亂序 也就是a_n-1
經由以上的討論
a_n = (n-1)(a_(n-1) + a_(n-2))
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82