容斥原理的应用

容斥原理的应用

邬 毅,于静静

【摘 要】摘 要:容斥原理是组合数学的一个基本的计数原理.通过给出容斥原理的两种等价形式,来探讨容斥原理在排列组合、数论、图论以及代数中有关解决有限集合计数问题方面的应用.

【期刊名称】西安文理学院学报（自然科学版） 【年(卷),期】2010(013)002 【总页数】3

【关键词】关键词:容斥原理;有限集合计数;组合数

首先给出容斥原理的两种等价形式,即下面的定理 1和定理 2.

定理 1[1] (容斥原理的简单形式):设 S是有限集合,P1,P2,…,Pm是同集合 S有关的 m个性质.设Ai表示 S中具有性质 Pi的元素构成的集合是 S中不具有性质 Pi的元素构成的集合(1≤i≤m),则有:

(Ⅰ)S中不具有性质 P1,P2,…,Pm的元素数是 (Ⅱ)在 S中至少具有一条性质的元素数是 (证明见文献[1])

定理 2[1] (容斥原理的一般形式)设集合 S中具有性质集合 P={P1,P2,…,Pm}中恰好 r个性质的元素个数为N(r),则 (证明见文献[1])

1 容斥原理在错排问题中的应用

利用容斥原理可以轻而易举得地得出在依次给以标号 1,2,…,n的 n个元素的全排列中,每个元素都不在自己原来位置上的排列数,其递推公式为:

(证明见文献[2])

例 1 数 1、2、3、…、9的全排列中,求偶数在原来位置上,其余都不在原来位置上的错排列数目.

解析 实际上是 1、3、5、7、9五个数的错排问题,由递推公式得其总数为 此外,容斥原理在有限制条件的排列问题和有禁区的排列问题中都有广泛的应用,举例详见有关文献.

2 容斥原理在多重集的 r组合数中的应用

例 2 确定多重集 S={2·a,2·b,4·c}的 4-组合数.

分析 设有多重集 S={n1·a1,n2·a2,…,nk·ak},要求它的 r-组合数,如果某个 ni>r,可用 r来代替 ni得到多重集 不难看出 S′的 r-组合数就是 S的 r-组合数,所以不妨假设所有的 ni≤r,i=1, 2,…,k.

解 令 S′={∞·a,∞·b,∞·c},则 S′的组合数为设集合A是S′的组合全体,则|A|=15,现在要求在 4-组合中 a的个数≤2,b的个数≤2,c的个数≤4-的组合数,定义性质集合 P={P1,P2,P3},其中 P1,P2,P3分别表示 4一组合数中 a的个数≥3,b的个数≥3,c的个数≥5的集合.将满足性质 Pi的 4-组合全体记为Ai(i=1,2,3).那么,A1中的元素可以看作是由 S′的 4 -3=1组合再拼上 3个 a构成的,所以有: 故同理 |A1∩A3|=0,|A2∩A3|=0,|A1∩A2∩A3|=0.而 a的个数≤2,b的个数≤2,c的个数≤4组合全体为由容斥原理,它的元素个数为

它们分别是 (0,0,5),(0,1,4),(0,2,3),(1,0,4),(1,1,3),(1,2,2),(2,0,3),(2,1,2),(2,2,1).

3 容斥原理在数论中的应用

问题 给定正整数 n∈N,确定欧拉函数φ(n),即求出小于 n且与 n互素的正整数个数.若 n=是将 n分解为 k个不同素因子的分解式,则再由容斥原理

类似地,对于任意的正整数 n,还可以应用容斥原理求出集合[1,n]中不能够被 ai整除的正整数的个数,其中 ai为一组两两互素的正整数.

例 3 求不超过 1 000的自然数中不能被 3整除也不能被 5整除的个数. 解不难发现所求个数为

4 容斥原理在图论中的应用

给定一个有限的无向图 G=(V,E),这里V是顶点集,E是边集,且完全子图定义为:它的顶点是 V的子集,在这些顶点中任两点都有 E中的边相连接.一个具有 k个顶点的完全子图称为一个完全 k-子图.下面假定 2≤k≤n,其中 n是 G的顶点数,顶点 v∈V的次数记为 d(v),定义为以 v作为一个端点的边数.显然,若一个图 G不包含完全 k-子图,则存在关于它的顶点的次数和它的边数的某些限制,其中有两个经典的结果:Zarankiewicz与 Turán.其中,Zarankiewicz的证明采用了反证法,巧妙的应用了容斥原理的对偶形式得到一个与题设矛盾的结论,而 Turán的证明采用了归纳法,应用容斥原理构造出一个在同构的意义下唯一的没有完全 k-子图的图.这两个结论的证明可以详见文献[4]. 此外,应用容斥原理可以求出图顶点染色的色多项式. 例 4 设有 4

个顶点的圈,顶点和边数依次记为

V={a,b,c,d},E={(a,b),(b,c),(c,d),(d,a)} ={e1,e2,e3,e4}.记性质 A1,A2,A3,A4分别为 a-b,b-c,c-d,d-a染色相同.现有 x种色,图 G的正常染色为每点染上一色且相邻接的顶点不同色,正常染色的方式数目记为 P(G,x)(称为色多项式),则 PA4).N(A1)表示 a-b染同色的 G的染色方式数,N(A1)=x3,显然 N(A2)=N(A3)=N(A4)==x3;N (A1∩A2)表示 a-b染同色且 b-c染同色的染色方式数,显然 N(A1∩A2)=N(A1∩A4)=N(A2∩A3)= N(A2∩A4)=x2,同理