組合數(shù)學(xué)(13)

1、1第六章第六章 容斥原理及應(yīng)用容斥原理及應(yīng)用6.2具有重復(fù)的組合具有重復(fù)的組合 前面我們已經(jīng)完成了對(duì)前面我們已經(jīng)完成了對(duì)n個(gè)不同元素的集合的個(gè)不同元素的集合的r-組合，其組合數(shù)為：組合，其組合數(shù)為：并且完成了并且完成了k類元素并且都有無(wú)窮重復(fù)數(shù)的多重類元素并且都有無(wú)窮重復(fù)數(shù)的多重集合的集合的r-組合，其組合數(shù)為：組合，其組合數(shù)為： r1 -kr)!( !rrnrnn2 本節(jié)我們將證明與容斥原理相聯(lián)系的公式，本節(jié)我們將證明與容斥原理相聯(lián)系的公式， 并給出一種方法來(lái)求對(duì)于其重復(fù)數(shù)無(wú)任何限并給出一種方法來(lái)求對(duì)于其重復(fù)數(shù)無(wú)任何限制的多重集的制的多重集的r-組合數(shù)。組合數(shù)。 設(shè)設(shè)T是一個(gè)多重集，并設(shè)是一

2、個(gè)多重集，并設(shè)T的某些種類型的元素的某些種類型的元素x具有大于具有大于r的重復(fù)數(shù)。此時(shí)，通過(guò)用的重復(fù)數(shù)。此時(shí)，通過(guò)用r代替代替x的重的重復(fù)數(shù)，復(fù)數(shù)， T的的 r-組合的個(gè)數(shù)等于從組合的個(gè)數(shù)等于從T得到多重集的得到多重集的r-組合的個(gè)數(shù)，因?yàn)槊總€(gè)組合的元素最多。組合的個(gè)數(shù)，因?yàn)槊總€(gè)組合的元素最多。 如如:3a, b, 6c, d =3a, r b, 6c, r d 3 因?yàn)槊總€(gè)因?yàn)槊總€(gè)r-組合中的元素最多能達(dá)到組合中的元素最多能達(dá)到r個(gè)，個(gè)， 所以對(duì)無(wú)窮重復(fù)數(shù)的多重集，實(shí)際上只需要所以對(duì)無(wú)窮重復(fù)數(shù)的多重集，實(shí)際上只需要有限重復(fù)數(shù)有限重復(fù)數(shù)r就夠了?？梢钥偨Y(jié)為：無(wú)窮重復(fù)數(shù)的就夠了?？梢钥偨Y(jié)為：無(wú)窮

3、重復(fù)數(shù)的多重集多重集 a1, a2, ., ak總能化為有限重復(fù)總能化為有限重復(fù)數(shù)的多重集數(shù)的多重集n1a1, n2a2, ., nkak,對(duì)于求對(duì)于求r-組組合的個(gè)數(shù)，可以確定兩個(gè)合的個(gè)數(shù)，可以確定兩個(gè)“極端極端”的情況：的情況： 1） n1= n2= .=nk=1， T是一個(gè)普通集合。是一個(gè)普通集合。 2） n1= n2= .=nk= r， T是重復(fù)數(shù)足夠的集合。是重復(fù)數(shù)足夠的集合。4我們將用容斥原理來(lái)解釋如何得到其他的解。我們將用容斥原理來(lái)解釋如何得到其他的解。 下面雖然只是一個(gè)例子，但能夠很清楚地得下面雖然只是一個(gè)例子，但能夠很清楚地得到解法，并且推廣到一般情況下：到解法，并且推廣到一

4、般情況下：例：確定多重集例：確定多重集T = 3a, 4b, 5c 的的10-組合的組合的數(shù)。數(shù)。解：在很久前我們遇到過(guò)類似的題，見書解：在很久前我們遇到過(guò)類似的題，見書P43;當(dāng)當(dāng)時(shí)我們用窮舉法排出來(lái)滿足條件的所有組合。時(shí)我們用窮舉法排出來(lái)滿足條件的所有組合。 現(xiàn)在我們將容斥原理應(yīng)用到多重集：現(xiàn)在我們將容斥原理應(yīng)用到多重集：5 T * = a, b, c 的所有的所有10-組合的集合組合的集合S上上令令P1表示表示T *的的10-組合具有多于組合具有多于3個(gè)個(gè)a的性質(zhì)；的性質(zhì)； P2表示表示T *的的10-組合具有多于組合具有多于4個(gè)個(gè)b的性質(zhì)；的性質(zhì)； P3表示表示T *的的10-組合具有

5、多于組合具有多于5個(gè)個(gè)c的性質(zhì)；的性質(zhì)；此時(shí)題意要求的多重集此時(shí)題意要求的多重集T的的10-組合的數(shù)就是組合的數(shù)就是T* 中不具備性質(zhì)中不具備性質(zhì)P1 ，P2 ，P3的的10-組合的數(shù)。同樣組合的數(shù)。同樣6 令令A(yù)i是由是由T *中滿足性質(zhì)中滿足性質(zhì)Pi（i =1,2,3）的那些）的那些 10-組合夠成。組合夠成。 的元素?cái)?shù)量即的元素?cái)?shù)量即是我們需要的，由容斥原理：是我們需要的，由容斥原理：321AAA321323121321321)()(AAAAAAAAAAAASAAA6610121013101103rkrS組合公式得：類無(wú)限重復(fù)元素的由7 其中集合其中集合A1是由是由a多于多于3個(gè)的個(gè)的T

6、 *的所有的所有10-組組 合組成；即構(gòu)成合組成；即構(gòu)成A1中每個(gè)中每個(gè)10-組合都至少有組合都至少有4個(gè)個(gè)a，如果任意取，如果任意取A1中的一個(gè)中的一個(gè)10-組合并且去掉組合并且去掉其中的其中的4個(gè)個(gè)a，剩下的就是，剩下的就是T *的的6-組合。組合。 反之，如果拿出反之，如果拿出T *的的6-組合再加入組合再加入4個(gè)個(gè)a就得就得到到T *的的10-組合，而且其中至少有組合，而且其中至少有4個(gè)個(gè)a，也就是，也就是說(shuō)說(shuō)T *的的10-組合個(gè)數(shù)等于組合個(gè)數(shù)等于T *的的6-組合個(gè)數(shù)，或者組合個(gè)數(shù)，或者說(shuō)說(shuō)A1中的中的4個(gè)元素已經(jīng)確定，余下再作三類元素個(gè)元素已經(jīng)確定，余下再作三類元素8 選擇選擇6

7、個(gè)的個(gè)的6-組合，故：組合，故：同理，集合同理，集合A2是由是由b多于多于4個(gè)的個(gè)的T*的所有的所有10-組組 合組成；合組成； A2中中 T *的的10-組合個(gè)數(shù)等于組合個(gè)數(shù)等于T *的的5-組組合個(gè)數(shù)。合個(gè)數(shù)。154641342157513532AA286861361A9 集合集合A1A2是至少有是至少有4個(gè)個(gè)a并且至少有并且至少有5個(gè)個(gè)b的的T* 的所有的所有10-組合組成，實(shí)際上這十個(gè)元素已組合組成，實(shí)際上這十個(gè)元素已經(jīng)固定了九個(gè)，另外一個(gè)可以選擇經(jīng)固定了九個(gè)，另外一個(gè)可以選擇a,b,c中任意一中任意一個(gè)，共有個(gè)，共有3種，種， 用前面同樣的分析，用前面同樣的分析，A1 A2中的一個(gè)中

8、的一個(gè)10-組合去掉組合去掉其中的其中的4個(gè)個(gè)a和和 5個(gè)個(gè)b ，剩下的就是，剩下的就是T *的的1-組合。組合。 反之，如果拿出反之，如果拿出T *的的1-組合再加入組合再加入4個(gè)個(gè)a和和 5個(gè)個(gè)b就得到就得到T *的的10-組合，而且其中至少有組合，而且其中至少有4個(gè)個(gè)a和和105個(gè)個(gè)b ，也就是說(shuō)，也就是說(shuō)T *的的10-組合個(gè)數(shù)等于組合個(gè)數(shù)等于T *的的1-組組 合個(gè)數(shù)，用多重集的合個(gè)數(shù)，用多重集的r-組合數(shù)公式求法：組合數(shù)公式求法：A2A3中總共才有中總共才有9個(gè)元素，沒有個(gè)元素，沒有10-組合，所以：組合，所以： A1A2 = 0；和；和 A1A2 A3 = 0;102013031

9、311313121AAAA同理有：與分析的結(jié)果三種一致11 60)013()152128(66321AAA只有六個(gè)只有六個(gè)10-組合，我們可以全部列出來(lái)：組合，我們可以全部列出來(lái)： 3a, 4b, 3c 3a, 3b, 4c 3a, 2b, 5c 2a, 4b, 4c 2a, 3b, 5c 1a, 4b, 5c 由此例題我們可以看出，當(dāng)重復(fù)數(shù)之和靠近由此例題我們可以看出，當(dāng)重復(fù)數(shù)之和靠近r-組合的組合的r時(shí)，我們可以窮舉出所有的時(shí)，我們可以窮舉出所有的r-組合，組合，12 但在這兩個(gè)數(shù)差距大時(shí)，我們最多求出但在這兩個(gè)數(shù)差距大時(shí)，我們最多求出r-組合組合 的個(gè)數(shù)。的個(gè)數(shù)。 我們?cè)?jīng)指出，我們?cè)?jīng)

10、指出，r-組合與方程的整數(shù)解之間的關(guān)組合與方程的整數(shù)解之間的關(guān)系：多重集系：多重集n1a1, n2a2, ., nkak的的r-組合的組合的個(gè)數(shù)等于方程：個(gè)數(shù)等于方程： x1+ x2+ .+xk= r的整數(shù)解的個(gè)的整數(shù)解的個(gè)數(shù)數(shù)(P44定理定理3.5.1)。這些解滿足：。這些解滿足： 0 xi ni (i=1,2,.k) 這些解的個(gè)數(shù)可以用上面的方法來(lái)求得。這些解的個(gè)數(shù)可以用上面的方法來(lái)求得。13 例：滿足例：滿足1 x1 5, 2 x2 4, 0 x3 5, 3 x4 9的方程的方程x1 x2 x3 x4 18 的的整數(shù)解的個(gè)數(shù)有多少？整數(shù)解的個(gè)數(shù)有多少？分析分析 這一問(wèn)題與我們上述一般情況

11、的差別在這一問(wèn)題與我們上述一般情況的差別在于解所滿足的條件不是于解所滿足的條件不是0 xini的形式。因此，的形式。因此，需進(jìn)行相應(yīng)的變量變換：令需進(jìn)行相應(yīng)的變量變換：令 y1x1-1, y2x2+2, y3=x3, y4=x4-314 使得原方程變?yōu)槭沟迷匠套優(yōu)閥1+ y2+ y3+ y4=16而原條件變?yōu)槎瓧l件變?yōu)?0y14, 0y26, 0y35, 0y46 對(duì)于方程對(duì)于方程 y1+ y2+ y3+ y4=16若其非負(fù)整數(shù)解集若其非負(fù)整數(shù)解集是是S，則以下的問(wèn)題就是根據(jù)容斥原理的具體，則以下的問(wèn)題就是根據(jù)容斥原理的具體計(jì)算了。計(jì)算了。9691619161416S15 令令P1為性質(zhì)為

12、性質(zhì)y15， P2為性質(zhì)為性質(zhì)y27， P3為性質(zhì)為性質(zhì) y36， P4為性質(zhì)為性質(zhì)y47。 令令A(yù)i為滿足性質(zhì)為滿足性質(zhì)Pi的解的集合，題意是求集合：的解的集合，題意是求集合： 的大小。其中集合的大小。其中集合A1為為滿足性質(zhì)滿足性質(zhì)y15的解組成，再作一次變量代換：的解組成，再作一次變量代換： z1 = y1 5, z2 = y2, z3 = y3, z4 = y4; 求集合求集合A1的解的個(gè)數(shù)就與下列方程非負(fù)整數(shù)解的解的個(gè)數(shù)就與下列方程非負(fù)整數(shù)解的個(gè)數(shù)相同，的個(gè)數(shù)相同， z1 + z2 + z3 + z4 = 114321AAAA16因此：因此：用類似的方法可以求用類似的方法可以求 A2

13、 、 A3 和和 A4 ，他們，他們分別是下列方程的非負(fù)整數(shù)解的個(gè)數(shù)分別是下列方程的非負(fù)整數(shù)解的個(gè)數(shù)：1 + 2 + 3 + 4 = 9 ； 1 + 2 + 3 + 4 = 10 1 + 2 + 3 + 4 = 936411141114111A22091291492A172209129149286101310141043AA而集合而集合A1A2是所有滿足性質(zhì)是所有滿足性質(zhì)y15且且y27的那些的那些解組成，作變量代換解組成，作變量代換u1 = y1 5, u2 = y2-7, u3 = y3, u4 = y4; 那么那么A1A2的解的個(gè)數(shù)等于方程：的解的個(gè)數(shù)等于方程： u1 + u2 + u3

14、 + u4 = 4的非負(fù)整數(shù)解的個(gè)數(shù)。的非負(fù)整數(shù)解的個(gè)數(shù)。18故故3547414421AA 同理得：同理得：;2036;1025;2036;3547;56584342324131AAAAAAAAAA19集合集合A1A2 A3肯定是空集，因?yàn)樗男再|(zhì)肯定是空集，因?yàn)樗男再|(zhì) 是三個(gè)解之和大于是三個(gè)解之和大于 遠(yuǎn)遠(yuǎn)超過(guò)方程右邊的數(shù)，遠(yuǎn)遠(yuǎn)超過(guò)方程右邊的數(shù)， 所以所以Ai三個(gè)以上的交集都為空。三個(gè)以上的交集都為空。 A1A2 A3 =0.;應(yīng)用容斥原理：應(yīng)用容斥原理：個(gè)55)2010205635()220286220364(9694321AAAA206.3 錯(cuò)位排列錯(cuò)位排列 集合的元素，對(duì)于某種特

15、定的情況下有指定集合的元素，對(duì)于某種特定的情況下有指定的位置，我們現(xiàn)在可以討論元素不再指定的位的位置，我們現(xiàn)在可以討論元素不再指定的位置上的排列數(shù)問(wèn)題。置上的排列數(shù)問(wèn)題。 例：在一個(gè)聚會(huì)上，有例：在一個(gè)聚會(huì)上，有10位紳士要查看他們的位紳士要查看他們的帽子，有多少中方式使得這些紳士中沒有人能帽子，有多少中方式使得這些紳士中沒有人能夠拿到他們來(lái)時(shí)所戴的帽子？夠拿到他們來(lái)時(shí)所戴的帽子？ 例：有多少種方法能夠?qū)⒆帜咐河卸嗌俜N方法能夠?qū)⒆帜窶,A,D,I,S,O,N拼拼寫出，并且使得拼出的單詞不同與寫出，并且使得拼出的單詞不同與Madison?21 以上都是錯(cuò)位排列問(wèn)題，簡(jiǎn)稱為以上都是錯(cuò)位排列問(wèn)題，

16、簡(jiǎn)稱為錯(cuò)排錯(cuò)排； 由于元素性質(zhì)與討論不相干，設(shè)由于元素性質(zhì)與討論不相干，設(shè)n個(gè)元素的個(gè)元素的集合集合 x1, 2, 3, , n， n個(gè)元素依次給以標(biāo)號(hào)個(gè)元素依次給以標(biāo)號(hào)1，2，n。在。在n個(gè)元素的全排列中，求每個(gè)個(gè)元素的全排列中，求每個(gè)元素元素都不在自己原來(lái)位置都不在自己原來(lái)位置上的排列數(shù)。上的排列數(shù)。 首先每一個(gè)錯(cuò)排都是原集合的一個(gè)全排列，首先每一個(gè)錯(cuò)排都是原集合的一個(gè)全排列， 記為記為 i1 ,i2 , , in 并且元素滿足：并且元素滿足： i1 1, i2 2, , in n 22 用用Dn表示表示1, 2, 3, , n的錯(cuò)位排列的個(gè)數(shù)。上的錯(cuò)位排列的個(gè)數(shù)。上 述的紳士帽子和字母拼

17、單詞問(wèn)題就成了求述的紳士帽子和字母拼單詞問(wèn)題就成了求D10 和和D7的值。下面對(duì)部分?jǐn)?shù)的集合求錯(cuò)排數(shù)；的值。下面對(duì)部分?jǐn)?shù)的集合求錯(cuò)排數(shù)； n = 1時(shí)，沒有錯(cuò)位排列，時(shí)，沒有錯(cuò)位排列， D1= 0 n = 2時(shí)，唯一錯(cuò)位排列是：時(shí)，唯一錯(cuò)位排列是： 21， D2= 1 n = 3時(shí)，有兩個(gè)錯(cuò)位排列：時(shí)，有兩個(gè)錯(cuò)位排列：231，312； D3= 2 (n = 3時(shí)的全排列共時(shí)的全排列共6個(gè)，分別是：個(gè)，分別是：123, 132, 213, 231, 312, 321;紅色的是錯(cuò)排紅色的是錯(cuò)排)23n = 4時(shí)，共有時(shí)，共有24個(gè)排列，其中錯(cuò)位排列有個(gè)排列，其中錯(cuò)位排列有9個(gè)：個(gè)： 2143， 3

18、142， 4123 2341， 3412， 4312 2413， 3421， 4321 D4= 9定理定理6.3.1 對(duì)于對(duì)于n 1，有：，有：)!1) 1(.! 31! 21! 111 ( !nnDnn24證明：此定理是指證明：此定理是指n個(gè)元素都錯(cuò)位的排列數(shù)。個(gè)元素都錯(cuò)位的排列數(shù)。 設(shè)設(shè)S是集合是集合1, 2, , n的全部的全部n！個(gè)排列的集！個(gè)排列的集合。中的第合。中的第j個(gè)位置上恰好是個(gè)位置上恰好是j，那么，集合，那么，集合 Aj= x | x S Pj(x) j=1,2,n便是便是S中所有滿足性質(zhì)中所有滿足性質(zhì)Pj排列的集合。排列的集合。 根據(jù)以上定義，顯然有根據(jù)以上定義，顯然有n

19、nAAAAD.32125由于由于Aj中的每個(gè)排列均具有形式中的每個(gè)排列均具有形式 i1 i2 ij-1 j ij+1 in其中其中, i1 i2 ij-1 ij+1 in是集合是集合1,2,j-1,j+1,n的一個(gè)的一個(gè)(n-1)-排列。顯然，這種排列有排列。顯然，這種排列有(n-1)!個(gè)。個(gè)。故此故此 |Aj|=(n-1)! j=1,2,.,n又又由于由于Ak Aj中的每個(gè)排列均具有形式中的每個(gè)排列均具有形式 i1 i2 ik-1 k ik+1 ij-1 j ij+1 in26 其中其中 i1 i2 ik-1 ik+1 ij-1 ij+1 in是集合是集合 1,2,k-1,k+1,j-1,j

20、+1,n 的一個(gè)的一個(gè)(n-2)-排排列，顯然，這種排列有列，顯然，這種排列有(n-2)!個(gè)，故此個(gè)，故此 | Ak Aj | = (n-2)! 1 kj n 一般來(lái)說(shuō)，對(duì)于一般來(lái)說(shuō)，對(duì)于1,2,n的任意的任意k-組合組合i1, i2 , , ik, 我們有：我們有：)!(.21knAAAkiii27另外，由于存在集合另外，由于存在集合1, 2, , n的的 個(gè)個(gè)k-組合組合 應(yīng)用容斥原理應(yīng)用容斥原理 P107 (6-3)式。式。 kn!)1(.)!2()!2( !2!)!1()!1( ! 1!0)1(.)!3(3)!2(2)!1(1!nnnnnnnnnnnnnnnnnnDnnn28定理得證。

21、定理得證。例：例：10位紳士帽子問(wèn)題可以用公式計(jì)算：位紳士帽子問(wèn)題可以用公式計(jì)算： 5字母拼單詞問(wèn)題：字母拼單詞問(wèn)題：)!1)1(.! 31!21! 111 ( !)1(.! 3!2! 1!nnnnnnnnDnnn)!101)1(.!31!21! 111( !101010D44)! 51! 41! 31! 21! 111 ( ! 55D29 例：數(shù)例：數(shù)1,2,9的全排列中，求偶數(shù)在原來(lái)位置的全排列中，求偶數(shù)在原來(lái)位置 上，其余都不在原來(lái)位置的錯(cuò)排數(shù)目。上，其余都不在原來(lái)位置的錯(cuò)排數(shù)目。 解：實(shí)際上是解：實(shí)際上是1，3，5，7，9五個(gè)數(shù)的錯(cuò)排問(wèn)題，五個(gè)數(shù)的錯(cuò)排問(wèn)題，總數(shù)為：總數(shù)為： 如果只是要

22、求如果只是要求部分元素錯(cuò)位排列部分元素錯(cuò)位排列，可以修改，可以修改為：令為：令A(yù)1, A2,., Ak的表示集合的表示集合 1, 2, n中部中部分元素分元素1, 2, k ( k n )在原來(lái)位置的排列，在原來(lái)位置的排列，44)! 51!41! 31!21! 111 ( ! 55D30那么部分元素那么部分元素1, 2, k的錯(cuò)位排列數(shù)是：的錯(cuò)位排列數(shù)是：)!()1(.)!2(2)!1(1!.21knkknknknAAAkk 由于由于k n ，公式只有，公式只有k+1項(xiàng)，余下項(xiàng)的的項(xiàng)，余下項(xiàng)的的系數(shù)均為系數(shù)均為0。31例：在例：在8個(gè)字母?jìng)€(gè)字母A,B,C,D,E,F,G,H的全排列中的全排列中

23、,求求 使使A,C,E,G四個(gè)字母不在原來(lái)四個(gè)字母不在原來(lái)上的錯(cuò)排數(shù)目。上的錯(cuò)排數(shù)目。解：解：8個(gè)字母的全排列數(shù)是個(gè)字母的全排列數(shù)是 8！, n = 8, k = 4 令令A(yù)1, A2, A3, A4, 分別表分別表A,C,E,G在原來(lái)位置上的排列，在原來(lái)位置上的排列，則錯(cuò)排數(shù)為：則錯(cuò)排數(shù)為： )!() 1(.)!2(2)!1(1!4321knkknknknAAAAk32 24024! 444! 534! 624!714! 8)!48(44) 1(.)!28(24)!18(14! 844321AAAA例例:求求8個(gè)字母?jìng)€(gè)字母A,B,C,D,E,F,G,H的全排列中只有的全排列中只有4 個(gè)不在原

24、來(lái)位置的排列數(shù)。個(gè)不在原來(lái)位置的排列數(shù)。33解：解：8個(gè)字母中只有個(gè)字母中只有4個(gè)不在原來(lái)位置上，其余個(gè)不在原來(lái)位置上，其余4 個(gè)字母保持不動(dòng)，相當(dāng)于個(gè)字母保持不動(dòng)，相當(dāng)于4個(gè)元素的錯(cuò)排，個(gè)元素的錯(cuò)排，但不屬于前面奇、偶數(shù)例題問(wèn)題，本題中哪但不屬于前面奇、偶數(shù)例題問(wèn)題，本題中哪4個(gè)字母錯(cuò)排？哪個(gè)字母錯(cuò)排？哪4個(gè)字母不動(dòng)我們不清楚。首個(gè)字母不動(dòng)我們不清楚。首先任意選取先任意選取4個(gè)字母，其數(shù)目為個(gè)字母，其數(shù)目為: 這這4個(gè)元素的錯(cuò)排數(shù)目：個(gè)元素的錯(cuò)排數(shù)目：D4 = 9故故8個(gè)字母的全排列中有個(gè)字母的全排列中有4個(gè)不在原來(lái)位置上的個(gè)不在原來(lái)位置上的排列數(shù)應(yīng)為：排列數(shù)應(yīng)為：9 =630484834

25、我們?cè)趯W(xué)習(xí)我們?cè)趯W(xué)習(xí)高等數(shù)學(xué)高等數(shù)學(xué)中中“無(wú)窮級(jí)數(shù)無(wú)窮級(jí)數(shù)”時(shí)知道，時(shí)知道， 利用麥克勞林級(jí)數(shù)將函數(shù)利用麥克勞林級(jí)數(shù)將函數(shù)e x展開展開.)!1)1(.!31!21! 111( !.!31!21! 111.!31!21! 111!11320nnDexxxxnennnnx而錯(cuò)排列數(shù) 由于由于e 1 是無(wú)窮級(jí)數(shù)，而是無(wú)窮級(jí)數(shù)，而Dn是有限項(xiàng)級(jí)數(shù)是有限項(xiàng)級(jí)數(shù)，35 e 1的前的前n 項(xiàng)可以用項(xiàng)可以用Dn除以除以n!來(lái)表示來(lái)表示.)!2(1)1()!1(1)1(!1)1(!1)1(.)!1)1(.! 31!21! 111 (21101nnnDiinennnninninn36 用無(wú)窮交錯(cuò)級(jí)數(shù)的性質(zhì)斷定：

26、用無(wú)窮交錯(cuò)級(jí)數(shù)的性質(zhì)斷定：3332(1+n )nn(1+n )n =22的整數(shù)是最接近實(shí)際上enDenDnDennDennnn!;!1)!1(1!1 計(jì)算表明，計(jì)算表明，n7時(shí)，時(shí)， 至少有三為至少有三為小數(shù)相同，就是說(shuō)精確到千分位。這時(shí)我們就小數(shù)相同，就是說(shuō)精確到千分位。這時(shí)我們就認(rèn)為認(rèn)為的錯(cuò)位，是集合而,.21!;!1nnDnDenn!1nDen與37 排列與全排列的比。那么隨機(jī)選擇一個(gè)排列，排列與全排列的比。那么隨機(jī)選擇一個(gè)排列， 它是錯(cuò)位排列的概率是它是錯(cuò)位排列的概率是Dn / n! 。 例：本節(jié)開始提出的帽子問(wèn)題，如果隨機(jī)將帽例：本節(jié)開始提出的帽子問(wèn)題，如果隨機(jī)將帽子發(fā)給這些紳士，他

27、們收到不是自己帽子的概子發(fā)給這些紳士，他們收到不是自己帽子的概率為：率為： D10 / 10! ，近似于，近似于e 1。如果紳士的人數(shù)。如果紳士的人數(shù)達(dá)到達(dá)到10000人，他們收到不是自己帽子的概率依人，他們收到不是自己帽子的概率依然為：然為： D10 / 10! ，近似于，近似于e 138錯(cuò)位排列數(shù)錯(cuò)位排列數(shù)D Dn n的性質(zhì)的性質(zhì) 1) Dn = (n-1)(Dn-2 + Dn-1) (n=3,4,) 當(dāng)當(dāng)n=1, 2時(shí)，時(shí)， D1 = 0，D2 = 1；這個(gè)公式將在第七章中給予證明。我們可以驗(yàn)證這個(gè)公式將在第七章中給予證明。我們可以驗(yàn)證 D3 = (3-1)(D3-2 + D3-1) =

28、 2(D1 + D2) =2(0+1)=2 D4 = (4-1)(D4-2 + D4-1) = 3(D2 + D3 ) =3(1+2)=9 D5 = 4(2 + 9)=44; D6 = 5(9 + 44)=26539 2) Dn = nDn-1 + (-1)n (n=3,4,) 由性質(zhì)由性質(zhì)1) Dn = (n-1)(Dn-2 + Dn-1) (n=3,4) 將上式變形為：將上式變形為：Dn nDn-1 = Dn +(n-1) Dn-2 Dn nDn-1 = Dn-1 (n-1) Dn-2 觀察等式兩邊可以看出：左邊是第觀察等式兩邊可以看出：左邊是第n項(xiàng)與項(xiàng)與n倍后項(xiàng)的差，右邊是第倍后項(xiàng)的差，右邊是第n-1項(xiàng)與項(xiàng)與n-1倍后項(xiàng)的差倍后項(xiàng)的差的相反數(shù)，依次規(guī)律再右邊應(yīng)該是第的相反數(shù)，依次規(guī)律再右邊應(yīng)該是第n-2項(xiàng)與項(xiàng)與 n-2倍后項(xiàng)的差的相反數(shù)再相反數(shù)，即倍后項(xiàng)的差的相反數(shù)再相反數(shù)，即(-1)2.1 2 31 2 3(11) (2 2) (3 3)3 1 22 3 1(3 2) (1 3) (2 1)2 3 13 2 1(2 3) (3 1) (1 2) 并置，40 Dn nDn-1 = Dn-1 (n-1) Dn-2 = (-1)2 Dn-2 (n-2) Dn-3 = (-1)3 Dn-3 (n-3) Dn-4 =. = (-1)n-