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

问题描述:

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

概念:全错位排列,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种.