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

【摘要】容斥原理是中学数学中的重要定理，在计数时先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计算时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复.而更列问题则是组合数学的难点之一.本文首先给出容斥原理的定义及性质与证明，然后引出更列问题，同时给出更列问题的一个有效解法，最后讨论容斥原理在更列问题中的一系列应用.

【关键词】容斥原理；更列问题；排列

一、容斥原理的概念

在计数时，必须注意无一重复，无一遗漏.为了使重叠部分不被重复计算，人们在计数时，必须注意研究出一种新的计算方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计算时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称之为容斥原理

二、容斥原理的性质

假定|A|表示集合A的元素个数，根据加法原则，若A∪B=,则|A∪B|=|A|+|B|.若A∩B=时，这时将|A∪B|多计算一次，可以直观有|A∪B|=|A|+|B|-|A∩B|.对于n个有限集合A1,A2,A3,…,An,同样有定理：

|A1∪A2∪…∪An|=∑n-1i=1|Ai|-∑n-1i=1∑j>i|An-1∩An|+…+(-1)n-2|A1∩An|∪(A2∩An)∪…∪(An-1∩An)|+∑ni=1∑j>1∑k>1|Ai∩Aj∩Ak|+…+(-1)n-1|A1∩A2∩…∩An|.

三、更列问题的概念

什么叫作更列问题？我们先来看一个题目，现有五件球衣分属五个运动员,现问五个运动员都不穿自己的球衣,而穿其他球员的球衣,这样的穿法有几种?这就是5个元素的更列问题.

就一般而言,有几个不同的元素,它们一一对应于几个位置,如果这n个元素都不排在自身对应的位置上,这种排列的方法称为几个元素的一个更列.现要计算这种更列的个数.大数学家欧拉曾用容斥原理求出了n个元素的更列个数为:

Mn=n!1-11!+22!-33!+…+(-1)nn! .

四、容斥原理与更列问题的关系

这是运用组合数学的方法解决问题的一个运用.下面我们就证明一下这个公式.现在,我们来考虑整数1,2,…,n的排列.如果1不出现在第1个位置,2不出现在第2个位置,…,n不出现在第n个位置，这时,这些整数的一个排列说成是它们的一个更列.也就是说,没有一个整数出现在它的自然位置上.用Mn记1,2,…,n这n个数的更列的个数.如何来求这个Mn,这既是一个排列问题,同时又是一个数列的通项问题.

我们不妨先考虑这个数列的前几项.整数更列的个数可由解递归关系而得到.考虑整数1,2,…,n的更列，对其进行合理分布,恰当分类.

由分步计数原理和分类计数原理,我们便得到了数列{Mn}的递推关系式:Mn=(n-1)(Mn-1+Mn-2).(*)

显然,M1=0,M2=1,M3=2.(*)式可进一步变形,Mn-nMn-1=-［Mn-1-(n-1)Mn-2］=…=(-1)n-3•(M3-3M2)=(-1)n-2=(-1)n.

Mn-nMn-1=(-1)n式两边同乘1n!，则有

Mnn!-Mn-1(n-1)!=(-1)nn!.（1）

由累加法，得Mn=n!1-11!+22!-33!+…+(-1)nn! .

五、容斥原理在更列问题中的应用

例1 4只小鸟飞入四个不同的笼子里,每只小鸟都有自己的一个笼子(不同的鸟,笼子也不同),每个笼子只能飞进一只鸟,若都不飞进自己的笼子,应有多少种不同的飞法？

解 为了准确地计算出有多少种不同的飞法,先求出4只小鸟随意飞有多少种不同的飞法,然后减去不符合条件的飞法.

记A1={甲飞入自己的笼子而另3只鸟随意飞的飞法}，A2={乙飞入自己的笼子而另3只鸟随意飞的飞法}，A3={丙飞入自己的笼子而另3只鸟随意飞的飞法}，A4={丁飞入自己的笼子而另3只鸟随意飞的飞法}.

根据上面提到的公式：

Mn=n!-C1n(n-1)!+C1n(n-2)!-…+(-1)nCnn(n-n)!

=n!1-11!+22!-33!+…+(-1)nn!.

若是5只小鸟按题意飞入鸟笼,则有Mn=5!12!-13!+14!-15!=44（种）不同的飞法.

例2 某市有8个县，每县派出一个巡视组到本市别的县去检查工作（每县去一组），问巡视组有多少种不同的分派方法？

解 设这8个县的编号为1，2，…,8，而ai为第i号县（i=1，2，…，8）派出的巡视组.I表示这8个巡视组分派到这8个县（每县一组）的所有可能的方法组成的集合，Ai表示I中ai分到i号县的分配方法组成的集合（i=1，2，…,8）.依题意，根据公式Mn=n!-C1n(n-1)!+C1n(n-2)!-…+(-1)n•Cnn(n-n)!=8!-C18(8-1)!+C17(7-2)!-…+(-1)8•C88(8-8)!=14833（种）分配方法，即为所求.

【参考文献】

［1］李超英.排列和数列的汇合点——有趣的更列问题.中学数学参考，2003（9）：35.

［2］周小华.由“小鸟飞错鸟笼”谈容斥原理的应用.绍兴文理学院院报,2001（2）.

［3］吴国柱，郝端绪.容斥原理在组合数学中的若干应用.冀东学刊，1994（6）：23.

［4］万大庆.关于容斥原理的一些注记［J］.四川大学学报（自然科学版）,1985,22(1):15-19.