文档介绍：容斥原理及其应用
摘要:容斥原理是组合计数的一个重要工具,本文对容斥原理的形式作了陈述,重点论述了容斥原理在竞赛数学中的应用。
关键字:容斥原理;母函数;权;组合
容斥原理,又称包含排斥原理,是组合数学中解决计数问题的一个重要工具之一。在计数时,为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。
对于数列,我们将形式幂级数
称为的普母函数,简称母函数;将形式幂级数
,我们把它看成是一般的幂级数。
容斥原理
简单形式
设为有限集,,则
证,我们证明在(1)式两边被计算的次数相同. 事实上,在(1)式左边被计算了1次。在(1)式右边的各个和式中被计算的次数分别为,
从而知在(1)式在右边计算的次数为
,
即在(1)式在右边被计算了一次,由于,在(1)式两边被计算的次数相同,故(1)式成立。
设为有限集,,则:
证,
。
其中,(1)式是加法法则的推广。又有集合论知:
因此,(1)式和(2)式反映的是同一个问题的两个方面。若已知其中一面,则另一面也就可以得到。
一般形式
设S是有限集,S中的任一个元s都被赋予了唯一的权w(s),,,是n个性质,对任意个正整数,以表示S中同时具有性质的元素的权和,令,又以表示S中所有元素的权和,以表示S中恰好具有,,中个性质的元素的权和,则。
证:设k为不大于n的非负整数,对任意的,以表示s的权
在中计算的次数,则。设且s恰具有,,中的个性质(此时记),因为从t个性质中选取k个性质的方法有种,故s的权在中计算的次数,从而有
所以
而
所以
设,对于不定方程
(1)
满足条件的整数解的个数记为,则的母函数为
(2)
证: 将式右边展开后比较左右两边的系数,设,且,则,即是不定方程满足条件的一个解;反之,设是不定方程满足条件的一个解,则,因此,式右边展开后的项数是不定方程满足条件的解的个数,所以合并后的系数。
设均为,集合的满足条件出现的次数属于的可充排列个数为,则的指母函数为
.
容斥原理的应用
错位排列问题
例1 设Z={1,2,···,n},Z的一个错位排列是指这样的全排列,使(j=1,2,...,n)。试求Z的所有错位排列的个数。
分析:由题设,Z的所有错位排列所构成的几何是Z的全排列集中去掉满足条件的全排列余下的全排列所构成的,可使用容斥原理。
解:用S表示Z的所有全排列所构成的集合,对于j=1,2,...,n规定在一个排列中,若j在第j个位置上,则该排列具有性质,令={x/xS,x具有性质},则Z的所有错位排列所构成的集合为.
中的排列具有下面的形式:1,其中是{2,3,···,n}的一个排列,所以=(n-1)!。同理,=(n-j)!(j=2,...,n)。
中排列具有下面的形式:12,于是=(n-2)!。同理,对于{1,2,
···,n}的任何一个2—组合{i,j},有=(n-2)!。
一般地,对任意整数k,,有=(n-k)!,其中是{1,2,···,n}的一个k—组合。
由容