※ 引述《alan790712 (方塊人)》之銘言：
: 假設有n個人，有n種限制
: ex甲乙丙丁，甲不能在第一位，乙不能在第二位，
: 丙不能在第三位，丁不能在第四位.......等。
: n
: 設此變數為E(Error) E
: m
: n為共有幾種，m為有幾個錯位
: n n-1 n-2
: 我們老師說可以找到一的遞回數列 H =(n-1){H +H }
: n n-1 n-2
你上面是不是有打錯?應該是E不是H吧?
: 請問可以幫證明或導出或說出裡面的原因嗎== ==?
: 謝謝
n
簡化符號，設a(n)=E
n
欲證 a(n)=(n-1)(a(n-1)+a(n-2))
proof
a(n)=n人皆排錯方法數
假設n人編號1~n
先排1號，只有(n-1)個位置可選，設他排到k號位
case1 k號坐到1號位
此時方法數=另外n-2人皆排錯方法數=a(n-2)
case2 k號不坐1號位
設m號坐到1號位，m=/=k
此時可將 1,2,..,k,..,m,..,n 號位看成
k,2,..,X,..,m,..,n (X代表不管他)(把1號位貼上號標籤)
座位上為 m,?,..,X,..,?,..,? (此時除1號外，每人皆坐錯位)
方法數=n-1人皆排錯方法數=a(n-1)
故 a(n)=(n-1)(a(n-1)+a(n-2))
q.e.d.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.197.241