✔ 最佳答案
這是錯位排列問題在排組課題中相當有名,一般有排容及遞歸兩種解法。
排容步驟較抽象繁複,不易為初學者所接受,以下用遞歸法解之。若只有兩個數字 1 , 2 , 明顯只有 2 , 1 一種填法, 記填法數 f(2) = 1。
若有三個數字 1 , 2 , 3 , 明顯只有 231 和 312 兩種填法, 於是 f(3) = 2。
現有五個數字, 這要求找出 f(5) 的值, 我們要建立 f(n) 的遞推關係。考慮 n 個數字 1 , 2 , 3 , ... , n 針對一個數, 比方說‘1’ , 它不能在首格,
設首格為 k = 2 , 3 , ... , n , 依 1 在何格分兩種情況 :情況Ⅰ: 1 在第 k 格, 有 (n - 1) f(n - 2) 種情況。
這是因為此時首格為 k , 第 k 格為 1 , 其餘 n - 2 個數就有 f(n - 2) 種排列,
而 k 有 n - 1 個可能數字, 於是就有 (n - 1) f(n - 2) 種情況。情況Ⅱ: 1 不在第 k 格, 有 (n - 1) f(n - 1) 種情況。
這是因為此時第 2 至第 n 格中, 1 不在第 k 格, 非 1 及 k 的 n - 2 個數字分別不在自己的同號格中, 於是 1 及該 n - 2 個數字共 n - 1 個數字在第 2 至第 n 格中有 f(n - 1) 種排列, 而 k 有 n - 1 個可能數字, 於是就有(n - 1) f(n - 1) 種情況。綜合Ⅰ,Ⅱ得 f(n) = (n - 1) f(n - 2) + (n - 1) f(n - 1) = (n - 1) ( f(n - 2) + f(n - 1) )
於是 f(5) = 4(f(3) + f(4)) = 4(f(3) + 3(f(3) + f(2))) = 4(2 + 3(2 + 1)) = 44。答: 44
2015-04-25 05:02:56 補充：
老師講的方法可能就是排容公式:
5! - (5C1)4! + (5C2)3! - (5C3)2! + (5C4)1! - (5C5)0! = 44
