摘 要： 容斥原理是组合数学中的一个重要定理和方法。将这一重要原理应用到排列问题中，会给解决错位排列、有禁区排列和圆形排列等问题带来极大的便利。
关键词： 容斥原理 错位排列 有禁区排列 圆形排列
容斥原理，又称包含——排斥原理或取舍原理，它是组合数学中解决计数问题的一个重要原理和工具，若将这一原理应用到排列问题中，则对解决错位排列、有禁区排列和圆形排列等问题都会起到很大作用.
1.容斥原理简述
（1）簡单形式：设有限集合和与中元素有关的性质集合P={p，p，…，p}，令A={x|x∈S，且x具有性质p}，=S-A（i=1，2，…，n），则|∩∩…∩|=|S|-|A|+|A∩A|-|A∩A∩A|+…+（-1）|A∩A∩…∩A|.
（2）一般形式：设S，P同上，F为一域，对每一a∈S，有唯一w（a）∈F与a对应，称w（a）为a的权，W（p，p，…，p）为S中同时具有r这个性质p，p，…，p的所有元素的权和，W（r）=∑W（p，p，…，p），其中和式取遍P的r元子集，当r=0时，规定W（0）等于S中所有元素的权的和，令E（k）表示中恰好具有P中k个性质的元素的权和，E（0）表示S中不具有P中任何性质的元素的权和，则有：
E（k）=（-1）mkW（m）?摇?摇?摇?摇E（0）=（-1）W（m）
若对一切a∈S，都有w（a）=1，并以N（m）记W（m），则有
E（k）=（-1）mkN（m）?摇?摇?摇?摇E（0）=（-1）N（m）
2.容斥原理在错排问题中的应用
错位排列，又称为更列，是一种带限制条件的全排列。若Z={1，2，…，n}，则Z的一个错位排列是指这样的全排列aa…a，使a≠i（i=1，2，…，n）.利用容斥原理可以推导的所有错位排列的个数Dn.
定义性质P：对排列aa…a，有a=i（i=1，2，…，n），设A为具有性质P的全体排列，则Z的所有错位排列所构成的集合为∩∩…∩.
因数字i不动，故
|Ai|=（n-1）！，i=1，2，…，n.
同理
|A∩A|=（n-2）！，i，j=1，2，…，n，i≠j.
……
由容斥原理得：
D=|∩∩…∩|
=n！-n1（n-1）！+n2（n-2）！-…+（-1）nn0！
=n！［1-+-…+（-1）］
例1：数1，2，3，…，9的全排列中，求偶数在原来的位置上，其余都不在原来的位置上的错排数目.
解：此问题实际上是1，3，5，7，9五个数的错排问题，总数是
5！［1-+-+-］=120×（-+-）=44.
3.容斥原理在有禁区排列中的应用
n个元素的某一排列可以看做是n个棋子在n×n的棋盘上的一种布局。当一个棋子置于棋盘的某一格子时，则这一格子所在的行和列都不能再布任何棋子，即棋盘的每一个布局每行每列有且只有一个棋子.有禁区排列是指每个棋子在棋盘上都有一定的禁区的布局.
利用容斥原理可以导出有禁区的排列数为
n！-r（n-1）！+r（n-2）！-…±r，
其中r是有i个棋子布置到禁区部分的方案数.
令PP…P为n个棋子布入n×n棋盘所得到的排列，其中P为第i个棋子落在棋盘的第i行的位置.A为第i个棋子放入禁区，即P在禁区内事件.
一个棋子落入禁区方案数为r，剩下的n-1个棋子为无限制条件的排列，故至少有一个棋子进入禁区的方案数为r（n-1）！.两个棋子落入禁区方案数为r，而其余n-2个棋子为无限制条件的排列，故至少有两个棋子进入禁区的方案数为r（n-2）！，依此类推.
依据容斥原理，布个棋子无一落入禁区的方案数应为：
|∩∩…∩|=n！-r（n-1）！+r（n-2）！-…±r.
例2：有甲，乙，丙，丁四个人，A，B，C，D为四项任务，甲不能从事任务B；乙不能从事B，C两项任务；丙不能从事C，D任务；丁不能从事任务D.若要求每人从事各自力所能及的一项任务，试问有多少种不同方案？
分析：每一种分配方案相当于图1的关于A，B，C，D的有禁区排列（阴影表示禁区）.问题也相当于求在如图1所示的有禁区的棋盘上，用四个棋子进行布局的方案数，因此需用到棋盘多项式.
解：图1的禁区的棋盘多项式为1+6x+10x+4x，
即r=6，r=10，r=4
所求方案数为：
4！-6×3！+10×2！-4=4.
4.容斥原理在圆形排列中的应用
问题：将1，1′，2，2′，…，n，n′排成一个圆圈，当i，i′（i=1，2，…，n）相邻时，则将i，i′看作一个整体而不考虑它们之间的顺序，求这种圆形排列的个数R.
应用容斥原理的一般形式，我们可以得到R的公式.
设S为1，1′，2，2′，…，n，n′的所有圆形排列的集合，P表示性质“排列中i，i′相邻”（i=1，2，…，n），则：
R=E（0）+E（1）+E（2）+…+E（n）=E（k）.
易知，N（m）=nm2（2n-m-1）！（m=0，1，…，n），由容斥原理知
E（k）=（-1）mkN（m），
故
R=E（k）=（-1）mkN（m）
=（-1）mkN（m）=（-1）mkN（m）
=（-1）mkN（m）=（-1）mkN（m）
=（-1）［（-1）mkN（m）］=（-1）N（m）
=（-1）nm（2n-m-1）！
例3：当n=2时，R=20•3！-21•2！+22•1！=3.
以上仅是容斥原理被应用到排列中的几个方面，而它在排列问题中的应用远不止这些，在其他类型的排列求解中也经常被使用.
参考文献：
［1］陈敬华.容斥原理及其应用［J］.高等函授学报（自然科学版），2000，13，（2）：17.
［2］柯召，魏万迪.组合论［M］.北京：科学出版社，1981.
［3］卢开澄.组合数学［M］.北京：清华大学出版社，1991.
［4］卢青林，刘光乾.一类排列问题的计数［J］.徐州师范大学学报（自然科学版），1998，16，（2）：17.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
