错位排列和禁位排列

1错位排列和禁位排列1.问题提出（1）某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？（2）有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉（LeonardEuler，1707—1783）称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰•伯努利（JohnBernoulli，1667—1748）的儿子丹尼尔•伯努利（DanidBernoulli，1700—1782）提出来的，大意如下：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封。问全部装错了信封的装法有几种？2.错位排列和禁位排列1）错位排列：n个相异元素中mmn个元素12,,,miiiaaa，其中1,2,,kiakm不在第1,2,,kikm个位置（一下简称其为kia的本位），而其他nm个元素中的任何一个都在原来的位置（本位）的排列。如果n个元素都不在本位，称为全错位排列。2）禁位排列（一个元素禁止排在一个位置）：n个相异元素中mmn个元素12,,,miiiaaa，其中1,2,,kiakm不能排在第1,2,,kjkm个位置的排列。3）两者的区别在于：错位排列中除这m个元素之外的其他nm个元素都在本位，即这m个元素只能在m个位置12,,,miii中排列，且不出现1,2,,kiakm在ki位的情况；而禁位排列中只限制m个元素不在本位，因此1,2,,kiakm可以排在1,2,,n中除ki之外的任何位置。3.禁位排列与全错位排列的种数1）禁位排列数：求禁位排列数，只需从n个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是111nmnCP，有两个元素占本位的排列数是211nmnCP，……，n个元素占本位的排列数是mnmmnmCP.记错位排列和禁位排列的排列数分别为,mmnnDE，用nD表示n个元素全错位排列。则由容斥原理有：【禁位排列公式】012121mmmnmmmmECnCnCnCnm！！！！【证明】①当0m时，等式左边为0nE，表示n个元素没有限制，所以有nnPn！，等式右边本应该有1m项，当0m时，只有1项，就是00Cnn！！.等式成立；②假设01kikininkniiECP；2③那么当1mk时，设第1k个元素为a，则前k个元素不占本位而a占本位的排列数为：11kkknnnEEE110011kkiiiniiniknikniiiCPCP，1011220112112121111kkknnnknknnknkknkknknknknkknknknkknkCPCPCPCPCPCPCPCP10111111kikniiniknkknkkniknkiCPCCPCP10111111111kikniniknkknkniknkiCPCPCP1101kiinikniiCP因此对于0mn时，公式1均成立。【例1】5个人站成一排，其中甲不站排头，乙不站排尾，共有多少种不同的站法。【解】由公式得：2051423525242378ECPCPCP【例2】6个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法。【解】由公式得：306152433636353433426ECPCPCPCP【变式1】用0,1,2,3,4这5个数字，组成没有重复数字的5位数，百位上不排3，一共有多少种排法？【变式2】在由1,2,3,5,9组成的没有重复数字的五位数中，共有多少个小于60000的奇数？2）全错为排列数：全错为排列就是n个元素，全不排在本位，实际上就是禁位排列中，当mn的情况，因此：【全错位排列公式】0121210nnnnnnnnnDECnCnCnC！！！！.另一种写法：01111111123innniDnnni！！！！！！！.【例3】寝室四个人每人写一张贺卡，然后互相交换，每个人不拿到自己的卡片，一共有多少种可能？【解】由公式得：0413223140444434241409DCPCPCPCPCP；用另外一个公式得：411114191234D！！！！！.【例4】有来自,,,,ABCDE五国的乒乓球裁判员各两名，执行某国际大赛的1,2,3,4,5号场地的乒乓球裁判工作，每个场地由2个来自不同国家的裁判组成，不同的安排方案共有多少种？【解】相当于把10个人分成两组，每组5人，但是这5个人必须是分别来自,,,,ABCDE五国，由于是平3均分组，因此有51222CP种（两组之间没有顺序）；然后这把一组先排列，有55P种排法；再把另外一组排列，要求同一个国家不能在一起，因此，是5个元素全错为排列的问题，有5D种排列。因此一共有5125552284480CPDP种。【变式】有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？3）部分错位排列：将n个元素12,,,naaa排在n个位置上，记其中有且仅有m个元素的编号都在与其位置编号不一致的排法种数为：mnD，则：【部分错位排列公式】mmnnmDCD.【注】部分错位的意思就是剩余部分就正常排列，剩余位置就只有一种排法。【分析】有且仅有m个元素的编号都与其位置编号不一致的可能性共有mnC种，所以：mmnnmDCD.【例5】五个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况共有多少种？【解】由公式，35320CD，一共有20种可能。【变式1】编号为1,2,3,4,5的五个小球，放入编号为1,2,3,4,5的5个盒子中，并且每盒至少一个小球，其中只有一个小球的编号与盒子编号一致，问：有多少种不同的方法？【变式2】客运公司调整6辆客车的发车班次，要求变动其中的4辆客车的发车班次，其余2辆的不变，共有多少种不同的调整方案？4）至少有其中的某m个元素错位排列：将n个元素12,,,naaa排在n个位置上，记至少有其中的某m个元素，12,,,mrrraaa的编号都与其位置编号不一致的排法种数为mnH，则：01111mnmmnnmmnmmnmnmnHCDCDCDCD.【证明】问题中对另外nm个元素的编号是否与其位置编号一致没有任何特别要求，当这nm个元素中有且只有0,1,2,,1,nmnm个元素的编号与其位置编号不一致时，分别有：01111,,,,nmmnmmnmmnmnmnCDCDCDCD种排法，所以：01111mnmmnnmmnmmnmnmnHCDCDCDCD.【注】至少有其中的某m个元素错位排列，就是禁位排列。5）至少有m个元素错位排列：将n个元素12,,,naaa排在n个位置上，记至少有其中有m个元素的编号都与其位置编号不一致的排4法种数为mnK，则：【至少有m个元素错位排列】1111mmmnnnnmnmnnnnKCDCDCDCD.【证明】有且只有,1,2,,mmmn个元素的编号与其位置编号都不一致时，分别有：1111,,,,mmnnnmnmnnnnCDCDCDCD种排法，所以：1111mmmnnnnmnmnnnnKCDCDCDCD.【例6】编号为1,2,3,4,5的五个人，分别坐在编号为1,2,3,4,5的座位上，则至多两个号码一致的坐法有多少种？【解】“至多两个号码一致”的意思就是“至少三个号码不一致”，由公式：33455535455109KCDCDCD.【例7】高二年级共有6个班，配备有6名数学教师，每班1名，学校准备适当调整这6名教师在该年级组内的任课班级，在以下情况下，各有多少种调整方案？（1）至少变动3名教师任课班级；（2）一定变动甲、乙、丙3名教师的任课班级；（3）变动甲、乙、丙3名教师的任课班级，其余3名教师的任课班级不变；（4）甲、乙、丙3名教师中至多变动1人的任课班级。【解】（1）由题意，知求36K，因为34562,9,44,265DDDD，所以：33456663646566704KCDCDCDCD，（2）属于禁位排列问题，306152433636353433426ECPCPCPCP种。（3）属于部分错位排列问题，可以看成是3个元素的全错为排列问题，有32D种。（4）①甲、乙、丙3名教师的任课班级都不变时，另3名教师中至少有2个人的任课班级有变动，另3名教师中至少有2人的任课班级有变动，其调整方案有2332335CDCD；②甲、乙、丙3名教师中至少有1人的任课班级有变动，其调整方案有1123332333454CCDCDCD种。故甲、乙、丙3名教师中至多变动1人的任课班级的调整方案共有55459.4.全错为排列的另一种证法当1n时，位置只有一个，而该元素不能排在该位置，所以，这种排法为0种，即10D.当2n时，1a不能排在第一个位置，2a不能排在第二个位置的排法只有1种〈即1a排在第二个位置，2a排在第一个位置），即21D.当3n时，设1,2,3,,iain不排在第1,2,3,,iin位，分别填人下面的n个方框中。12…i…n5第一步：考虑第1个位置，因为1a不能排在第一个位置，所以第1个位置的排法共有1n种，下面假定2iain排在第1个位置。第二步：考虑第i个位置，根据第i个位置是否排1a可分成两种情形：（1）当1a排在第i个位置（此时ia已排在第1个位置），则还剩下2n个元素及与之对应的2n个位置，则问题变为2n个元素的错位排列问题，因此不同的排法有2nD种。（2）当1a不排在第i个位置（此时ia仍排在第1个位置），因为1a和ia均不能排在第i个位置，所以，当ia排在第1个位置后，剩下的1n个人：12311,,,,,,,iinaaaaaa和1n个位置：2,3,,n其中2,3,,1,1,,kakiin不排在第k位，1a不排在第i位。故此时也相当于1n个元素的错位排列，则不同的排法是1nD种.由乘法和加法原理知：121nnnDnDD（*），其中120,1DD.下面用递归迭代法得出nD的计算公式。由（*）得：122112111111=111212nnnnnnnnDnDnDDDDDnnnnnnnnnnnnn！！！！！！！所以1121112nnnnDDDDnnnnn！！！！223111123nnDDnnnn！！2211111112321nDDnnn！！因为120,1DD，所以1111nnnDDnnn！！！，利用累加法，求得11111111