论文容斥原理的应用

由《集合中元素的个数》到“莎士比亚巧合” 容斥原理的应用举例莎士比亚是英国著名戏剧家，其不仅才华横溢，更有一个有趣的巧合流传甚广。他生于1564年4月23廿，卒于1616年4月23 |_1,生卒日期相

由《集合中元素的个数》到“莎士比亚巧合” -------- 容斥原理的应用举例 莎士比亚是英国著名戏剧家，其不仅才华横溢，更有一个有趣的巧合流传甚广。他生于 年月廿，卒于年月生卒日期相同.下面，我们就从这个巧合说起， 谈谈组合数 15644231616423 |_1, 学中最重要原理之一的容斥原理. 例若按每年天计算，且一个人生卒日期均是随机的，则他生卒口期相同的概率 365 1 是多少？显然是上.试问，两个人都生卒口期相同呢？两个人中至少一个人生卒口期相同 365 的概率呢？如果是个人呢？ N 为解决这个问题，可参考普通高中数学课程标准(实验)中，必修课程(数学页阅读与思考《集 1)13 合中元素的个数》一节的内容。对求多个集合的元素总个数，这样解释： card {Acardcardcard (AB). 一般地，对于任意两个有限集合 有 A, 5, UB) =(A) +(B) -Pl 表示有限集合中元素的个数)，这实质就是两个集合的容斥关系的体现. (card (A)A 属 如果被计数的事物有、两类,那么,类类元素个数总和=属于类元素个数+于类元素 ABABAB 个数一既是类又是类的元素个数. AB 两个集合的容斥关系记作： cardcardcard (B) -cardB). (A UB) =(A) +(A A 三类, C 如果被计数的事物有、、那么，类和类和类元素个数总和=类元 素个数+ ABABCAB 类元素个数类元素个数一既是类又是类的元素个数一既是类又是类的元素个数一既是类 +CABAC B 又是类的元素个数+既是类又是类而且是类的元素个数. CABC 三个集合的容斥关系公式记作： cardcard(A) +cardcard (C)-cardcard(Br\C) (AUBUC) =(B) +(APIS)- -cardcard (C AA) +(A fl 8D C). 现详细推理如下： 图分块标记如右图:构成构成构成上式 Venn1245A, 2356B, 4567C 简记为： AUBUC= {[(A+B -ADB)+C -BQC]. CHA }+ AABAC (1) 等式左边指的是 右图中的七部 分； 1+2+3+4+5+6+7 (2) 等式右边()指的是右图中的六部分； 1+2+3+4+5+6 (3) 等式右边[]相当于多加了 ； AUBUC4 (4) 等式右边{ }相当于多减了 ； AUBUC5 (5) 而就是.则加上刚好是 AABAC5AnBnC,AUBUC. 对于〃个集合不难推理类似定理，即世纪英国数学家西尔维斯特首先 ( 19J.J.Sylverster)