错位排列和禁位排列.docx

:..--------------------------校验:_____________-----------------------日期:(1)某省决定对所辖8个城市的党政一把手进行任职交流,要求把每个干部都调到另一个城市去担任相应的职务,问共有多少种不同的干部调配方案?(2)有5个客人参加宴会,他们把衣帽寄放在室内,宴会后每人戴了一顶帽子回家,回家后,他们的妻子都发现,他们戴了别人的帽子,问5个客人都不戴自己帽子的戴法有多少种?上述两个问题,实质上是同一种类型的问题,被著名数学家欧拉(LeonardEuler,1707—1783)称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰•伯努利(JohnBernoulli,1667—1748)的儿子丹尼尔•伯努利(DanidBernoulli,1700—1782)提出来的,大意如下:一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封。问全部装错了信封的装法有几种?)错位排列:n个相异元素中个元素,其中不在第个位置(一下简称其为的本位),而其他个元素中的任何一个都在原来的位置(本位)的排列。如果n个元素都不在本位,称为全错位排列。2)禁位排列(一个元素禁止排在一个位置):n个相异元素中个元素,其中不能排在第个位置的排列。3)两者的区别在于:错位排列中除这m个元素之外的其他个元素都在本位,即这m个元素只能在m个位置中排列,且不出现在位的情况;而禁位排列中只限制m个元素不在本位,因此可以排在中除之外的任何位置。)禁位排列数:求禁位排列数,只需从n个元素的全排列中除去指定元素占本位的排列即可,其中有1个元素占本位的排列数是,有两个元素占本位的排列数是,……,,用表示n个元素全错位排列。则由容斥原理有:【禁位排列公式】【证明】①当时,等式左边为,表示n个元素没有限制,所以有,等式右边本应该有项,当时,只有1项,;②假设;③那么当时,设第个元素为a,则前k个元素不占本位而a占本位的排列数为:,因此对于时,公式1均成立。【例1】5个人站成一排,其中甲不站排头,乙不站排尾,共有多少种不同的站法。【解】由公式得:【例2】6个人站成一排,其中甲不站第一位,乙不站第二位,丙不站第三位,共有多少种不同的站法。【解】由公式得:【变式1】用这5个数字,组成没有重复数字的5位数,百位上不排3,一共有多少种排法?【变式2】在由组成的没有重复数字的五位数中,共有多少个小于60000的奇数?2)全错为排列数:全错为排列就是n个元素,全不排在本位,实际上就是禁位排列中,当的情况,因此:【全错位排列公式】.另一种写法:.【例3】寝室四个人每人写一张贺卡,然后互相交换,每个人不拿到自己的卡片,一共有多少种可能?【解】由公式得:;用另外一个公式得:.【例4】有来自五国的乒乓球裁判员各两名,执行某国际大赛的号场地的乒乓球裁判工作,每个场地由2个来自不同国家的裁判组成,不同的安排方案共有多