裝錯(cuò)信封問(wèn)題即歐拉錯(cuò)排問(wèn)題

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

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

3、信封，問(wèn)都裝錯(cuò)信封的裝法有多少種？|公式證明n個(gè)相異的元素排成一排a1,a2,.,an,且 ai(i=1,2,.,n)不在第i位的排列數(shù)為n!(1-1/1!+1/2!-1/3!+.+(-1)An*1/n!)證明:設(shè)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問(wèn)題的提出同室四人各寫一張賀年卡，先集中起來(lái)，然后每人從中拿一張別人送出的賀年卡.則 四張賀年卡的不同分配方式有A. 6 種 B. 9 種 C. 11 種 D. 23 種(1993年全國(guó)高考題理科17題)有5個(gè)客人參加宴會(huì)，他們把帽子放在衣帽寄放室內(nèi)，宴會(huì)結(jié)束后每人戴了一頂帽 子回家.回家后，他們的妻子都發(fā)現(xiàn)他們戴了別人的帽子.問(wèn)5個(gè)客人都不戴自己帽 子的戴法有多少種？上述兩個(gè)問(wèn)題，實(shí)質(zhì)上是完全一樣的.是被著名數(shù)學(xué)家歐拉(L eonhard

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

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

7、=直接用遞推公式，我試過(guò)了，推不出；直接用容斥原理就可以了：f(n)=n!(1/1! - 1/2! + 1/3! + (-1)(n-1)/n!)有 N 封不同的信裝入 N 個(gè)不同的信封，沒(méi)有一封裝對(duì)的裝法有多少種？用遞推的方法算到 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)算到這個(gè)類似與二項(xiàng)式的東西后就算不下去了我想知道a(n)=多少？能不能用我這個(gè)方法接著算下去？不能的話用正確的方法怎么算呀？問(wèn)題補(bǔ)充：不是說(shuō) 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)這步不會(huì)我想知道算到 a(n)=(-1)An*A(n,0)+(-1)A(n-1)*A(n,1)+.(-1)A1*A(n,n-1)后再怎 么把a(bǔ)(n)化到最簡(jiǎn)用A1,A2,.,An表示以下事件：Ak表示第k封信放在本 來(lái)的信封上。求出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!即至少有一對(duì)裝對(duì)的概率就是1-1/2! +1/3! -+(-1)A(n-1)/n!當(dāng)n無(wú)窮大時(shí)即=1/e你已經(jīng)化到最簡(jiǎn)了不用再化下去的！ a(n)=(n-1)*a(n-1)+a(n-2) a1=0 a2=1算到這一步是對(duì)的.即 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