宿舍里的4名同学为庆祝元旦,每人准备了一份礼物进行交换,规定自己不拿自己的礼物,则有多少种拿法

Question

宿舍里的4名同学为庆祝元旦,每人准备了一份礼物进行交换,规定自己不拿自己的礼物,则有多少种拿法

Answer 1

概念：全错位排列,n个物质,重新排列顺序,使其均不在原位.
历史:被著名数学家欧拉(Leonhard Euler,1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．
“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli,1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli,1700－1782)提出来的,大意如下：
个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种?
公式：
递推公式：设n个物质排列方法为s（n）
当n=1 时,s（n）=0
当n=2 时,s（n）=1
否则 s（n）=（n-1）*（s（n-1）+s（n-2））
阶乘公式：n!-C(1 n)*(n-1)!+C(2 n)!-…+(-1)^kC(k n)*(n-k)!+…+(-1)^n*C(n n)*0!
上式等价于n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
________________________
对本题：
S（1）＝0,S（2）＝1
S（3）＝2（0＋1）＝2
S（4）＝3（2＋1）＝9
本题数量不多也可直接枚举：设四位同学顺序是（甲乙丙丁）,
（乙,甲,丁,丙）（乙,丙,丁,甲）（乙,丁,甲,丙）
（丙,甲,丁,乙）（丙,丁,甲,乙）（丙,丁,乙,甲）
（丁,甲,乙,丙）（丁,丙,甲,乙）（丁,丙,乙,甲）
以上共9种.