第 2 題
現在要從
n個囚犯中提取若干人作審訊,為了防止串供,編號連續的囚犯不得同時拘提。例如編號1,2,3,4,5,6等六人,一次可以同時拘提135號囚犯,或24號囚犯,亦可以只拘提5號一人。令
F(n)表示
n有個囚犯時一次拘提若干人的方法數,請回答以下問題。
(a)
F(1)+F(2)+F(3)=?
(b)若
F(n)=aF(n−1)+bF(n−2)+c,
n
3,求
a
b
c。
(c)
F(6)=?
[解答]
(b)
(1) 提取第 n 個囚犯:則第 (n - 1) 個囚犯不能提取,前 (n - 2) 個有 F(n - 2) 種提取方法,每一種都把第 n 個加進去,另外有 1 種是僅提取第 n 個囚犯,計有 F(n - 2) + 1 種方法
(2) 不提取第 n 個囚犯:有 F(n - 1) 種方法
故 F(n) = F(n - 1) + F(n - 2) + 1