错位排列和禁位排列

《错位排列和禁位排列》由会员分享，可在线阅读，更多相关《错位排列和禁位排列（8页珍藏版）》请在装配图网上搜索。

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

2、lli，10078）提出来的,大意如下：一种人写了n 封不同的信及相应的n个不同的信封，她把这n封信都装错了信封。问所有装错了信封的装法有几种？.错位排列和禁位排列)错位排列:个相异元素中个元素，其中不在第个位置（一下简称其为的本位）,而其她个元素中的任何一种都在本来的位置（本位)的排列。如果个元素都不在本位，称为全错位排列。）禁位排列(一种元素严禁排在一种位置）:个相异元素中个元素，其中不能排在第个位置的排列。3)两者的区别在于：错位排列中除这m个元素之外的其她个元素都在本位，即这m个元素只能在m个位置中排列，且不出目前位的状况；而禁位排列中只限制m个元素不在本位，因此可以排在中除之外的任何

3、位置。.禁位排列与全错位排列的种数)禁位排列数:求禁位排列数，只需从n个元素的全排列中除去指定元素占本位的排列即可,其中有个元素占本位的排列数是,有两个元素占本位的排列数是,n个元素占本位的排列数是记错位排列和禁位排列的排列数分别为，用表达个元素全错位排列。则由容斥原理有：【禁位排列公式】【证明】当时，等式左边为,表达n个元素没有限制,因此有，等式右边本应当有项,当时，只有项，就是.等式成立;假设;那么当时,设第个元素为a，则前k个元素不占本位而a占本位的排列数为:,因此对于时,公式均成立。【例】 5个人站成一排，其中甲不站排头，乙不站排尾，共有多少种不同的站法。 【解】由公式得:【例】6个人

4、站成一排,其中甲不站第一位，乙不站第二位，丙不站第三位,共有多少种不同的站法。【解】由公式得：【变式1】用这5个数字，构成没有反复数字的5位数，百位上不排3,一共有多少种排法?【变式2】在由构成的没有反复数字的五位数中，共有多少个不不小于60000的奇数？2)全错为排列数：全错为排列就是n个元素,全不排在本位,事实上就是禁位排列中,当的状况，因此:【全错位排列公式】.另一种写法：.【例3】寝室四个人每人写一张贺卡,然后互相互换,每个人不拿到自己的卡片,一共有多少种也许？【解】由公式得：；用此外一种公式得：.【例4】有来自五国的乒乓球裁判员各两名，执行某国际大赛的号场地的乒乓球裁判工作，每个场地

5、由2个来自不同国家的裁判构成,不同的安排方案共有多少种?【解】相称于把10个人提成两组,每组5人,但是这5个人必须是分别来自五国，由于是平均分组，因此有种（两组之间没有顺序）;然后这把一组先排列,有种排法;再把此外一组排列，规定同一种国家不能在一起,因此，是5个元素全错为排列的问题,有种排列。因此一共有种。【变式】有5个客人参与宴会,她们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家,回家后，她们的妻子都发现,她们戴了别人的帽子,问5个客人都不戴自己帽子的戴法有多少种？)部分错位排列:将个元素排在个位置上，记其中有且仅有个元素的编号都在与其位置编号不一致的排法种数为:,则：【部分错位排列公式】【

6、注】部分错位的意思就是剩余部分就正常排列,剩余位置就只有一种排法。【分析】有且仅有个元素的编号都与其位置编号不一致的也许性共有种，因此:.【例5】五个瓶子都贴了标签,其中正好贴错了三个,则错的也许状况共有多少种?【解】由公式,一共有0种也许。【变式】编号为的五个小球，放入编号为的个盒子中,并且每盒至少一种小球,其中只有一种小球的编号与盒子编号一致,问：有多少种不同的措施?【变式2】客运公司调节6辆客车的发车班次，规定变动其中的4辆客车的发车班次,其他2辆的不变,共有多少种不同的调节方案？)至少有其中的某m个元素错位排列:将个元素排在个位置上,记至少有其中的某个元素,的编号都与其位置编号不一致的

7、排法种数为，则:.【证明】问题中对此外个元素的编号与否与其位置编号一致没有任何特别规定，当这个元素中有且只有个元素的编号与其位置编号不一致时，分别有:种排法,因此:.【注】至少有其中的某m个元素错位排列，就是禁位排列。）至少有m个元素错位排列:将个元素排在个位置上，记至少有其中有个元素的编号都与其位置编号不一致的排法种数为，则:【至少有m个元素错位排列】.【证明】有且只有个元素的编号与其位置编号都不一致时,分别有：种排法,因此：.【例6】编号为的五个人,分别坐在编号为的座位上,则至多两个号码一致的坐法有多少种?【解】“至多两个号码一致”的意思就是“至少三个号码不一致”,由公式：.【例】高二年级

8、共有6个班,配备有6名数学教师,每班1名,学校准备合适调节这名教师在该年级组内的任课班级,在如下状况下,各有多少种调节方案？(1）至少变动3名教师任课班级;（2）一定变动甲、乙、丙名教师的任课班级；(3)变动甲、乙、丙3名教师的任课班级，其他3名教师的任课班级不变；（4)甲、乙、丙名教师中至多变动人的任课班级。【解】(1)由题意，知求,由于,因此：， （2）属于禁位排列问题,种。 ()属于部分错位排列问题,可以当作是3个元素的全错为排列问题，有种。 (4）甲、乙、丙3名教师的任课班级都不变时，另名教师中至少有2个人的任课班级有变动，另名教师中至少有人的任课班级有变动,其调节方案有；甲、乙、丙3

9、名教师中至少有1人的任课班级有变动，其调节方案有种。 故甲、乙、丙3名教师中至多变动人的任课班级的调节方案共有.4.全错为排列的另一种证法当时,位置只有一种，而该元素不能排在该位置，因此,这种排法为种，即.当时,不能排在第一种位置，不能排在第二个位置的排法只有1种即排在第二个位置,排在第一种位置),即.当时,设不排在第位,分别填人下面的个方框中。in第一步：考虑第1个位置,由于不能排在第一种位置，因此第 1个位置的排法共有 种，下面假定排在第 1个位置。第二步：考虑第 i个位置，根据第 i个位置与否排可提成两种情形：(1）当排在第i个位置(此时已排在第1个位置）,则还剩余个元素及与之相应的个位

10、置,则问题变为个元素的错位排列问题，因此不同的排法有种。(2)当不排在第i个位置（此时仍排在第1个位置),由于和均不能排在第i个位置，因此,当排在第1个位置后，剩余的个人：和个位置:其中不排在第 k 位，不排在第i位。故此时也相称于个元素的错位排列,则不同的排法是种.由乘法和加法原理知:(*）,其中. 下面用递归迭代法得出的计算公式。由（*)得：因此 由于，因此,运用累加法,求得因此即在个不同元素的全排列中，错排列数为:,其中5全错为排列的推广上面我们讨论了个元素的全错位排列问题。如果我们换一种角度来看,把n个元素当作n组人,则为每一组只有1人的全错位排列。为此,我们自然会想到每组有人、人甚至

11、个人时的状况又会如何呢？为此我们将此模型进一步推广:【定理1】个人，每组k个人，共组，坐到n行k列共k个位置中，但若第组不能坐到第行中(组内成员可换位置）。不同的坐法有:,其中,且（为n个元素的错位排列数）。证明:当时,由于第一构成员不能坐在第一行中,因此. 当时，由于第1组人做到第2组位置构成全排列,第二组人坐到第组位置又构成全排列，因此种。 当时,一方面考虑第1行的位置，也许坐此位置的人共有组,但无论哪一组人坐，不同的坐法有种。下面假定第 1行被第i组坐了。接着,再考虑第i行,同样可分两种状况讨论:（1）若第i行被第1组人坐(此时第 行被第i组人坐)，还剩余组人和与之相应的组位置,则共有种

12、不同的坐法。(2）若第i行不被第组人坐(此时第1行仍被第i组人坐）.则剩余组人和组位置，则不同的坐法共有种。由乘法和加法原理知：, 事实上，此问题也可以这样考虑：第一步以组为单位,正好为n个元素的错排列，公有种排列措施;第二步,每一组个元素均进行全排列，共有种排列措施。由乘法原理知: 从上面这个通项公式，我们可以看出时正好是错位排列的通解。【定理】个人，每组k个人，共组，坐到n行列,共如个位置中，但若第组不能坐到第行中，组内成员可换位置,但每组内第j人不能坐到第j列。共有坐法为:【证明】此问题可以这样考虑:第一步以组为单位,正好为n个元素的错排列，共有种排列措施;第二步，每组内第j人不能坐到第列,即每一组k个元素均进行错排列,共有种排列措施。由乘法原理知：【定理3】编号为的个人（每组个人,共n组)，坐到编号为的个位置中(共行k列），但编号为的人不能坐到编号为的位置中,则不同的坐法为： 【分析】 此问题可以这样考虑，编号为的人不能坐到编号为的位置中事实上就相称于所有元素的错排列。证明略(参照原数学模型的证明）。 从上面这个通项公式中,我们可以看出：当或时正好为错位排列的通解。