裝錯信封問題即歐拉錯排問題

1、“裝錯信封問題”的數(shù)學模型與求解某人寫了n封信，同時寫了n個信封，然后將信任意裝入信封，問：每封信都裝錯的情 況有多少種？排列、組合及簡單計數(shù)問題.計算題.設這n封信依次為a、b、c.，第1封信a有(n-1)種放法，假設a放到了 b對 應的信封里，則b有(n-1)種放法；依此類推，分析隨后的幾封信的放法，進而 由排列數(shù)公式計算可得答案.解：設這n封信依次為a、b、c.，則第1封信a有(n-1)種放法，假設a放到了 b對應的信封里，則b有(n-1) 種放法；假設b放到了 c對應的信封里，則c有(n-2)種放法；假設c放到了 d對應的信封里，則d有(n-3)種放法； .依此類推，第n封信有1種放法

2、；則共有(n-1) (n - 1) (n - 2) (n-3) .1= (n - 1) (n-1) !，故每封信都裝錯的情況有(n-1) (n-1) !種.點評：本題考查分步計數(shù)原理的運用，解題中注意用假設的方法.被著名數(shù)學家歐拉(Leonhard Euler，1707-1783)稱為“組合數(shù)論的一個妙題”的“裝錯信 封問題”的兩個特例.“裝錯信封問題”是由當時最有名的數(shù)學家約翰伯努利(Johann Bernoulli，1667-1748)的兒子丹尼爾伯努利(DanidBernoulli，1700-1782)提出來的，大意如下：一個人寫了n封不同的信及相應的n個不同的信封，他把這n封信都裝錯了

3、信封，問都裝錯信封的裝法有多少種？|公式證明n個相異的元素排成一排a1,a2,.,an,且 ai(i=1,2,.,n)不在第i位的排列數(shù)為n!(1-1/1!+1/2!-1/3!+.+(-1)An*1/n!)證明:設1,2,.,n的全排列t1,t2,.,tn的集合為I,而使ti=i的全排列的集合記為Ai(1=i=n),貝Dn=|I|-|A1 UA2U.UAn|.所以 Dn=n!-|A1 UA2U.UAn|.注意到 |Ai|=(n-1)!,|AinAj|=(n-2)!,.,|AinA2n.nAn|=0!=1.由容斥原理：Dn=n!-|A1 U A2U. U An|=n!-C(n,1)(n-1)!+

4、C(n,2)(n-2)!-C(n,3)(n-3)!+.+(-1)AnC(n,n)*0!=n!(1-1/1!+1/2!-1/3!+.+(-1)5*1/n!)1問題的提出同室四人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡.則 四張賀年卡的不同分配方式有A. 6 種 B. 9 種 C. 11 種 D. 23 種(1993年全國高考題理科17題)有5個客人參加宴會，他們把帽子放在衣帽寄放室內，宴會結束后每人戴了一頂帽 子回家.回家后，他們的妻子都發(fā)現(xiàn)他們戴了別人的帽子.問5個客人都不戴自己帽 子的戴法有多少種？上述兩個問題，實質上是完全一樣的.是被著名數(shù)學家歐拉(L eonhard

5、 Euler，1707 一 1783)稱為“組合數(shù)論的一個妙題”的“裝錯信封問題”的兩個特例.“裝錯信封問 題”是由當時最有名的數(shù)學家約翰伯努利(Johann Bernoulli，16671748)的兒子丹 尼爾伯努利(DanidBernoulli，17001782)提出來的，大意如下：一個人寫了n封不同的信及相應的n個不同的信封，他把這n封信都裝錯了信封，問 都裝錯信封的裝法有多少種？2建立數(shù)學模型“裝錯信封問題”及兩個特例，其實就是n個不同元素的一類特殊排列問題，本文試 就給出這類問題的數(shù)學模型及求解公式.為方便，我們先把n個不同的元素及相應的 位置都編上序號1，2,，n，并且約定：在n個

6、不同元素的排列中1若編號為i(i=1, 2,，n)的元素排在第i個位置，則稱元素i在原位；否則稱元 素i不在原位.2若所有的元素都不在原位，則稱這種排列為n個不同元素的一個錯排(若每個元 素都在原位則稱為序排).按照上面約定，“裝錯信封問題”即為n個不同元素的錯排問題，則可構建“裝錯信 封問題”的數(shù)學模型為在n個不同元素的全排列中，有多少種不同的錯排？3模型求解應用集合中的容斥原理，我們就可得到“裝錯信封問題”的數(shù)學模型的求解公式.設I表示n個不同元素的全排列的集合Ai(i=1，2,，n)為元素i在原位的排列的集合.Ain A.(1 ij Wn)為元素i與j在原位的排列的集合.nA2時f(n)

7、=直接用遞推公式，我試過了，推不出；直接用容斥原理就可以了：f(n)=n!(1/1! - 1/2! + 1/3! + (-1)(n-1)/n!)有 N 封不同的信裝入 N 個不同的信封，沒有一封裝對的裝法有多少種？用遞推的方法算到 a(n)=(n-1)*(a(n-1)+a(n-2)然后得到 a(n)=(-1)人n*A(n,0)+(-1A(n-1)*A(n,1)+.(-1)A1*A(n,n-1)算到這個類似與二項式的東西后就算不下去了我想知道a(n)=多少？能不能用我這個方法接著算下去？不能的話用正確的方法怎么算呀？問題補充：不是說 a(n)=(n-1)*(a(n-1)+a(n-2)至0a(n)

8、=(-1)An*A(n,0)+(-1)A(n-1)*A(n,1)+(-1)A1*A(n,n-1)這步不會我想知道算到 a(n)=(-1)An*A(n,0)+(-1)A(n-1)*A(n,1)+.(-1)A1*A(n,n-1)后再怎 么把a(n)化到最簡用A1,A2,.,An表示以下事件：Ak表示第k封信放在本 來的信封上。求出A1UA2U . UAn的種類 然后用總的減去它就是所需答 案了那么，根據(jù)容斥原理，有：P(A1 U A2 UUAn) =P(A1)+P(A2)+P(An)-(P(AinA2)+P(AinA3)+P(A(n-1)AAn)(注意：求和取遍所有不同的AinAj)+(P(Ain

9、A2nA3)+P(AinA2nA4)+P(A(n-2)nP(A(n-1)nP(An)(注意：求和取遍所有不同的 AinAjnAk) +(-1)A(n-1)P(A1nA2nnAn)二(n-1)!*n/n!-(n-2)!/n!*C_nA2+(n-3)!/n!*C_n3+(-1)A(n-1)/n!=1-1/2! +1/3! -+(-1)A(n-1)/n!即至少有一對裝對的概率就是1-1/2! +1/3! -+(-1)A(n-1)/n!當n無窮大時即=1/e你已經(jīng)化到最簡了不用再化下去的！ a(n)=(n-1)*a(n-1)+a(n-2) a1=0 a2=1算到這一步是對的.即 a(n+1)=n*a(n)+a(n-1)然后令:b(n)=a(n)/n!(n+1)b(n+1)=nb(n)+b(n-1)故，b(n+1)-b(n)=b(n)-b(n-1)/(n+1)b(n)-b(n-1)=b(n-1)-b(n-2)/nb(n-1