容斥原理及其应用

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

文章编号:1006-7353(2000)02-0017-04

容斥原理及其应用

陈敬华

(湖北师范学院数学系)

　　摘要:容斥原理是组合计数的一个重要工具。本文对容斥原理的表现形式作了陈述,重点论述了容斥原理在数学各个分支中的应用。

关键词:容斥原理;权;可重组合;积和式中图分类号:O157　　　　文献标识码:A

1　引言

元素的权和,W(r)=

容斥原理,又称包含排斥原理,是组合数学中解决计数问题的一个重要工具之一。对初学者而言,无论是在对容斥原理的理解困难,:

:S和与S中的元P={p1,p2,…,pm},令Ai

={x|x∈S,且x具有性质pi},Ai=S-Ai(i=1,2,…,m),则

1,p2,…,

pirr=0

时,。

(p中k个性质的,E(0)表示S中不具有p中任何性质的元素的权的和,则有

k+E(k)=W(k)-

W(k+1)+

k+k

m-W(k+2)-…+(-1)

W(m)

③

|A1∪A2∪…∪Am|=

i=1

∑|

E(0)=W(0)-W(1)+W(2)-…+

Ai|-

1≤i

∑

|Ai∩Aj|+

1≤i

∑

|Ai∩Aj∩Ak

m+1

|-…+(-1)|A1∩A2∩…∩Am|

④

容斥原理的证明详见有关文献,对于容斥原理可作如下说明:

(-1)

W(m)

(1)①式②式比较直观,其中①式是加

①

Ai|+

|A1∩A2∩…∩Am|=|S|-

i=1

∑|

法法则的推广。又由集合论知:|S|=|A1∪

A2∪…∪Am|+|A1∪A2∪…∪Am|=|A1∪A2∪…∪Am|+|A1∩A2∩…∩Am|,因此①式和②式反映的是同一个问题

1≤i

∑

|Ai∩Aj|-

1≤i

∑

|Ai∩Aj∩Ak|+

…+(-1)m|A1∩A2∩…∩Am|

②

一般形式:设S,P同上,F为一域,对每

个a∈S,有唯一ω(a)∈F与a对应,称ω(a)为a的权,W(pi1,pi2,…,pir)为S中同时具有这r个性质pi1,pi2,…,pir的所有

收稿日期:2000-02-16

的两个方面。若已知其中一面,则另一面也就得到。

(2)④式是③式当k=0时的特殊情形,若对S的任何元素a,w(a)=1,则④式

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

就是②式,初学者对①～④式之间的关系往往理解不够,它们之间的关系见下图:k=0

w(a)=1

一般地,对任意整数k,1≤k≤n,有

|Ai1∩Ai2∩…∩Aik|=(n-k)!,其中{i1,i2,…,ik}是{1,2,…,n}的一个k—组

①式

ir)

求

和是对P的所有r-子集来求,即表示S中至少具有P中r个性质的元素的权的和。

(4)若所求解问题能表示为求|A1∩

(3)W(r)=

A2∩…∩Am|(即求某集合S中不满足某

∑W(p1,p2,…,p

合。

由容斥原理得:

Dn=n!-(-1)n

n(n-1)!+

(n-2)!-…+

些条件的元素的个数或能表示为求其集合中不满足某些条件的元素的权的和)时,通常可考虑使用容斥原理。

对于什么样的问题可使用容斥原理,以及如何使用容斥原理,下面我们从几个方面用例子来说明。

2　容斥原理在排列组合问题中的应用2.1错位排列问题

n+-…+(-1).1!2!n=n1-

2.2多重集的r—可重组合数N

设有多重集W={n1・a1,n2・a2,…,nk・

ak},n1+n2…+nk=n.,r≤ni(i,r

,则须另寻解法。=1,,n,N-例1　设Z={1,2,…,in,ijj(j=,,n个数　由题设,Z的所有错位排列所构成的集合是Z的全排列集中去掉满足条件ij=j的全排列余下的全排列所构成的,可使用容斥原理。

解　用S表示Z的所有全排列所构成的集合,对于j=1,2,…,n规定在一个排列中,若j在第j个位置上,则该排列具有性质pj,令Aj={x|x∈S,x具有性质pj},则

Z的所有错位排列所构成的集合为A1∩A2

W={3・a,4・b,5・c}的10—可重组合数。

分析　表面看来,同例1相比,似乎此问题与使用容斥原理联系不大,但仔细分析,会觉得有使用容斥原理的可能性。碰到此类问题大家容易得到的是多重集T={∞・a,∞・b,∞・c}的10—可重组合数N=3+10-1

12　10

==66,但T的10—可

重且合数并非所求。因为W的10—可重组合均是T的10—可重组合,而T的10—可重组合却不一定是W的10—可重组合。如

T的某10—可重组中含4个a,就不是W的

∩…∩An。

A1中的排列具有下面的形式:1i2…in,其中i2…in是{2,3,…,n}的一个排列,所以|A1|=(n-1)!.同理,|Aj|=(n-1)!(j=2,…,n)。

A1∩A2中排列具有下面的形式:12i3…in,于是|A1∩A2|=(n-2)!,同

10—可重组合。基于此,可设S={x|x是T

的10—可重组合}我们所求的就是S中不满足条件“a的个数多于3个,b的个数多于4个,c的个数多于5个”的10—可重组合的个数,因此可考虑使用容斥原理。

解　设S={x|x是T的10—可重组合},对任一x∈S,如果a多于3个,则称它具有性质p1,如果其中b多于4个,则称它具有性质p2,如果c多于5个,则称它具有性质

理,对于{1,2,…,n}的任何一个2—组合

{i,j},有|Ai∩Aj|=(n-2)!。18

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

p3,令Ai={x|x∈s,x具有性质pi},i=

1,2,3.

所以|Ai|=

a(i=1,2,…,r).aiaj,2aiaj,aa,aiaij

先计算|Ai|,i=1,2,3.

A1中的每个10—可重组合至少含有4个a,去掉这4个a,得T的一个6—可重组合;反之,对T的任一个6—可重组合加4个a就得到A1的一个10—可重组合,所以

3+6-1

|A1|==28.

65+5-1

同理:|A2|==21.

53+4-1

|A3|==15.

用类似的方法可得:

3+1-1

|A1∩A2|==3,|A1∩A3|=

3+0-1

=1.

|A2∩A3|=,A3=0.|珚A12A3|=66-(28+21+15)+(3+1+0)-0=6.

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

例3　设a1,a2,…,ar是一组两两互素的正整数,n是任意给定的正整数,则集合[1,n]中不能被任何一个ai(i=1,2,…,r)整除的正整数的个数N=n-1≤i≤r

又因为Ai∩Aj=故|Ai∩Aj|=同理可得:

(1≤i

由容斥原理得:

N=n-(-1)

1≤i≤r

1≤i

∑

-…+aiaa1a2…a证毕.

4,下例将使用一般形式求矩阵的积和式。

设矩阵A=(aij)

m×n

(m≤n),称

∑a1

a2i2…amim为A的积和式.记为

Per(A)=

∑a1

a2i2…amim,其中求和是对

{1,2,…,n}的所有m—排列i1i2…im。

例4　设A是m×n矩阵,m≤n,把A的某r列改写为零后所得的m×n矩阵记为

Ar,并记这个Ar的m个行的行和的乘积为S(Ar),再令

∑S(A

r)为所有可能取得的

1≤i

∑

-…+(-1)aiar

a1a2…a。

A(r)的S(Ar)之和,则Per(A)=

分析　此问题的结论:“集合[1,n]中不能被ai(i=1,2,…,r)整除的正整数个数”可转化为“集合[1,n]中不满足条件‘能被ai(i=1,2,…,r)整除’的正整数个数。”故可使用容斥原理求解。

证明　设S=[1,n],pi为S中的元能被ai整除的性质,Ai={x|x∈S,x具有性质pi}(i=,2,…,n)因为

Ai=

ai,2ai,…,a,

aii

∑

S(An-m)-

n-m+1

∑S(A

n-m+1)

n-m+2

∑S(A

n-1m-n-m+2)

-…+(-1)n

∑S(A

n-1).

分析,不是求某集合的元素的个数。分析积和式定义:

Per(A)=

∑a1

a2j2…amjm求和是对

{1,2,…,n}的所有m-排列来求。

由此得到启示:设S={x|x是[1,n]的

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

m-可重排列},对S中的任一元素a=j1j2…jm,可定义权w(a)=a1j1a2j2…amjm,

于是A1∩A2∩…∩Am是[1,n]含有{1,2,…,m}的所有r元子集的集合,于是

|A1∩A∩…∩A|=

n-mr-m

n-m-rn-1

(1≤j≤m)

于是Per(A)等于S中正好不包含集[1,n]中n-m个整数的元素的权的和。因此有使用容斥原理一般形式的可能性。

证　设S={x|x是集[1,n]的m-可重排列}对x=j1j2…jm,令x的权w(x)=a1j1a2j2…amjm,S的元素j1j2…jm不包含整数i(i=1,2,…,n)的性质为pi。如果Ar是把A中第i1,i2,…,ir列改成零后所得的矩阵,则W(pi1,pi2,…,pir)=S(Ar),从而

W(r)=

另一方面,有|Aj|=

|Ai∩Aj|=

n-2

(1≤i

……

|A1∩A2∩…∩Am|=

n-mr

∑

S(Ar)

由容斥原理得:

n-mr

=A1∩AS=1

Per(A)的值等于S中正好具有n

-m个性

质pi(i=1,2,…,n)的元素的权的和。由容斥原理③式得

n-m+Per(A)=W(n-m)-W(nm+1n-m

n-mn-1=

∑|A|+

1≤i≤|ij|-+(-1)m|A1∩A2

∩…∩Am|

n-m

n-r

-m-+

W(n-1)+(-1)n-m+m

-…+

n1m-n-m)

nW(n)+

(-1)m

n-r(-1)i

n-ir

∑S(A

(-1)m-1

∑S(A

n-m+1)

i=0

∑

n-m+∑

S(An-m+2)-…+

n-1).

证毕.

以上我们通过容斥原理在若干方面的应用力求对读者在对容斥原理的理解,以及如何运用容斥原理方面有一定帮助。我们注意到,任何一个问题若涉及某集合(有限集)中不满足某些条件的元素的计数或“权”的和,都有可能使用容斥原理,不过不同的问题在细节上需使用不同的技巧与方法,关键是原理中S,Pi,S中元的“权”的设置。

参考文献

1　毛经中.组合数学基础.武汉:华中师范大学出版

n-1m-∑S(A

证毕.

5　在其它方面的应用

容斥原理的应用相当广泛,除了上述应

用外,还可应用于图论,组合恒等式的证明等方面,下面仅举1例。

例5　证明:

n-mn-r

i=0

∑

(-1)

n-ir

社,1990.

2　杨天民.组合数学教程.北京:机械工业出版社,

1993.

3　H.J.赖瑟著、李乔译.组合数学.北京:科学出版

证明　令S={X|X是[1,n]的r元

子集},pj={X|X∈S,且j

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

文章编号:1006-7353(2000)02-0017-04

容斥原理及其应用

陈敬华

(湖北师范学院数学系)

　　摘要:容斥原理是组合计数的一个重要工具。本文对容斥原理的表现形式作了陈述,重点论述了容斥原理在数学各个分支中的应用。

关键词:容斥原理;权;可重组合;积和式中图分类号:O157　　　　文献标识码:A

1　引言

元素的权和,W(r)=

容斥原理,又称包含排斥原理,是组合数学中解决计数问题的一个重要工具之一。对初学者而言,无论是在对容斥原理的理解困难,:

:S和与S中的元P={p1,p2,…,pm},令Ai

={x|x∈S,且x具有性质pi},Ai=S-Ai(i=1,2,…,m),则

1,p2,…,

pirr=0

时,。

(p中k个性质的,E(0)表示S中不具有p中任何性质的元素的权的和,则有

k+E(k)=W(k)-

W(k+1)+

k+k

m-W(k+2)-…+(-1)

W(m)

③

|A1∪A2∪…∪Am|=

i=1

∑|

E(0)=W(0)-W(1)+W(2)-…+

Ai|-

1≤i

∑

|Ai∩Aj|+

1≤i

∑

|Ai∩Aj∩Ak

m+1

|-…+(-1)|A1∩A2∩…∩Am|

④

容斥原理的证明详见有关文献,对于容斥原理可作如下说明:

(-1)

W(m)

(1)①式②式比较直观,其中①式是加

①

Ai|+

|A1∩A2∩…∩Am|=|S|-

i=1

∑|

法法则的推广。又由集合论知:|S|=|A1∪

A2∪…∪Am|+|A1∪A2∪…∪Am|=|A1∪A2∪…∪Am|+|A1∩A2∩…∩Am|,因此①式和②式反映的是同一个问题

1≤i

∑

|Ai∩Aj|-

1≤i

∑

|Ai∩Aj∩Ak|+

…+(-1)m|A1∩A2∩…∩Am|

②

一般形式:设S,P同上,F为一域,对每

个a∈S,有唯一ω(a)∈F与a对应,称ω(a)为a的权,W(pi1,pi2,…,pir)为S中同时具有这r个性质pi1,pi2,…,pir的所有

收稿日期:2000-02-16

的两个方面。若已知其中一面,则另一面也就得到。

(2)④式是③式当k=0时的特殊情形,若对S的任何元素a,w(a)=1,则④式

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

就是②式,初学者对①～④式之间的关系往往理解不够,它们之间的关系见下图:k=0

w(a)=1

一般地,对任意整数k,1≤k≤n,有

|Ai1∩Ai2∩…∩Aik|=(n-k)!,其中{i1,i2,…,ik}是{1,2,…,n}的一个k—组

①式

ir)

求

和是对P的所有r-子集来求,即表示S中至少具有P中r个性质的元素的权的和。

(4)若所求解问题能表示为求|A1∩

(3)W(r)=

A2∩…∩Am|(即求某集合S中不满足某

∑W(p1,p2,…,p

合。

由容斥原理得:

Dn=n!-(-1)n

n(n-1)!+

(n-2)!-…+

些条件的元素的个数或能表示为求其集合中不满足某些条件的元素的权的和)时,通常可考虑使用容斥原理。

对于什么样的问题可使用容斥原理,以及如何使用容斥原理,下面我们从几个方面用例子来说明。

2　容斥原理在排列组合问题中的应用2.1错位排列问题

n+-…+(-1).1!2!n=n1-

2.2多重集的r—可重组合数N

设有多重集W={n1・a1,n2・a2,…,nk・

ak},n1+n2…+nk=n.,r≤ni(i,r

解　用S表示Z的所有全排列所构成的集合,对于j=1,2,…,n规定在一个排列中,若j在第j个位置上,则该排列具有性质pj,令Aj={x|x∈S,x具有性质pj},则

Z的所有错位排列所构成的集合为A1∩A2

W={3・a,4・b,5・c}的10—可重组合数。

12　10

==66,但T的10—可

重且合数并非所求。因为W的10—可重组合均是T的10—可重组合,而T的10—可重组合却不一定是W的10—可重组合。如

T的某10—可重组中含4个a,就不是W的

∩…∩An。

A1中的排列具有下面的形式:1i2…in,其中i2…in是{2,3,…,n}的一个排列,所以|A1|=(n-1)!.同理,|Aj|=(n-1)!(j=2,…,n)。

A1∩A2中排列具有下面的形式:12i3…in,于是|A1∩A2|=(n-2)!,同

10—可重组合。基于此,可设S={x|x是T

的10—可重组合}我们所求的就是S中不满足条件“a的个数多于3个,b的个数多于4个,c的个数多于5个”的10—可重组合的个数,因此可考虑使用容斥原理。

解　设S={x|x是T的10—可重组合},对任一x∈S,如果a多于3个,则称它具有性质p1,如果其中b多于4个,则称它具有性质p2,如果c多于5个,则称它具有性质

理,对于{1,2,…,n}的任何一个2—组合

{i,j},有|Ai∩Aj|=(n-2)!。18

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

p3,令Ai={x|x∈s,x具有性质pi},i=

1,2,3.

所以|Ai|=

a(i=1,2,…,r).aiaj,2aiaj,aa,aiaij

先计算|Ai|,i=1,2,3.

A1中的每个10—可重组合至少含有4个a,去掉这4个a,得T的一个6—可重组合;反之,对T的任一个6—可重组合加4个a就得到A1的一个10—可重组合,所以

3+6-1

|A1|==28.

65+5-1

同理:|A2|==21.

53+4-1

|A3|==15.

用类似的方法可得:

3+1-1

|A1∩A2|==3,|A1∩A3|=

3+0-1

=1.

|A2∩A3|=,A3=0.|珚A12A3|=66-(28+21+15)+(3+1+0)-0=6.

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

例3　设a1,a2,…,ar是一组两两互素的正整数,n是任意给定的正整数,则集合[1,n]中不能被任何一个ai(i=1,2,…,r)整除的正整数的个数N=n-1≤i≤r

又因为Ai∩Aj=故|Ai∩Aj|=同理可得:

(1≤i

由容斥原理得:

N=n-(-1)

1≤i≤r

1≤i

∑

-…+aiaa1a2…a证毕.

4,下例将使用一般形式求矩阵的积和式。

设矩阵A=(aij)

m×n

(m≤n),称

∑a1

a2i2…amim为A的积和式.记为

Per(A)=

∑a1

a2i2…amim,其中求和是对

{1,2,…,n}的所有m—排列i1i2…im。

例4　设A是m×n矩阵,m≤n,把A的某r列改写为零后所得的m×n矩阵记为

Ar,并记这个Ar的m个行的行和的乘积为S(Ar),再令

∑S(A

r)为所有可能取得的

1≤i

∑

-…+(-1)aiar

a1a2…a。

A(r)的S(Ar)之和,则Per(A)=

证明　设S=[1,n],pi为S中的元能被ai整除的性质,Ai={x|x∈S,x具有性质pi}(i=,2,…,n)因为

Ai=

ai,2ai,…,a,

aii

∑

S(An-m)-

n-m+1

∑S(A

n-m+1)

n-m+2

∑S(A

n-1m-n-m+2)

-…+(-1)n

∑S(A

n-1).

分析,不是求某集合的元素的个数。分析积和式定义:

Per(A)=

∑a1

a2j2…amjm求和是对

{1,2,…,n}的所有m-排列来求。

由此得到启示:设S={x|x是[1,n]的

第13卷第2期2000年4月高等函授学报(自然科学版)

JournalofHigherCorrespondenceEducation(NaturalSciences)Vol.13No.2February2000

m-可重排列},对S中的任一元素a=j1j2…jm,可定义权w(a)=a1j1a2j2…amjm,

于是A1∩A2∩…∩Am是[1,n]含有{1,2,…,m}的所有r元子集的集合,于是

|A1∩A∩…∩A|=

n-mr-m

n-m-rn-1

(1≤j≤m)

于是Per(A)等于S中正好不包含集[1,n]中n-m个整数的元素的权的和。因此有使用容斥原理一般形式的可能性。

W(r)=

另一方面,有|Aj|=

|Ai∩Aj|=

n-2

(1≤i

……

|A1∩A2∩…∩Am|=

n-mr

∑

S(Ar)

由容斥原理得:

n-mr

=A1∩AS=1

Per(A)的值等于S中正好具有n

-m个性

质pi(i=1,2,…,n)的元素的权的和。由容斥原理③式得

n-m+Per(A)=W(n-m)-W(nm+1n-m

n-mn-1=

∑|A|+

1≤i≤|ij|-+(-1)m|A1∩A2

∩…∩Am|

n-m

n-r

-m-+

W(n-1)+(-1)n-m+m

-…+

n1m-n-m)

nW(n)+

(-1)m

n-r(-1)i

n-ir

∑S(A

(-1)m-1

∑S(A

n-m+1)

i=0

∑

n-m+∑

S(An-m+2)-…+

n-1).

证毕.

参考文献

1　毛经中.组合数学基础.武汉:华中师范大学出版

n-1m-∑S(A

证毕.

5　在其它方面的应用

容斥原理的应用相当广泛,除了上述应

用外,还可应用于图论,组合恒等式的证明等方面,下面仅举1例。

例5　证明:

n-mn-r

i=0

∑

(-1)

n-ir

社,1990.

2　杨天民.组合数学教程.北京:机械工业出版社,

1993.

3　H.J.赖瑟著、李乔译.组合数学.北京:科学出版

证明　令S={X|X是[1,n]的r元

子集},pj={X|X∈S,且j

容斥原理及其应用

相关文章