容斥原理讲义模板.doc

容斥原理讲义容斥原理例题在很多计数问题中常用到数学上的一个包含与排除原理,也称为容斥原理。为了说明这个原理,我们先介绍一些集合的初步知识。在讨论问题时,常常需要把具有某种性质的同类事物放在一起考虑。如:A={五(1)班全体同学}。我们称一些事物的全体为一个集合。A={五(1)班全体同学}就是一个集合。B={全体自然数}={1,2,3,4,…}是一个具体的有无限多个元素的集合。C={在1,2,3,…,100中能被3整除的数}={3,6,9,12,…,99}是一个具有有限多个元素的集合。通常集合用大写的英文字母A、B、C、…表示。构成这个集合的事物称为这个集合的元素。如上面例子中五(1)班的每一位同学均是集合A的一个元素。又如在例1中任何一个自然数都是集合B的元素。像集合B这种含有无限多个元素的集合称为无限集。像集合C这样含有有限多个元素的集合称为有限集。有限集合所含元素的个数常用符合︱A︱、︱B︱、︱C︱、…表示。记号A∪B表示所有属于集合A或属于集合B的元素所组成的集合,就是下边示意图中两个圆所覆盖的部分。集合A∪B叫做集合A与的并集。“∪”读作“并”,“A∪B”读AB设集合A={1,2,3,4},集合B={2,4,6,8},则A∪B={1,2,3,4,6,8}。元素2,4在集合A、B中都有,在并集中只写一个。记号A∩B表示所有既属于集合A也属于集合B中的元素的全体。就是上面图中阴影部分所表示的集合。即是由集合A、B的公共元素所组成的集合。它称为集合A、B的交集。符号“∩”读作“交”,“A∩B”读作“A交B”。如例3中的集合A、B,则A∩B={2,4}。设集合I={1,3,5,7,9},集合A={3,5,7},={属于集合,但不属于集合A的全体元素}={1,9}。我们称属于集合I但不属于集合A的元素的集合为集合A在集合I中的补集(或余集),如下图中阴影部分表示的集合(整个长方形表示集合I),常记作。如例4中={1,9}就是集合A在集合I中的补集。显然,A和没有公共元素,即A∩=(表示空集,即没有元素的集合)。A此外,A∪=I。对于两个没有公共元素的集合A和B,显然有︱A∪B︱=︱A︱+︱B︱。例如,A={1,2,…,100},B={101},则A∪B={1,2,…,100,101},A∩B=,所以︱A∪B︱=101=100+1=︱A︱+︱B︱。如果集合A与B有公共元素,例如A={1,2,…,100},B={90,91,…,101},则A∩B={90,91,…,100},A∪B={1,2,…,100,101}。此时,︱A∪B︱与︱A︱+︱B︱有什么关系呢?在这个例中,︱A∪B︱=101,︱A︱+︱B︱=100+12=112,所以︱A∪B︱=︱A︱+︱B︱-11。我们注意到,11恰为A∩B的元素个数,这是合理的,因为在求︱A∪B︱时,90,91,…,100这11个数各被计入一次,而在求︱A︱+︱B︱时,这11个数各被计入两次(即多算了一次),并且这11个数组成的集合恰为A∩B。因此得到:︱A∪B︱=︱A︱+︱B︱-︱A∩B︱(1)【重要公式,两个集合的容斥关系公式】这就是关于两个集合的容斥原理:集合A与B的元素个数,等于集合A的元素个数与集合B的元素个数的和,减去集合A与B的交集的元素个数。是容斥原理的第一个公式,我们还能够用下图来说明。如图我们用N1、