錯位排列和禁位排列

錯位排列和禁位排列問題提出〔1〕某省決定對所轄8個城市的黨政一把手進行任職交流，要求把每個干部都調到另一個城市去擔任相應的職務，問共有多少種不同的干部調配方案？〔2〕有5個客人參加宴會，他們把衣帽寄放在室內，宴會后每人戴了一頂帽子回家，回家后，他們的妻子都發(fā)現，他們戴了別人的帽子，問5個客人都不戴自己帽子的戴法有多少種？上述兩個問題，實質上是同一種類型的問題，被著名數學家歐拉〔LeonardEuler，1707—1783〕稱為“組合數論”的一個妙題的“裝錯信封問題”的兩個特例?！把b錯信封問題”是由當時最有名的數學家約翰?伯努利〔JohnBernoulli,1667—1748〕的兒子丹尼爾?伯努利〔DanidBernoulli,1700—1782〕提出來的，大意如下：一個人寫了n封不同的信及相應的n個不同的信封，他把這n封信都裝錯了信封。問全部裝錯了信封的裝法有幾種？錯位排列和禁位排列1〕錯位排列：n個相異元素中m(m，n)個元素a,a,…,a，其中a(k?1,2,…,m)不在第TOC\o"1-5"\h\zi1i2 im iki(k?1,2,…,m)個位置〔一下簡稱其為a的本位〕，而其他n-m個元素中的任何一個都在原來的位置k ik〔本位〕的排列。如果n個元素都不在本位，稱為全錯位排列。2〕禁位排列〔一個元素禁止排在一個位置〕：n個相異元素中m(m，n)個元素a,a,…,a，其中i1i2 ima(k?1,2,…,m)不能排在第j(k?1,2,…,m)個位置的排列。ikk3〕兩者的區(qū)別在于：錯位排列中除這m個元素之外的其他n-m個元素都在本位，即這m個元素只能在m個位置i,i,…,i中排列，且不出現a(k?1,2,…,m)在i位的情況；而禁位排列中只限制m個元素不在12m i kk本位，因此a(k?1,2,…,m)可以排在1,2,…,n中除i之外的任何位置。ikk禁位排列與全錯位排列的種數1〕禁位排列數：求禁位排列數，只需從n個元素的全排列中除去指定元素占本位的排列即可，其中有1個元素占本位的排列數是C1Pn-1，有兩個元素占本位的排列數是C2Pn-1，……，n個元素占本位的排列數是CmPn-m.TOC\o"1-5"\h\zmn-1 mn-1 mn-m記錯位排列和禁位排列的排列數分別為Dm,Em，用D表示n個元素全錯位排列。則由容斥原理有:nn n【禁位排列公式】Em?C0n！-C1(n-1)!+C2(n-2)!F(—lbCm(n-m)!nmm m m【證明】①當m?0時，等式左邊為E0，表示n個元素沒有限制，所以有Pn?n！，nn等式右邊本應該有m+1項，當m?0時，只有1項，就是C0n！?n!.等式成立;0②假設Ek?工(-1)iCiPn-i；n kn-ii?0③那么當m€k+1時，設第k+1個元素為a,則前k個元素不占本位而a占本位的排列數為:Ek+Ek+1€Ek—Ek€ Pn-i—n n n-1 kn-i kn-i-1i€0 i€0€^C0Pn—C1Pn-1+C2Pn-2—???+(,1)kkn kn-1 kn-2 kn-k0Pn-1—C1Pn-2+???+ (-1)kkn-1 kn-2 kn-k kn-k-1€C0Pn+…(，1?(Ci n-i+(€C0Pn+…(，1?(Ci n-i+(，1)kn k k n-ini€1W+1CkPkn—k—1€C0Pn+…(，1?CiPn-i+(—1)k+1Ck+1Pn-k-1k+1n—i k+1n—k—1k+1ni€1二…(-1?CiPn-ik+1n-ii€0因此對于0<m<n時，公式1均成立。【例1】5個人站成一排，其中甲不站排頭，乙不站排尾，共有多少種不同的站法。【解】由公式得：E2€C0P5一C1P4+C2P3€785 25 24 2 3例2】6個人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少種不同的站法?！窘狻坑晒降茫篍3€C0P6，C1P5+C2P4，C3P3€4266 3 6 35 3 4 3 3變式1】用0,1,2,3,4這5個數字，組成沒有重復數字的5位數，百位上不排3，一共有多少種排法？變式2】在由1,2,3,5,9組成的沒有重復數字的五位數中，共有多少個小于60000的奇數？2〕全錯為排列數:全錯為排列就是n個元素，全不排在本位，實際上就是禁位排列中，當m€n的情況，因此:【全錯位排列公式】D€En€C0n！，C1(n—1)!+C2(n—2)!—…+(—1》C“0！.nnn n n n另一種寫法：D€n！n1,丄+丄，丄+???+(,)丄1！ 2！ 3！ n！i€0 i！例3】寢室四個人每人寫一張賀卡，然后互相交換，每個人不拿到自己的卡片，一共有多少種可能？【解】由公式得：D€C0P4一C1P3+C2P2一C3P1+C4P0=9；44 43 42 41 40€9.用另外一個公式得：D€4！1，1+寺―1€9.【例4】有來自A,B,C,D,E五國的乒乓球裁判員各兩名，執(zhí)行某國際大賽的1,2,3,4,5號場地的乒乓球裁判工作，每個場地由2個來自不同國家的裁判組成，不同的安排方案共有多少種？【解】相當于把10個人分成兩組，每組5人，但是這5個人必須是分別來自A,B,C,D,E五國，由于是平

€ci)均分組，因此有一1種〔兩組之間沒有順序〕；然后這把一組先排列，有P5種排法；再把另外一組P2 52排列，要求同一個國家不能在一起，因此，是5個元素全錯為排列的問題，有D種排列。5因此一共有 ，P5，D=84480種。P2 5 52【變式】有5個客人參加宴會，他們把衣帽寄放在室內，宴會后每人戴了一頂帽子回家，回家后，他們的妻子都發(fā)現，他們戴了別人的帽子，問5個客人都不戴自己帽子的戴法有多少種？3〕部分錯位排列：將n個元素a,a,…,a排在n個位置上，記其中有且僅有m個元素的編號都在與其位置編號不一致的1 2n排法種數為：Dm，則:n【部分錯位排列公式】Dm二Cm，D.nnm注】部分錯位的意思就是剩余部分就正常排列，剩余位置就只有一種排法?！痉治觥坑星覂H有m個元素的編號都與其位置編號不一致的可能性共有Cm種，所以：Dm二Cm，D.n nnm例5】五個瓶子都貼了標簽，其中恰好貼錯了三個，則錯的可能情況共有多少種？【解】由公式，C3D二20，一共有20種可能。53變式1】編號為1,2,3,4,5的五個小球，放入編號為1,2,3,4,5的5個盒子中，并且每盒至少一個小球，其中只有一個小球的編號與盒子編號一致，問：有多少種不同的方法？【變式2】客運公司調整6輛客車的發(fā)車班次，要求變動其中的4輛客車的發(fā)車班次，其余2輛的不變，共有多少種不同的調整方案？4〕至少有其中的某m個元素錯位排列：r1r2的編號都與其位將n個元素a,a,…,a排在nr1r2的編號都與其位1 2n置編號不一致的排法種數為Hm，則:nHm=C0D+C1D+???+Cn?m?1D+CmD.n n—mm n—mm+1 n—m n?1 mn【證明】問題中對另外n-m個元素的編號是否與其位置編號一致沒有任何特別要求，當這n-m個元素中有且只有0,1,2,…,n-m?1,n-m個元素的編號與其位置編號不一致時，分別有：C0D,C1D,…,Cn?m?1D,CmD種排法，n?mmn?mm+1 n?mn?1mn所以：Hm=C0D+C1D……Cn?m?1D+CmD.n n?mmn?mm+1 n?mn?1mn【注】至少有其中的某m個元素錯位排列，就是禁位排列。5〕至少有m個元素錯位排列：將n個元素a,a,…,a排在n個位置上，記至少有其中有m個元素的編號都與其位置編號不一致的1 2n排法種數為Km，貝y：n【至少有m個元素錯位排列】Km，CmD€Cm+1D€€Cn-1D€C"D.n nmnm+1 nn-1nn【證明】有且只有m,m+1,m+2,…,n個元素的編號與其位置編號都不一致時，分別有：CmD,Cm+1D,…,Cn-1D,CnD種排法，所以：Km，CmD+Cm+1D€€Cn-1D+CnD.nmnm+1 nn-1nn n nmnm+1 nn-1nn【例6】編號為1,2,3,4,5的五個人，分別坐在編號為1,2,3,4,5的座位上，貝至多兩個號碼一致的坐法有多少種？【解】“至多兩個號碼一致”的意思就是“至少三個號碼不一致”，由公式：K3，C3D+C4D+C5D，109.5 3 5 4 5 5【例7】高二年級共有6個班，配備有6名數學教師，每班1名，學校準備適當調整這6名教師在該年級組內的任課班級，在以下情況下，各有多少種調整方案？〔1〕至少變動3名教師任課班級；〔2〕一定變動甲、乙、丙3名教師的任課班級；〔3〕變動甲、乙、丙3名教師的任課班級，其余3名教師的任課班級不變；〔4〕甲、乙、丙3名教師中至多變動1人的任課班級。【解】〔1〕由題意，知求K3，因為D=2,D=9,D=44,D=265，所以：TOC\o"1-5"\h\z3 4 5 6K3，C3D+C4D+C5D+C6D，704，6 6 3 6 4 6 5 6 6⑵屬于禁位排列問題，E3，C0P6—C1P5+C2P4—C3P3，426種。6 3 6 35 3 4 3 3〔3〕屬于部分錯位排列問題，可以看成是3個元素的全錯為排列問題，有D，2種。3〔4〕①甲、乙、丙3名教師的任課班級都不變時，另3名教師中至少有2個人的任課班級有變

動，另3名教師中至少有2人的任課班級有變動，其調整方案有C2D+C3D，5；②甲、乙、丙3名3 2 3 3教師中至少有1人的任課班級有變動，其調整方案有C1?C1D+C2D+C3D…，54種。3 32 3 3 3 4故甲、乙、丙3名教師中至多變動1人的任課班級的調整方案共有5+54，59.全錯為排列的另一種證法當n，1時，位置只有一個，而該元素不能排在該位置，所以，這種排法為0種，即D1，0.當n，2時，a不能排在第一個位置，a不能排在第二個位置的排法只有1種〈即a排在第二個位121置，a排在第一個位置〕，即D，1.22當n>3時，設a?i，1,2,3,…,n…不排在第i?i，1,2,3,…,n…位，分別填人下面的n個方框中。i12???i???n

第一步：考慮第1個位置，因為0］不能排在第一個位置，所以第1個位置的排法共有€n-1)種，下面假定a(2<i<n)排在第1個位置。i第二步：考慮第i個位置，根據第i個位置是否排a1可分成兩種情形：⑴當a排在第i個位置〔此時a已排在第1個位置〕，則還剩下(n-2)個元素及與之對應的(n-2)個1i位置，則問題變?yōu)?n-2)個元素的錯位排列問題，因此不同的排法有D種。n一2〔2〕當a不排在第i個位置〔此時a仍排在第1個位置〕，因為a和a均不能排在第i個位置，所以，當TOC\o"1-5"\h\z1 i 1ia排在第1個位置后，剩下的(n一1)個人：a,a,a,…,a，a,…,a和(n—1)個位置：2,3,…,n其中i 123 i，1i?1 na(k=2,3,…,i—1,i?1,…,n)不排在第k位,a不排在第i位。故此時也相當于(n—1)個元素的錯位排k1列，則不同的排法是D種?由乘法和加法原理知：D=(n，1)(D?D)〔*〕，其中D=0,D=1.n，1 n n，1 n，2 1 2下面用遞歸迭代法得出D的計算公式。由〔*下面用遞歸迭代法得出D的計算公式。由〔*〕得:nD(n-1)D (n-1)D n-1Dn= ? n-2_ ? ?—n!n! n! n(n一1)!n(n-1)D1D_]1) 、(n_2——_ 1——… n1、?—… n2、

?(n一1丿?(n—2)! <n丿(n一1)!n(n一2)!D1TOC\o"1-5"\h\z—-/ n1\ _—— ■/ n1\——-/ n2\! (n，1)!n<(n，1)! (n，2)!=(=(，1)2丄?丄nn一1G-n2、—y n3、)D)2，—11!丿、，)D)2，—11!丿_(_1》一2?丄._Ann，1n一2因為￡_0,D2_1，所以務—(二A_(—1)n? 利用累加法,求得■nn！2！3！+???+(求得■nn！2！3！+???+(-1)n?—n！1！2！3！+???+(_1》丄n！1-1+2丿，掃…心〉?n1-1+2丿，掃…心〉?n所以D_n!ni_0即在n個不同元素的全排列中，錯排列數為：D_(n—1)(D+D)，其中D_0,D_1n n，1 n，2 1 21-丄+丄-丄+???+(-1)丄1！ 2！ 3！ n！5.全錯為排列的推廣,工(T>，n！?/i，o i！上面我們討論了n個元素的全錯位排列問題。如果我們換一個角度來看，把n個元素看成n組人，則為每一組只有1人的全錯位排列。為此，我們自然會想到每組有2人、3人甚至n個人時的情況又會如何呢？為此我們將此模型進一步推廣：【定理1】kn個人，每組k個人，共n組，坐到n行k列共kn個位置中,但假設第i(i，1,2,3,…,k)組不能坐到第i(i，1,2,3,…,k)行中〔組內成員可換位置〕。不同的坐法有:a，Pkkn k位排列數〕。，其中a，0,a，Cpk),k1 k2 k且a，Dkn n-(Pk)〔D為n個元素的錯kn證明：當n，證明：當n，1時,當n，2時,以a，(Pk)種。k2 k當n>3時,因為第一組成員不能坐在第一行中，所以ak1因為第1組人做到第2組位置構成全排列，第二組人坐到第1組位置又構成全排列，所首先考慮第1行的位置，可能坐此位置的人共有(n-1)組，但無論哪一組人坐，不同的坐法有(n-加種。下面假定第1行被第i組坐了。接著，再考慮第i行，同樣可分兩種情況討論:⑴假設第i行被第1組人坐〔此時第1行被第i組人坐〕，還剩下(n-2)組人和與之對應的(n-2)組位置，則共有Pk-a()種不同的坐法。kk(n-2)〔2〕假設第i行不被第1組人坐〔此時第1行仍被第i組人坐〕.則剩下(n-1)組人和(n-1)組位置，則不同的坐法共有a()種。由乘法和加法原理知：a，Pkk(n-1) kn k事實上，此問題也可以這樣考慮