容斥原理在排列问题中的应用实例

开篇：润墨网以专业的文秘视角，为您筛选了一篇容斥原理在排列问题中的应用实例范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 容斥原理是组合数学中的一个重要定理和方法。将这一重要原理应用到排列问题中，会给解决错位排列、有排列和圆形排列等问题带来极大的便利。

关键词： 容斥原理 错位排列 有排列 圆形排列

容斥原理，又称包含――排斥原理或取舍原理，它是组合数学中解决计数问题的一个重要原理和工具，若将这一原理应用到排列问题中，则对解决错位排列、有排列和圆形排列等问题都会起到很大作用.

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格式阅读原文

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文