使用數(shù)學(xué)歸納法證明容斥原理

使用數(shù)學(xué)歸納法證明容斥原理在計(jì)數(shù)時(shí)，必須注意沒(méi)有重復(fù)，沒(méi)有遺漏。為了使重疊部分不被重復(fù)計(jì)算，人們研究出一種新的計(jì)數(shù)方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對(duì)象的數(shù)目先計(jì)算出來(lái)，然后再把計(jì)數(shù)時(shí)重復(fù)計(jì)算的數(shù)目排斥出去，使得計(jì)算的結(jié)果既無(wú)遺漏又無(wú)重復(fù)，這種計(jì)數(shù)的方法稱為容斥原理。如果被計(jì)數(shù)的事物有A、B、C三類，那么，A類和B類和C類元素個(gè)數(shù)總和=A類元素個(gè)數(shù)+B類元素個(gè)數(shù)+C類元素個(gè)數(shù)—既是A類又是B類的元素個(gè)數(shù)—既是A類又是C類的元素個(gè)數(shù)—既是B類又是C類的元素個(gè)數(shù)+既是A類又是B類而且是C類的元素個(gè)數(shù)。（A∪B∪C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C）。例如：一次期末考試，某班有15人數(shù)學(xué)得滿分，有12人語(yǔ)文得滿分，并且有4人語(yǔ)、數(shù)都是滿分，那么這個(gè)班至少有一門得滿分的同學(xué)有多少人？分析：依題意，被計(jì)數(shù)的事物有語(yǔ)、數(shù)得滿分兩類，“數(shù)學(xué)得滿分”稱為“A類元素”，“語(yǔ)文得滿分”稱為“B類元素”，“語(yǔ)、數(shù)都是滿分”稱為“既是A類又是B類的元素”，“至少有一門得滿分的同學(xué)”稱為“A類和B類元素個(gè)數(shù)”的總和。為15+12-4=23。容斥原理怎么證明首先說(shuō)明一點(diǎn),數(shù)學(xué)歸納法原理是自然數(shù)的公理之一.

所以關(guān)于自然數(shù)的命題基本上都有數(shù)學(xué)歸納法背景.

常用的"依此類推","..."這樣的寫法本質(zhì)上也是數(shù)學(xué)歸納法的簡(jiǎn)略形式.

要在"形式上"不用數(shù)學(xué)歸納法證明容斥原理,可以用二項(xiàng)式定理.

設(shè)A[1],A[2],...,A[n]是n個(gè)集合,用|S|表示集合S的元素個(gè)數(shù),C(m,k)表示m中選k的組合數(shù).

證明容斥原理:|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]|.

對(duì)任意x∈A[1]∪A[2]∪...∪A[n],設(shè)A[1],A[2],...,A[n]中恰有m個(gè)集合包含x.

A[i]∩A[j]包含x當(dāng)且僅當(dāng)A[i]與A[j]都包含x.

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

在三三之交中恰有C(m,3)個(gè)集合包含x,依此類推.

可知在右端的和式中,x被計(jì)數(shù)的次數(shù)為C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1).

而由二項(xiàng)式定理,有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]中的任意元素,在右端和式中恰好被計(jì)數(shù)1次.

即證明了容斥原理.公式兩個(gè)集合的容斥關(guān)系公式：A∪B=|A∪B|=|A|+|B|-|A∩B|(∩：重合的部分）圖1三個(gè)集合的容斥關(guān)系公式：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|詳細(xì)推理如下：1、等式右邊改造={[（A+B-A∩B）+C-B∩C]-C∩A}+A∩B∩C2、維恩圖分塊標(biāo)記如右圖圖1：1245構(gòu)成A，2356構(gòu)成B，4567構(gòu)成C3、等式右邊（）里指的是下圖的1+2+3+4+5+6六部分：那么A∪B∪C還缺部分7。4、等式右邊[]號(hào)里+C（4+5+6+7）后，相當(dāng)于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。嚴(yán)格證明舉例例1（小學(xué)奧數(shù)題）某校六⑴班有學(xué)生45人，每人在暑假里都參加體育訓(xùn)練隊(duì)，其中參加足球隊(duì)的有25人，參加排球隊(duì)的有22人，參加游泳隊(duì)的有24人，足球、排球都參加的有12人，足球、游泳都參加的有9人，排球、游泳都參加的有8人，問(wèn)：三項(xiàng)都參加的有多少人？分析：參加足球隊(duì)的人數(shù)25人為A類元素，參加排球隊(duì)人數(shù)22人為B類元素，參加游泳隊(duì)的人數(shù)24人為C類元素，既是A類又是B類的為足球排球都參加的12人，既是B類又C類的為足球游泳都參加的9人，既是C類又是A類的為排球游泳都參加的8人，三項(xiàng)都參加的是A類B類C類的總和設(shè)為X。注意：這個(gè)題說(shuō)的每人都參加了體育訓(xùn)練隊(duì)，所以這個(gè)班的總?cè)藬?shù)即為A類B類和C類的總和。答案：25+22+24-12-9-8+X=45，解得X=3

例2（高中題）在1到1000的自然數(shù)中，能被3或5整除的數(shù)共有多少個(gè)？不能被3或5整除的數(shù)共有多少個(gè)？分析：顯然，這是一個(gè)重復(fù)計(jì)數(shù)問(wèn)題（當(dāng)然，如果不怕麻煩你可以分別去數(shù)3的倍數(shù)，5的倍數(shù)）。我們可以把“能被3或5整除的數(shù)”分別看成A類元素和B類元素，能“同時(shí)被3或5整除的數(shù)（15的倍數(shù)）”就是被重復(fù)計(jì)算的數(shù)，即“既是A類又是B類的元素”。求的是“A類或B類元素個(gè)數(shù)”。我們還不能直接計(jì)算，必須先求出所需條件。1000÷3=333……1，能被3整除的數(shù)有333個(gè)（想一想，這是為什么？）同理，可以求出其他的條件。例3（高中題）分母是1001的最簡(jiǎn)分?jǐn)?shù)一共有多少個(gè)？分析：這一題實(shí)際上就是找分子中不能與1001進(jìn)行約分的數(shù)。由于1001=7×11×13，所以就是找不能被7，11，13整除的數(shù)。解答：1~1001中，有7的倍數(shù)1001/7=143（個(gè))；有11的倍數(shù)1001/11=91（個(gè)），有13的倍數(shù)1001/13=77（個(gè)）；有7*11=77;77是11的倍數(shù)1001/77=13（個(gè)），有7*13=91;91是13的倍數(shù)；1001/91=11（個(gè)），有11*13=143;143是13的倍數(shù)1001/143=7（個(gè)）.有1001的倍數(shù)1個(gè)。由容斥原理知：在1~1001中，能被7或11或13整除的數(shù)有（143+91+77）-（13+11+7）+1=281（個(gè)），從而不能被7、11或13整除的數(shù)有1001-281=720（個(gè)）.也就是說(shuō)，分母為1001的最簡(jiǎn)分?jǐn)?shù)有720個(gè)。例4（小學(xué)奧數(shù)題）某個(gè)班的全體學(xué)生在進(jìn)行了短跑、游泳、投擲三個(gè)項(xiàng)目的測(cè)試后，有4名學(xué)生在這三個(gè)項(xiàng)目上都沒(méi)有達(dá)到優(yōu)秀，其余每人至少有一項(xiàng)達(dá)到了優(yōu)秀，達(dá)到了優(yōu)秀的這部分學(xué)生情況如下表：短跑游泳投擲短跑游泳短跑投擲游泳投擲短跑游泳投擲1718156652求這個(gè)班的學(xué)生共有多少人？分析：這個(gè)班的學(xué)生數(shù)，應(yīng)包括達(dá)到優(yōu)秀和沒(méi)有達(dá)到優(yōu)秀的。4+17+18+15-6-6-5+2=39（人）例5（小學(xué)奧數(shù)題）在一根長(zhǎng)的木棍上有三種刻度線，第一種刻度線將木棍分成10等份，第二種將木棍分成12等份，第三種將木棍分成15等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段？分析：很顯然，要計(jì)算木棍被鋸成多少段，只需要計(jì)算出木棍上共有多少條不同的刻度線，在此基礎(chǔ)上加1就是段數(shù)了。若按將木棍分成10等份的刻度線鋸開(kāi)，木棍有9條刻度線。在此木棍上加上將木棍分成12等份的11條刻度線，顯然刻度線有重復(fù)的，如5/10和6/12都是1/2。同樣再加上將木棍分成15等份的刻度線，也是如此。所以，我們應(yīng)該按容斥原理的方法來(lái)解決此問(wèn)題。用容斥原理的那一個(gè)呢？想一想，被計(jì)數(shù)的事物有那幾類？每一類的元素個(gè)數(shù)是多少？解答解一：[10，12，15]=60，設(shè)木棍60厘米60÷10=6厘米，60÷12=5厘米，60÷15=4(厘米10等分的為第一種刻度線，共10－1=9(條)12等分的為第二種刻度線，共12－1=11(條)15等分的為第三種刻度線，過(guò)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(條)三種刻度線重合的沒(méi)有，[6、5、4]=60因此，共有刻度線9+11+14－1－4－2=27條，木棍總共被鋸成27+1=28段。解二：總長(zhǎng)看成單位1分別分成10、12、15段。1/10與1/12的最小公倍數(shù)1/2，1/10與1/15的最小公倍數(shù)1/5，1/12與1/15的最小公倍數(shù)1/3，1/10，1/12和1/15的最小公倍數(shù)為1，有10+12+15-（2+5+3）+1=28解三：10、12、15的最小公倍數(shù)是60，假設(shè)木棍就是長(zhǎng)60，1、那么，分成10等份的每份6，刻度就是0，6，12，18，24，30，36，42，48，54，602、分成12等分的每份就是5，0，5，1