使用数学归纳法证明容斥原理

使用数学归纳法证明容斥原理在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和=A类元素个数+B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C）。例如：一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？分析：依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。为15+12-4=23。容斥原理怎么证明首先说明一点,数学归纳法原理是自然数的公理之一.

所以关于自然数的命题基本上都有数学归纳法背景.

常用的"依此类推","..."这样的写法本质上也是数学归纳法的简略形式.

要在"形式上"不用数学归纳法证明容斥原理,可以用二项式定理.

设A[1],A[2],...,A[n]是n个集合,用|S|表示集合S的元素个数,C(m,k)表示m中选k的组合数.

证明容斥原理:|A[1]∪A[2]∪...∪A[n]|=∑{1≤i≤n}|A[i]|-∑{1≤i<j≤n}|A[i]∩A[j]|

+∑{1≤i<j<k≤n}|A[i]∩A[j]∩A[k]|-...+(-1)^(n-1)·|A[1]∩A[2]∩...∩A[n]|.

对任意x∈A[1]∪A[2]∪...∪A[n],设A[1],A[2],...,A[n]中恰有m个集合包含x.

A[i]∩A[j]包含x当且仅当A[i]与A[j]都包含x.

因此在A[1],A[2],...,A[n]的两两之交中恰有C(m,2)个交集包含x.

在三三之交中恰有C(m,3)个集合包含x,依此类推.

可知在右端的和式中,x被计数的次数为C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1).

而由二项式定理,有0=(1-1)^m=1-C(m,1)+C(m,2)-C(m,3)+...+(-1)^m.

即C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1)=1.

A[1]∪A[2]∪...∪A[n]中的任意元素,在右端和式中恰好被计数1次.

即证明了容斥原理.公式两个集合的容斥关系公式：A∪B=|A∪B|=|A|+|B|-|A∩B|(∩：重合的部分）图1三个集合的容斥关系公式：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|详细推理如下：1、等式右边改造={[（A+B-A∩B）+C-B∩C]-C∩A}+A∩B∩C2、维恩图分块标记如右图图1：1245构成A，2356构成B，4567构成C3、等式右边（）里指的是下图的1+2+3+4+5+6六部分：那么A∪B∪C还缺部分7。4、等式右边[]号里+C（4+5+6+7）后，相当于A∪B∪C多加了4+5+6三部分，减去B∩C（即5+6两部分）后，还多加了部分4。5、等式右边{}里减去C∩A（即4+5两部分）后，A∪B∪C又多减了部分5，则加上A∩B∩C（即5）刚好是A∪B∪C。严格证明举例例1（小学奥数题）某校六⑴班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？分析：参加足球队的人数25人为A类元素，参加排球队人数22人为B类元素，参加游泳队的人数24人为C类元素，既是A类又是B类的为足球排球都参加的12人，既是B类又C类的为足球游泳都参加的9人，既是C类又是A类的为排球游泳都参加的8人，三项都参加的是A类B类C类的总和设为X。注意：这个题说的每人都参加了体育训练队，所以这个班的总人数即为A类B类和C类的总和。答案：25+22+24-12-9-8+X=45，解得X=3

例2（高中题）在1到1000的自然数中，能被3或5整除的数共有多少个？不能被3或5整除的数共有多少个？分析：显然，这是一个重复计数问题（当然，如果不怕麻烦你可以分别去数3的倍数，5的倍数）。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素，能“同时被3或5整除的数（15的倍数）”就是被重复计算的数，即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。我们还不能直接计算，必须先求出所需条件。1000÷3=333……1，能被3整除的数有333个（想一想，这是为什么？）同理，可以求出其他的条件。例3（高中题）分母是1001的最简分数一共有多少个？分析：这一题实际上就是找分子中不能与1001进行约分的数。由于1001=7×11×13，所以就是找不能被7，11，13整除的数。解答：1~1001中，有7的倍数1001/7=143（个)；有11的倍数1001/11=91（个），有13的倍数1001/13=77（个）；有7*11=77;77是11的倍数1001/77=13（个），有7*13=91;91是13的倍数；1001/91=11（个），有11*13=143;143是13的倍数1001/143=7（个）.有1001的倍数1个。由容斥原理知：在1~1001中，能被7或11或13整除的数有（143+91+77）-（13+11+7）+1=281（个），从而不能被7、11或13整除的数有1001-281=720（个）.也就是说，分母为1001的最简分数有720个。例4（小学奥数题）某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后，有4名学生在这三个项目上都没有达到优秀，其余每人至少有一项达到了优秀，达到了优秀的这部分学生情况如下表：短跑游泳投掷短跑游泳短跑投掷游泳投掷短跑游泳投掷1718156652求这个班的学生共有多少人？分析：这个班的学生数，应包括达到优秀和没有达到优秀的。4+17+18+15-6-6-5+2=39（人）例5（小学奥数题）在一根长的木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？分析：很显然，要计算木棍被锯成多少段，只需要计算出木棍上共有多少条不同的刻度线，在此基础上加1就是段数了。若按将木棍分成10等份的刻度线锯开，木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线，显然刻度线有重复的，如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线，也是如此。所以，我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢？想一想，被计数的事物有那几类？每一类的元素个数是多少？解答解一：[10，12，15]=60，设木棍60厘米60÷10=6厘米，60÷12=5厘米，60÷15=4(厘米10等分的为第一种刻度线，共10－1=9(条)12等分的为第二种刻度线，共12－1=11(条)15等分的为第三种刻度线，过15－1=14(条)第一种与第二种刻度线重合的[6，5]=30，60÷30－1=2－1=1(条)第一种与第三种刻度线重合的[6，4]=12，60÷12－1=5－1=4(条)第二种与第三种刻度线重合的[5，4]=20，60÷20－1=3－1=2(条)三种刻度线重合的没有，[6、5、4]=60因此，共有刻度线9+11+14－1－4－2=27条，木棍总共被锯成27+1=28段。解二：总长看成单位1分别分成10、12、15段。1/10与1/12的最小公倍数1/2，1/10与1/15的最小公倍数1/5，1/12与1/15的最小公倍数1/3，1/10，1/12和1/15的最小公倍数为1，有10+12+15-（2+5+3）+1=28解三：10、12、15的最小公倍数是60，假设木棍就是长60，1、那么，分成10等份的每份6，刻度就是0，6，12，18，24，30，36，42，48，54，602、分成12等分的每份就是5，0，5，1