错位排列和禁位排列

错位排列和禁位排列问题提出〔1〕某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？〔2〕有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉〔LeonardEuler，1707—1783〕称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰•伯努利〔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〕两者的区别在于：错位排列中除这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个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法。【解】由公式得：E3€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五国的乒乓球裁判员各两名，执行某国际大赛的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个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？3〕部分错位排列：将n个元素a,a,…,a排在n个位置上，记其中有且仅有m个元素的编号都在与其位置编号不一致的1 2n排法种数为：Dm，则:n【部分错位排列公式】Dm二Cm，D.nnm注】部分错位的意思就是剩余部分就正常排列，剩余位置就只有一种排法。【分析】有且仅有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辆客车的发车班次，要求变动其中的4辆客车的发车班次，其余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位置，则问题变为(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事实上，此问题也可以这样考虑