容斥原理及其应用

夏婧

摘   要：容斥原理是奧数的四大原理之一，是考生们绕不过去的知识点。孩子学习奥数，家长一定要让孩子掌握容斥原理解题方法。

关键词：计数问题;容斥原理;奥数

计数问题是数学竞赛中常见的一类问题，很自然地，若用集合的观点去看计数问题，则计数问题就是要求某一特定集合的元素个数，从而可以利用集合的包含与排除关系，利用集合的交、并、补运算使计数问题转化，使问题得到解决。这种问题解决的策略就是容斥原理。

若对于有限集合A，当A1，A2，……，An是其一个分划，即：

A1∪A2∪……∪An=A

Ai∩Aj=Φ，（i，j = 1，2，3，……，n且i≠j）

此时，有|A|=|A1|+|A2|+……+|An|。这就是组合计数中的加法原理，基本思想是把不易计数的有限集A分成若干彼此不相交的容易计数的子集A1，A2，……，An，分别计算各子集元素的个数，从而得到集合A的元素个数。

给出的有限集A一般容易找到这样的若干子集A1，A2，……，An，使得A=A1∪A2∪……∪An，但往往难以满足条件Ai∩Aj=Φ，（i，j = 1，2，3，……，n且i≠j），若按加法原理会将A中的元素重复计算。这种情况下，希望能“多退少补”地对加法原理计算得到的结果进行修正，即重复计数（多的）部分减去，若减得太多了再补上，直至结果刚好为|A|。这就是容斥原理的基本思想[1]。

为了帮助理解，先来看简单的情况。如图1所示，若集合A，B，S满足A∪S，B∪S，且A∪B=S，A∩B≠Φ，则易知|S|=|A∪B|=|A|+|B|-|A∩B|。

上述情况推广到3个集合时，如图2所示，相应地有结论：

|S|=|A∪B∪C|=|A|+|B|+|C|-（|A∩B|+|A∩C|+|B∩C|）+|A∩B∩C|

若推广到n个集合时，有：

定理1（容斥原理）设A1，A2，……，An是有限集S的子集，S=A1∪A2∪……∪An，则：

|S|=|A1∪A2∪……∪An|=-++……+（-1）n-1|A1∩A2∩……∩An| （1）

证明对n用数学归纳法。

当n=2时，即为|A∪B|=|A|+|B|-|A∩B|，设（1）对k≤n成立。

下面证明（1）对n+1成立。

记A=A1∪A2∪……∪An，则S=A∪An+1，由公式|A∪B|=|A|+|B|-|A∩B|，有：

|S|=|A|+|An+1|-|A∩An+1|      （2）

由归纳假设：

|A|=|A1∪A2∪……∪An|=-++……+（-1）n-1|A1∩A2∩……∩An| （3）

又：|A∪An+1|=（A1∪A2∪……∪An）∩An+1=（A1∩An+1）∪（A2∩An+1）∪……∪（An∩An+1），再由归纳假设：

|An∩An+1|=-++……+（-1）n-1|A1∩A2∩……∩An∩An+1|（4）

把（3）、（4）代入（2），|S|=-++……+（-1）n|A1∩A2∩……∩An+1|。

这就证明了容斥原理成立。

若S中的子集为A，S对A的补集记为A—的话，由定理1容易得到容斥原理的另一种形式。

定理2（逐步淘汰原理）设A1，A2，……，An是集合S的子集，则：

……|=S-+-+……+（-1）n| A1∩A2∩……∩An |

显然，A1∪A2∪……∪An与……是集合S的一个划分，即：

S=（A1∪A2∪……∪An）∪（……）

且（A1∪A2∪……∪An）∩（……）=Φ。

由加法原理：|S|=|A1∪A2∪……∪An|+|……|。

再由定理1即得定理2。

容斥原理是加法原理的一个推广（当A1，A2，……，An两两不相交时，容斥原理即为加法原理），是组合计数的一个重要工具[2]。

例1：求在小于1 000的正整数中能被7或11整除的数的个数。

解：设A=﹛小于1 000的正整数中能被7整除的数﹜

B=﹛小于1 000的正整数中能被11整除的数﹜

|A|=[]=142，|B|=[]=90，|A∩B|=[]=12

由容斥原理，|A∪B|=|A|+|B|-|A∩B|=142+90-12=220。

上例是容斥原理的一个简单应用，问题的反面可以用逐步淘汰法解决，于是把问题作些改动就得到下面的竞赛题目。

例2（第4届莫斯科数学竞赛题）：在小于1 000的正整数中，既不能被5整除也不能被7整除的有多少个？

解：设S=﹛小于1 000的正整数﹜;A=﹛小于1 000的正整数中能被5整除的数﹜;B=﹛小于1 000的正整数中能被7整除的数﹜。则：

|A|=[]=199， |B|=[]=142， |A∩B|=[]=28

||=S-（|A|+|B|）+|A∩B|=999-（199+142）+28=686

例3（1960年-1961年波兰数学竞赛题）：某人给6个不同的收信人写了6封信，并且准备了6个写有收信人地址的信封。有多少种投放信笺的方法，使每份信笺与信封上的收信人都不相符？

解：设I为所有的装法构成的集合，则显然有I=6！，我们用1，2，3，4，5，6分别对信和信封编号，记Ai（i=1，2，…，6）为第i封信恰好装入第i个信封的所有装法构成的集合，则为第i封信不装进第i个信封的所有装法构成的集合，而所求的全部装错的装法的集合即为……。

由逐步淘汰原理，

|……|=|I|-+-+……+（-1）6 | A1∩A2∩……∩A6|

|Ai|=（6-1）！=5！=120， |Ai∩Aj|=（6-2）！=4！=24，……

|A1∩A2∩……∩Ak|=（6-k）！，| A1∩A2∩……∩A6|=（6-6）！=0！=1

所以：|……|=6！-120+24-6+2-+=256。

在上题的解答中，6这个数字不起特别的作用。全部推导对于任意n份信笺和n个信封的一般情形依然有效。

容斥原理不仅在关于计数的解答问题中有广泛的应用，有的证明题中将容斥原理与推理结合起来，也有很好的效果。

由上面的例子可以看出，容斥原理解决的问题大多涉及某一对象集合A满足性质集合P中的某些性质的元素的计数问题[3]。如A中不具备P中任何性质的元素个数有多少，A中至少具备P中r个性质的元素个数是多少，或A中恰好具备P中r个性质的元素的个数是多少等。

这里再给出可以应用容斥原理解决的问题作为练习。

示例1，参加大型团体表演的学生共240名，他们面对教练站成一行，自左至右按1，2，3，4，5，……依次报数，教练要求全体学生牢记各自所报的数，并做下列动作：先让报的数是3的倍数的全体同学向后转;接着让报的数是5的倍数的全体同学向后转;最后让报的数是7的倍数的全体同学向后转。问：（1）此时还有多少名同学面对教练？（2）面对教练的同学中，自左至右第66位同学所报的数是几？[参考答案：（1）136人;（2）118]

示例2，给出1 978个集合，每个集合都恰有40个元素，每两个集合都恰有一个公共元素，求这1 978个集合的并集所含元素的个数。（参考答案：77 143）

[参考文献]

[1]费振鹏.例析数学竞赛中的计数问题[J].中学数学月刊，2003（10）：44.

[2]周春荔.例谈用容斥原理证明问题[J].数学通讯，2002，2（4）：86.

[3]陈传理，张同君.竞赛数学教程[M].北京：高等教育出版社，2000.