论文：容斥原理的应用

1 由《集合中元素的个数》到“莎士比亚巧合”-------容斥原理的应用举例莎士比亚是英国著名戏剧家，其不仅才华横溢，更有一个有趣的巧合流传甚广。他生于1564 年 4 月 23 日，卒于 1616 年 4 月 23 日，生卒日期相同． 下面， 我们就从这个巧合说起，谈谈组合数学中最重要原理之一的容斥原理．例 1 若按每年 365 天计算， 且一个人生卒日期均是随机的，则他生卒日期相同的概率是多少？显然是3651.试问，两个人都生卒日期相同呢？两个人中至少一个人生卒日期相同的概率呢？如果是N 个人呢？为解决这个问题，可参考普通高中数学课程标准 (实验)中，必修课程 (数学 1)13页阅读与思考 《集合中元素的个数》一节的内容。 对求多个集合的元素总个数，这样解释：).()()()(,,BAcardBcardAcardBAcardBA有有限集合一般地，对于任意两个(card（A）表示有限集合A 中元素的个数） ，这实质就是两个集合的容斥关系的体现. 如果被计数的事物有A、B 两类，那么，A 类 B 类元素个数总和= 属于 A 类元素个数 + 属于 B 类元素个数 — 既是 A 类又是 B 类的元素个数 . ).()()()(BAcardBcardAcardBAcard作：两个集合的容斥关系记如果被计数的事物有A、B、C 三类，那么， A 类和 B 类和 C 类元素个数总和= A 类元素个数 + B 类元素个数 +C 类元素个数 — 既是 A 类又是 B 类的元素个数 — 既是 A 类又是 C类的元素个数 — 既是 B 类又是 C 类的元素个数 +既是 A 类又是 B 类而且是 C 类的元素个数. 三个集合的容斥关系公式记作：).()()()()()()()(CBAcardACcardCBcardBAcardCcardBcardAcardCBAcard现详细推理如下：Venn 图分块标记如右图：1245 构成 A ，2356 构成 B，4567 构成 C 上式简记为：A∪B∪C = {[（A+B - A∩B ）+C - B∩ C] - C∩ A }+ A ∩ B∩C（1） 等式左边指的是右图中的 1+2+3+4+5+6+7 七部分；（2）等式右边（）指的是右图中的1+2+3+4+5+6 六部分；（3）等式右边[ ] 相当于 A∪B∪C 多加了 4 ；（4）等式右边{ } 相当于 A∪B∪C 多减了 5；（5）而A∩B∩C 就是 5.则加上 A∩B∩C，刚好是A∪B∪C . 对于 n 个集合不难推理类似定理，即19世纪英国数学家西尔维斯特（2 .AA(.)1(---),2,1(11-1111表示）元素的个数用集合都是有限集合，则有容斥原理：设ininnjikjinjijiniiiniiAAAAAAAAniA下我们思考例 1所提问题，...