容斥問題公式及運用

容斥問題公式及運用容斥問題公式及運用容斥問題公式及運用資料僅供參考文件編號：2022年4月容斥問題公式及運用版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：容斥問題公式及運用在計數(shù)時，必須注意無一重復(fù)，無一遺漏。為了使重疊部分不被重復(fù)計算，研究出一種新的計數(shù)方法。這種方法的基本思路是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去，使得計算的結(jié)果既無遺漏又無重復(fù)，這種計數(shù)的方法稱為容斥原理。一、容斥原理1：兩個集合的容斥原理如果被計數(shù)的事物有A、B兩類，那么，先把A、B兩個集合的元素個數(shù)相加，發(fā)現(xiàn)既是A類又是B類的部分重復(fù)計算了一次，所以要減去。如下圖所示?！臼纠?】一次期末考試，某班有15人數(shù)學(xué)得滿分，有12人語文得滿分，并且有4人語、數(shù)都是滿分，那么這個班至少有一門得滿分的同學(xué)有多少人解：數(shù)學(xué)得滿分人數(shù)→A，語文得滿分人數(shù)→B，數(shù)學(xué)、語文都是滿分人數(shù)→A∩B，至少有一門得滿分人數(shù)→A∪B。A∪B=15+12-4=23，共有23人至少有一門得滿分。二、容斥原理2：三個集合的容斥原理如果被計數(shù)的事物有A、B、C三類，那么，將A、B、C三個集合的元素個數(shù)相加后發(fā)現(xiàn)兩兩重疊的部分重復(fù)計算了1次，三個集合公共部分被重復(fù)計算了2次。如下圖所示，灰色部分A∩B-A∩B∩C、B∩C-A∩B∩C、C∩A-A∩B∩C都被重復(fù)計算了1次，黑色部分A∩B∩C被重復(fù)計算了2次，因此總數(shù)A∪B∪C=A+B+C-（A∩B-A∩B∩C）-（B∩C-A∩B∩C）-（C∩A-A∩B∩C）-2A∩B∩C=A+B+C-A∩B-B∩C-C∩A+A∩B∩C。即得到：【示例2】某班有學(xué)生45人，每人都參加體育訓(xùn)練隊，其中參加足球隊的有25人，參加排球隊的有22人，參加游泳隊的有24人，足球、排球都參加的有12人，足球、游泳都參加的有9人，排球、游泳都參加的有8人，問：三項都參加的有多少人解：參加足球隊→A，參加排球隊→B，參加游泳隊→C，足球、排球都參加的→A∩B，足球、游泳都參加的→C∩A，排球、游泳都參加的→B∩C，三項都參加的→A∩B∩C。三項都參加的有A∩B∩C=A∪B∪C-A-B-C+A∩B+B∩C+C∩A=45-25-22-24+12+9+8=3人。例1在1到1000的自然數(shù)中，能被3或5整除的數(shù)共有多少個不能被3或5整除的數(shù)共有多少個分析：顯然，這是一個重復(fù)計數(shù)問題（當(dāng)然，如果不怕麻煩你可以分別去數(shù)3的倍數(shù)，5的倍數(shù)）。我們可以把“能被3或5整除的數(shù)”分別看成A類元素和B類元素，能“同時被3或5整除的數(shù)（15的倍數(shù)）”就是被重復(fù)計算的數(shù)，即“既是A類又是B類的元素”。求的是“A類或B類元素個數(shù)”。我們還不能直接計算，必須先求出所需條件。1000÷3=333……1，能被3整除的數(shù)有333個（想一想，這是為什么）同理，可以求出其他的條件。例2某個班的全體學(xué)生在進行了短跑、游泳、投擲三個項目的測試后，有4名學(xué)生在這三個項目上都沒有達到優(yōu)秀，其余每人至少有一項達到了優(yōu)秀，達到了優(yōu)秀的這部分學(xué)生情況如下表：短跑游泳投擲短跑游泳短跑投擲游泳投擲短跑游泳投擲1718156652求這個班的學(xué)生共有多少人分析：這個班的學(xué)生數(shù)，應(yīng)包括達到優(yōu)秀和沒有達到優(yōu)秀的。4+17+18+15-6-6-5+2=39（人）例3在一根長的木棍上有三種刻度線，第一種刻度線將木棍分成10等份，第二種將木棍分成12等份，第三種將木棍分成15等份。如果沿每條刻度線將木棍鋸斷，木棍總共被鋸成多少段分析：很顯然，要計算木棍被鋸成多少段，只需要計算出木棍上共有多少條不同的刻度線，在此基礎(chǔ)上加1就是段數(shù)了。若按將木棍分成10等份的刻度線鋸開，木棍有9條刻度線。在此木棍上加上將木棍分成12等份的11條刻度線，顯然刻度線有重復(fù)的，如5/10和6/12都是1/2。同樣再加上將木棍分成15等份的刻度線，也是如此。所以，我們應(yīng)該按容斥原理的方法來解決此問題。用容斥原理的那一個呢想一想，被計數(shù)的事物有那幾類每一類的元素個數(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等分的為第三種刻度線，過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的最小公倍數(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è)木棍就是長60，1、那么，分成10等份的每份6，刻度就是0，6，12，18，24，30，36，42，48，54，602、分成12等分的每份就是5，0，5，10，15，20，25，30，35，40，45，50，55，603、分成15等分的每份就是4，0，4，8，12，16，20，24，