2022年错位排列和禁位排列 .pdf

《2022年错位排列和禁位排列 .pdf》由会员分享，可在线阅读，更多相关《2022年错位排列和禁位排列 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 错位排列和禁位排列1.问题提出 1某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？ 2有 5 个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5 个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉Leonard Euler，1707 1783称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰?伯努利 John Bernoulli ，16671748 的儿子丹

2、尼尔 ?伯努利Danid Bernoulli ，17001782提出来的，大意如下：一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封。问全部装错了信封的装法有几种？2.错位排列和禁位排列1错位排列：n 个相异元素中m mn个元素12,miiiaaa，其中1,2,kiakm不在第1,2,kikm个位置一下简称其为kia的本位，而其他nm个元素中的任何一个都在原来的位置本位的排列。如果n 个元素都不在本位，称为全错位排列。2禁位排列一个元素禁止排在一个位置：n 个相异元素中m mn个元素12,miiiaaa，其中1,2,kiakm不能排在第1,2,kjkm个位置的排列。

3、3两者的区别在于：错位排列中除这m 个元素之外的其他nm个元素都在本位，即这m 个元素只能在m个位置12, ,mi ii中排列，且不出现1,2,kiakm在ki位的情况；而禁位排列中只限制m 个元素不在本位，因此1,2,kiakm可以排在1,2,n中除ki之外的任何位置。3.禁位排列与全错位排列的种数1禁位排列数：求禁位排列数，只需从n 个元素的全排列中除去指定元素占本位的排列即可，其中有1 个元素占本位的排列数是111nmnC P，有两个元素占本位的排列数是211nmnC P， n 个元素占本位的排列数是mn mmn mC P. 记错位排列和禁位排列的排列数分别为,mmnnDE，用nD表示

4、n 个元素全错位排列。则由容斥原理有：【禁位排列公式】012121mmmnmmmmEC nCnCnCnm！【证明】 当0m时，等式左边为0nE，表示 n 个元素没有限制，所以有nnPn！，等式右边本应该有1m项，当0m时，只有1 项，就是00C nn！.等式成立；假设01kikin inkn iiEC P；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页2 那么当1mk时，设第1k个元素为a，则前 k 个元素不占本位而a 占本位的排列数为：11kkknnnEEE110011kkiiin iin ikn ikn iiiC PC P，

5、1011220112112121111kkknnnkn knnknkkn kknknknkn kknknkn kkn kC PC PC PC PC PC PC PC P10111111kikniin ikn kknkkn iknkiC PCCPC P10111111111kiknin iknkknkn ikn kiCPCPCP1101kiin ikn iiCP因此对于0mn时，公式1 均成立。【例 1】 5个人站成一排，其中甲不站排头，乙不站排尾，共有多少种不同的站法。【解】由公式得：2051423525242378EC PC PC P【例 2】6 个人站成一排，其中甲不站第一位，乙不站第二位

6、，丙不站第三位，共有多少种不同的站法。【解】由公式得：306152433636353433426EC PC PC PC P【变式 1】用0,1,2,3,4这 5 个数字，组成没有重复数字的5 位数，百位上不排3，一共有多少种排法？【变式 2】在由1,2,3,5,9组成的没有重复数字的五位数中，共有多少个小于60000 的奇数？2全错为排列数：全错为排列就是n 个元素，全不排在本位，实际上就是禁位排列中，当mn的情况，因此：【全错位排列公式】0121210nnnnnnnnnDEC nCnCnC！. 另一种写法：01111111123innniDnnni！. 【例 3】寝室四个人每人写一张贺卡，然

7、后互相交换，每个人不拿到自己的卡片，一共有多少种可能？【解】由公式得：0413223140444434241409DC PC PC PC PC P；用另外一个公式得：411114191234D！. 【例 4】有来自,A B C D E五国的乒乓球裁判员各两名，执行某国际大赛的1,2,3,4,5号场地的乒乓球裁判工作，每个场地由2 个来自不同国家的裁判组成，不同的安排方案共有多少种？【解】相当于把10 个人分成两组，每组5 人，但是这5 个人必须是分别来自,A B C D E五国，由于是平精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7

8、 页3 均分组，因此有51222CP种两组之间没有顺序；然后这把一组先排列，有55P种排法；再把另外一组排列，要求同一个国家不能在一起，因此，是5 个元素全错为排列的问题，有5D种排列。因此一共有5125552284480CPDP种。【变式】有5 个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5 个客人都不戴自己帽子的戴法有多少种？3部分错位排列：将n个元素12,na aa排在n个位置上，记其中有且仅有m个元素的编号都在与其位置编号不一致的排法种数为：mnD，则：【部分错位排列公式】mmnnmDCD. 【注】部分错位的意思就是

9、剩余部分就正常排列，剩余位置就只有一种排法。【分析】有且仅有m个元素的编号都与其位置编号不一致的可能性共有mnC种，所以：mmnnmDCD. 【例 5】五个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况共有多少种？【解】由公式，35320C D，一共有20 种可能。【变式 1】编号为1,2,3,4,5的五个小球，放入编号为1,2,3,4,5的 5 个盒子中，并且每盒至少一个小球，其中只有一个小球的编号与盒子编号一致，问：有多少种不同的方法？【变式 2】客运公司调整6 辆客车的发车班次，要求变动其中的4 辆客车的发车班次，其余2 辆的不变，共有多少种不同的调整方案？4至少有其中的某m 个元素

10、错位排列：将n个元素12,na aa排在n个位置上，记至少有其中的某m个元素，12,mrrraaa的编号都与其位置编号不一致的排法种数为mnH，则：01111mn mmnn mmn mmn mnmnHCDCDCDC D. 【证明】问题中对另外nm个元素的编号是否与其位置编号一致没有任何特别要求，当这nm个元素中有且只有0,1,2,1,nmnm个元素的编号与其位置编号不一致时，分别有：01111,nmmn mmn mmn mnmnCDCDCDC D种排法，所以：01111mn mmnn mmn mmn mnmnHCDCDCDC D. 【注】至少有其中的某m 个元素错位排列，就是禁位排列。5至少有

11、 m 个元素错位排列：将n个元素12,na aa排在n个位置上，记至少有其中有m个元素的编号都与其位置编号不一致的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页4 排法种数为mnK，则：【至少有m 个元素错位排列】1111mmmnnnnmnmnnnnKC DCDCDC D. 【证明】有且只有,1,2,m mmn个元素的编号与其位置编号都不一致时，分别有：1111,mmnnnmnmnnnnC DCDCDC D种排法，所以：1111mmmnnnnmnmnnnnKC DCDCDC D.【例 6】编号为1,2,3,4,5的五个人，分别坐

12、在编号为1,2,3,4,5的座位上，则至多两个号码一致的坐法有多少种？【解】“至多两个号码一致”的意思就是“至少三个号码不一致”，由公式：33455535455109KC DC DC D. 【例 7】高二年级共有6 个班，配备有6 名数学教师，每班1 名，学校准备适当调整这6 名教师在该年级组内的任课班级，在以下情况下，各有多少种调整方案？1至少变动3 名教师任课班级；2一定变动甲、乙、丙3 名教师的任课班级；3变动甲、乙、丙3 名教师的任课班级，其余3 名教师的任课班级不变；4甲、乙、丙3名教师中至多变动1 人的任课班级。【解】 1由题意，知求36K，因为34562,9,44,265DDDD

13、，所以：33456663646566704KC DC DC DC D，2属于禁位排列问题，306152433636353433426EC PC PC PC P种。3属于部分错位排列问题，可以看成是3 个元素的全错为排列问题，有32D种。4甲、乙、丙3 名教师的任课班级都不变时，另3 名教师中至少有2 个人的任课班级有变动，另 3 名教师中至少有2 人的任课班级有变动，其调整方案有2332335C DC D；甲、乙、丙3 名教师中至少有1 人的任课班级有变动，其调整方案有1123332333454CC DC DC D种。故甲、乙、丙3 名教师中至多变动1 人的任课班级的调整方案共有55459.4

14、.全错为排列的另一种证法当1n时，位置只有一个，而该元素不能排在该位置，所以，这种排法为0 种，即10D. 当2n时，1a不能排在第一个位置，2a不能排在第二个位置的排法只有1 种即1a排在第二个位置，2a排在第一个位置，即21D. 当3n时，设1,2,3,ia in不排在第1,2,3,i in位，分别填人下面的n 个方框中。1 2 i n 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页5 第一步：考虑第1 个位置，因为1a不能排在第一个位置，所以第1 个位置的排法共有1n种，下面假定2iain排在第1 个位置。第二步：考虑第i

15、 个位置，根据第i 个位置是否排1a可分成两种情形：1当1a排在第 i 个位置此时ia已排在第 1 个位置，则还剩下2n个元素及与之对应的2n个位置，则问题变为2n个元素的错位排列问题，因此不同的排法有2nD种。2当1a不排在第i 个位置此时ia仍排在第 1 个位置，因为1a和ia均不能排在第i 个位置，所以，当ia排在第 1 个位置后，剩下的1n个人：12311,iina aaaaa和1n个位置：2,3,n其中2,3,1,1,kakiin不排在第k 位，1a不排在第i 位。故此时也相当于1n个元素的错位排列，则不同的排法是1nD种.由乘法和加法原理知：121nnnDnDD*，其中120,1D

16、D. 下面用递归迭代法得出nD的计算公式。由 *得：122112111111=111212nnnnnnnnDnDnDDDDDnnnnnnnnnnnnn！所以1121112nnnnDDDDnnnnn！223111123nnDDn nnn！2211111112321nDDn nn！因为120,1DD，所以1111nnnDDnnn！，利用累加法，求得111111111123123nnnDnnn！所以01111111123innniDnnni！即在n个不同元素的全排列中，错排列数为：121nnnDnDD，其中120,1DD精选学习资料 - - - - - - - - - 名师归纳总结 - - - -

17、- - -第 5 页，共 7 页6 01111111123innniDnnni！5.全错为排列的推广上面我们讨论了n 个元素的全错位排列问题。如果我们换一个角度来看，把n 个元素看成n组人，则为每一组只有1 人的全错位排列。为此，我们自然会想到每组有2 人、 3 人甚至 n 个人时的情况又会如何呢？为此我们将此模型进一步推广：【定理 1】kn个人，每组k 个人，共n 组，坐到n 行 k 列共 kn 个位置中，但假设第1,2,3,i ik组不能坐到第1,2,3,i ik行中组内成员可换位置。不同的坐法有：121kkknkkk nk naPnaP a，其中2120,kkkkaaP，且kkknnka

18、DPnD为 n 个元素的错位排列数。证明：当1n时，因为第一组成员不能坐在第一行中，所以10ka. 当2n时，因为第1 组人做到第2 组位置构成全排列，第二组人坐到第1 组位置又构成全排列，所以22kkkaP种。当3n时，首先考虑第1 行的位置，可能坐此位置的人共有1n组，但无论哪一组人坐，不同的坐法有1kknP种。下面假定第1 行被第 i 组坐了。接着，再考虑第i 行，同样可分两种情况讨论：1假设第i 行被第 1组人坐此时第1 行被第 i 组人坐，还剩下2n组人和与之对应的2n组位置，则共有2kkk nPa种不同的坐法。2假设第i 行不被第1 组人坐此时第1 行仍被第i 组人坐 .则剩下1n

19、组人和1n组位置，则不同的坐法共有1k na种。由乘法和加法原理知：121kkknkkk nkaPnaP a，事实上，此问题也可以这样考虑：第一步以组为单位，恰好为n 个元素的错排列，公有nD种排列方法；第二步，每一组k 个元素均进行全排列，共有kkkP种排列方法。由乘法原理知：kkknnkaDP从上面这个通项公式，我们可以看出1k时正好是错位排列的通解。【定理 2】kn个人，每组k 个人，共 n 组，坐到n 行 k 列，共如个位置中，但假设第1,2,3,i ik组不能坐到第1,2,3,i ik行中，组内成员可换位置，但每组内第j 人不能坐到第j 列。共有坐法为：111111iinkknnki

20、iEDDnkii！ ！精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页7 【证明】此问题可以这样考虑：第一步以组为单位，恰好为n 个元素的错排列，共有nD种排列方法；第二步，每组内第j 人不能坐到第j 列，即每一组k 个元素均进行错排列，共有kD种排列方法。由乘法原理知：111111iinkknnkiiEDDnkii！ ！【定理 3】编号为111212,knnkaaaaa的nk个人每组k 个人，共n 组，坐到编号为111212,knnkbbbbb的nk个位置中共n 行 k 列，但编号为ija的人不能坐到编号为ijb的位置中，则不同的坐法为：111111111123inknkknnkiFDnknknki！【分析】此问题可以这样考虑，编号为ija的人不能坐到编号为ijb的位置中实际上就相当于所有元素的错排列。证明略参照原数学模型的证明。从上面这个通项公式中，我们可以看出：当1n或1k时正好为错位排列的通解。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页