论文部分内容阅读
【摘要】分析错位排列和禁位排列的特征、区别和联系，给出相应的排列数计算公式.
【关键词】错位排列；禁位排列；全错位排列；容斥原理
错位排列和禁位排列是学生容易混淆，解题常感棘手的排列难题，有必要对这两个概念加以区分，并对其计算方法进行探讨.
错位排列:n个相异元素中m(≤n)个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不在第ik(k=1,2,…,m)个位置(以下简称其为aik的本位)，而其他n-m个元素中的任何一个都在原来的位置(本位)的排列.
禁位排列(本文只讨论一个元素禁止排在一个位置的情况):n个相异元素中的m个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不能排在第jk(k=1,2,…,m)个位置的排列.
两者的区别在于：错位排列中除这m个元素之外的其他n-m个元素都在本位，即这m个元素只能在m个位置i1,i2,…,im中排列，且不出现aik(k=1,2,…,m)在ik位的情况；而禁位排列中只限制m个元素不在本位，因此aik(k=1,2,…,m)可以排在1,2,…,n中除ik之外的任何位置.
求禁位排列数，只需从n个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是C1mPn-1n-1，有2个元素占本位的排列数是C2mPn-2n-2，…，n个元素都占本位的排列是CmmPn-mn-m.
记错位排列和禁位排列的排列数分别为Dmn，Emn，并规定P00=C00=0!=1，则由容斥原理(把多减的补回，多补的再减去)，有
公式一 Emn=n!C0m-(n-1)!C1m+(n-2)!C2m-…+(-1)m(n-m)!Cmm.
证明 易知当m=0时，等式成立.
假设Ekn=∑ki=0(-1)iCikPn-in-i.
那么，当m=k+1时，设第k+1个元素为a，则前k个元素不占本位而a占本位的排列数为
Ekn-1=∑ki=0(-1)iCikPn-i-1n-i-1.
因而前k+1个元素不占本位的全排列即为从前k个元素不占本位的全部排列中再除去a占本位的排列，即
Ek+1n=Ekn-Ekn-1
=∑ki=0(-1)iCikPn-in-i-∑ki=0(-1)iCikPn-i-1n-i-1
=C0kPnn+∑ki=1(-1)i(Cik+Ci-1k)Pn-in-i+
(-1)k+1CkkPn-k-1n-k-1
=∑k+1i=0(-1)iCik+1Pn-in-i.
由上可知公式一成立.证毕.
错位排列有两种情况：1.限定的m个元素不占本位；2.未限定的m个元素不占本位.
特别地，当n个元素都不在本位时，称为全错位排列.记其排列数为Dn，则有
公式二 Dn=n!C0n-(n-1)!C1n+(n-2)!C2n-…+(-1)n(n-1)!Cmn.或
公式二(*)
Dn=n!1-11!+12!-13!+…+(-1)n-11n!.
由公式二，n个相异元素中m个指定元素的错位排列数为：
公式三 Dm=m!C0m-(m-1)!C1m+(m-2)!C2m-…+(-1)mCmm.
n个相异元素中有m个元素的错位排列数为：
公式四 Dmn=CmnDm.
易知，当n=m时，公式一、公式三、公式四都可表示为公式二.
例1 要安排6名学生分别担任6个班干部工作，其中甲不能当班长，乙不能当体育委员，丙不能当生活委员，共有多少种安排方法？(E36)
例2 甲、乙、丙、丁四人排成一排，甲不能站一位，乙不能站二位，丙不能站三位，丁不能站四位，共有多少种排法？(D4)
例3 一个人写了8封不同的信及相应的8个不同的信封，问：将这8封信装进信封时(每个信封中只能装一封信)，有3封信装错的装法有多少种？(D38)
【参考文献】
卢开澄，卢华明.组合数学(第三版)［M］.北京：清华大学出版社，2002.
【关键词】错位排列；禁位排列；全错位排列；容斥原理
错位排列和禁位排列是学生容易混淆，解题常感棘手的排列难题，有必要对这两个概念加以区分，并对其计算方法进行探讨.
错位排列:n个相异元素中m(≤n)个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不在第ik(k=1,2,…,m)个位置(以下简称其为aik的本位)，而其他n-m个元素中的任何一个都在原来的位置(本位)的排列.
禁位排列(本文只讨论一个元素禁止排在一个位置的情况):n个相异元素中的m个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不能排在第jk(k=1,2,…,m)个位置的排列.
两者的区别在于：错位排列中除这m个元素之外的其他n-m个元素都在本位，即这m个元素只能在m个位置i1,i2,…,im中排列，且不出现aik(k=1,2,…,m)在ik位的情况；而禁位排列中只限制m个元素不在本位，因此aik(k=1,2,…,m)可以排在1,2,…,n中除ik之外的任何位置.
求禁位排列数，只需从n个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是C1mPn-1n-1，有2个元素占本位的排列数是C2mPn-2n-2，…，n个元素都占本位的排列是CmmPn-mn-m.
记错位排列和禁位排列的排列数分别为Dmn，Emn，并规定P00=C00=0!=1，则由容斥原理(把多减的补回，多补的再减去)，有
公式一 Emn=n!C0m-(n-1)!C1m+(n-2)!C2m-…+(-1)m(n-m)!Cmm.
证明 易知当m=0时，等式成立.
假设Ekn=∑ki=0(-1)iCikPn-in-i.
那么，当m=k+1时，设第k+1个元素为a，则前k个元素不占本位而a占本位的排列数为
Ekn-1=∑ki=0(-1)iCikPn-i-1n-i-1.
因而前k+1个元素不占本位的全排列即为从前k个元素不占本位的全部排列中再除去a占本位的排列，即
Ek+1n=Ekn-Ekn-1
=∑ki=0(-1)iCikPn-in-i-∑ki=0(-1)iCikPn-i-1n-i-1
=C0kPnn+∑ki=1(-1)i(Cik+Ci-1k)Pn-in-i+
(-1)k+1CkkPn-k-1n-k-1
=∑k+1i=0(-1)iCik+1Pn-in-i.
由上可知公式一成立.证毕.
错位排列有两种情况：1.限定的m个元素不占本位；2.未限定的m个元素不占本位.
特别地，当n个元素都不在本位时，称为全错位排列.记其排列数为Dn，则有
公式二 Dn=n!C0n-(n-1)!C1n+(n-2)!C2n-…+(-1)n(n-1)!Cmn.或
公式二(*)
Dn=n!1-11!+12!-13!+…+(-1)n-11n!.
由公式二，n个相异元素中m个指定元素的错位排列数为：
公式三 Dm=m!C0m-(m-1)!C1m+(m-2)!C2m-…+(-1)mCmm.
n个相异元素中有m个元素的错位排列数为：
公式四 Dmn=CmnDm.
易知，当n=m时，公式一、公式三、公式四都可表示为公式二.
例1 要安排6名学生分别担任6个班干部工作，其中甲不能当班长，乙不能当体育委员，丙不能当生活委员，共有多少种安排方法？(E36)
例2 甲、乙、丙、丁四人排成一排，甲不能站一位，乙不能站二位，丙不能站三位，丁不能站四位，共有多少种排法？(D4)
例3 一个人写了8封不同的信及相应的8个不同的信封，问：将这8封信装进信封时(每个信封中只能装一封信)，有3封信装错的装法有多少种？(D38)
【参考文献】
卢开澄，卢华明.组合数学(第三版)［M］.北京：清华大学出版社，2002.