|
容斥原理从字面意思看，“容”有包含之意，“斥”有排除之意。 我们先看一个例子： 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 在本题中，如果把数学得满分的15人记为A，把语文得满分的12人记为B，语、数都是满分的4人记为C，如下图：
问题是求“至少有一门得满分的同学有多少人”，其意义就是求有一门得满分的同学和有两门得满分的同学一共有多少人。 反映在图形中，有一门得满分的同学分为两部分，一是只有数学满分的为A-C，二是只有语文满分的为B-C，而有两门得满分的同学为C。把这三部分相加为A-C+B-C+C=A+B-C=15+12-4=23人，简单表示为A+B-C=15+12-4=23人。 显然，A中包含C，B中也包含C，也就是A、B中都“容”C，所以在计算A+B时，C就被算了2次，应该“斥”一个C，这就是“容斥”之意吧！
所以，“在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。” |
|
|
