错位排列和禁位排列(共7页).docx

精选优质文档-----倾情为你奉上错位排列和禁位排列1.问题提出（1）某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？（2）有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉 （Leonard Euler，1707 —1783）称为“组合数论”的一个妙题的“装错信封问题”的两个特例装错信封问题”是由当时最有名的数学家约翰•伯努利（John Bernoulli，1667—1748） 的儿子丹尼尔•伯努利 （Danid Bernoulli，1700—1782）提出来的，大意如下：一个人写了 n 封不同的信及相应的n个不同的信封，他把这n封信都装错了信封问全部装错了信封的装法有几种？2.错位排列和禁位排列1）错位排列：n个相异元素中个元素，其中不在第个位置（一下简称其为的本位），而其他个元素中的任何一个都在原来的位置（本位）的排列如果n个元素都不在本位，称为全错位排列。

2）禁位排列（一个元素禁止排在一个位置）：n个相异元素中个元素，其中不能排在第个位置的排列3）两者的区别在于：错位排列中除这m个元素之外的其他个元素都在本位，即这m个元素只能在m个位置中排列，且不出现在位的情况；而禁位排列中只限制m个元素不在本位，因此可以排在中除之外的任何位置3.禁位排列与全错位排列的种数1）禁位排列数：求禁位排列数，只需从n个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是，有两个元素占本位的排列数是，……，n个元素占本位的排列数是.记错位排列和禁位排列的排列数分别为，用表示n个元素全错位排列则由容斥原理有：【禁位排列公式】【证明】①当时，等式左边为，表示n个元素没有限制，所以有，等式右边本应该有项，当时，只有1项，就是.等式成立；②假设；③那么当时，设第个元素为a，则前k个元素不占本位而a占本位的排列数为：，因此对于时，公式1均成立例1】 5个人站成一排，其中甲不站排头，乙不站排尾，共有多少种不同的站法 【解】由公式得：【例2】6个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法解】由公式得：【变式1】用这5个数字，组成没有重复数字的5位数，百位上不排3，一共有多少种排法？【变式2】在由组成的没有重复数字的五位数中，共有多少个小于60000的奇数？2）全错为排列数：全错为排列就是n个元素，全不排在本位，实际上就是禁位排列中，当的情况，因此：【全错位排列公式】.另一种写法：.【例3】寝室四个人每人写一张贺卡，然后互相交换，每个人不拿到自己的卡片，一共有多少种可能？【解】由公式得：；用另外一个公式得：.【例4】有来自五国的乒乓球裁判员各两名，执行某国际大赛的号场地的乒乓球裁判工作，每个场地由2个来自不同国家的裁判组成，不同的安排方案共有多少种？【解】相当于把10个人分成两组，每组5人，但是这5个人必须是分别来自五国，由于是平均分组，因此有种（两组之间没有顺序）；然后这把一组先排列，有种排法；再把另外一组排列，要求同一个国家不能在一起，因此，是5个元素全错为排列的问题，有种排列。

因此一共有种变式】有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？3）部分错位排列：将个元素排在个位置上，记其中有且仅有个元素的编号都在与其位置编号不一致的排法种数为：，则：【部分错位排列公式】.【注】部分错位的意思就是剩余部分就正常排列，剩余位置就只有一种排法分析】有且仅有个元素的编号都与其位置编号不一致的可能性共有种，所以：.【例5】五个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况共有多少种？【解】由公式，，一共有20种可能变式1】编号为的五个小球，放入编号为的5个盒子中，并且每盒至少一个小球，其中只有一个小球的编号与盒子编号一致，问：有多少种不同的方法？【变式2】客运公司调整6辆客车的发车班次，要求变动其中的4辆客车的发车班次，其余2辆的不变，共有多少种不同的调整方案？4）至少有其中的某m个元素错位排列：将个元素排在个位置上，记至少有其中的某个元素，的编号都与其位置编号不一致的排法种数为，则：.【证明】问题中对另外个元素的编号是否与其位置编号一致没有任何特别要求，当这个元素中有且只有个元素的编号与其位置编号不一致时，分别有：种排法，所以：.【注】至少有其中的某m个元素错位排列，就是禁位排列。

5）至少有m个元素错位排列：将个元素排在个位置上，记至少有其中有个元素的编号都与其位置编号不一致的排法种数为，则：【至少有m个元素错位排列】.【证明】有且只有个元素的编号与其位置编号都不一致时，分别有：种排法，所以：.【例6】编号为的五个人，分别坐在编号为的座位上，则至多两个号码一致的坐法有多少种？【解】“至多两个号码一致”的意思就是“至少三个号码不一致”，由公式：.【例7】高二年级共有6个班，配备有6名数学教师，每班1名，学校准备适当调整这6名教师在该年级组内的任课班级，在以下情况下，各有多少种调整方案？（1）至少变动3名教师任课班级；（2）一定变动甲、乙、丙3名教师的任课班级；（3）变动甲、乙、丙3名教师的任课班级，其余3名教师的任课班级不变；（4）甲、乙、丙3名教师中至多变动1人的任课班级解】（1）由题意，知求，因为，所以：， （2）属于禁位排列问题，种 （3）属于部分错位排列问题，可以看成是3个元素的全错为排列问题，有种 （4）①甲、乙、丙3名教师的任课班级都不变时，另3名教师中至少有2个人的任课班级有变动，另3名教师中至少有2人的任课班级有变动，其调整方案有；②甲、乙、丙3名教师中至少有1人的任课班级有变动，其调整方案有种。

故甲、乙、丙3名教师中至多变动1人的任课班级的调整方案共有.4.全错为排列的另一种证法当时，位置只有一个，而该元素不能排在该位置，所以，这种排法为0种，即.当时，不能排在第一个位置，不能排在第二个位置的排法只有1种〈即排在第二个位置，排在第一个位置） ，即.当时，设不排在第位，分别填人下面的n个方框中12…i…n第一步：考虑第1个位置，因为不能排在第一个位置，所以第 1个位置的排法共有 种，下面假定排在第 1个位置第二步：考虑第 i个位置，根据第 i个位置是否排可分成两种情形：（1）当排在第i个位置（此时已排在第1个位置），则还剩下个元素及与之对应的个位置，则问题变为个元素的错位排列问题，因此不同的排法有种2）当不排在第i个位置（此时仍排在第1个位置），因为和均不能排在第i个位置，所以，当排在第1个位置后，剩下的个人：和个位置：其中不排在第 k 位，不排在第i位故此时也相当于个元素的错位排列，则不同的排法是种.由乘法和加法原理知：（*），其中. 下面用递归迭代法得出的计算公式 由（*）得：所以 因为，所以，利用累加法，求得所以即在个不同元素的全排列中，错排列数为：，其中5.全错为排列的推广上面我们讨论了n个元素的全错位排列问题。

如果我们换一个角度来看，把n个元素看成n组人，则为每一组只有1人的全错位排列为此，我们自然会想到每组有2人、3人甚至n个人时的情况又会如何呢？为此我们将此模型进一步推广：【定理1】个人，每组 k个人，共 n 组，坐到n行k列共kn个位置中，但若第组不能坐到第行中（组内成员可换位置）不同的坐法有：，其中，且（为n个元素的错位排列数）证明：当时，因为第一组成员不能坐在第一行中，所以. 当时，因为第1组人做到第2组位置构成全排列，第二组人坐到第1组位置又构成全排列，所以种 当时，首先考虑第1行的位置，可能坐此位置的人共有组，但无论哪一组人坐，不同的坐法有种下面假定第 1行被第i组坐了接着，再考虑第i行，同样可分两种情况讨论：（1）若第i行被第1组人坐（此时第 1行被第i组人坐），还剩下组人和与之对应的组位置，则共有种不同的坐法2）若第i行不被第1组人坐（此时第1行仍被第i组人坐）.则剩下组人和组位置，则不同的坐法共有种由乘法和加法原理知：， 事实上，此问题也可以这样考虑：第一步以组为单位，恰好为n个元素的错排列，公有种排列方法；第二步，每一组k个元素均进行全排列，共有种排列方法。

由乘法原理知： 从上面这个通项公式，我们可以看出时正好是错位排列的通解定理2】个人，每组k个人，共n组，坐到n行k列，共如个位置中，但若第组不能坐到第行中，组内成员可换位置，但每组内第j人不能坐到第j列共有坐法为：【证明】 此问题可以这样考虑：第一步以组为单位，恰好为n个元素的错排列，共有种排列方法；第二步，每组内第j人不能坐到第j列，即每一组k个元素均进行错排列，共有种排列方法由乘法原理知：【定理3】编号为的个人（每组k个人，共n组），坐到编号为的个位置中（共n行k列），但编号为的人不能坐到编号为的位置中，则不同的坐法为： 【分析】 此问题可以这样考虑，编号为的人不能坐到编号为的位置中实际上就相当于所有元素的错排列证明略（参照原数学模型的证明） 从上面这个通项公式中，我们可以看出：当或时正好为错位排列的通解专心---专注---专业。