2014級(jí)離散第3章-包含排斥原理

1、3-3 包含排斥原理 (容斥原理)要求： 掌握n個(gè)集合的包含排斥原理，并應(yīng)用它求解實(shí)際問題。(1)max(|A|，|B|)|AB|A|+|B|(2)|AB|min(|A|，|B|)(3)|A|-|B|A-B|A|(4)|AB|=|A|+|B|-2|AB| 一、有限集合的計(jì)數(shù) 設(shè)A，B為有限集合，其元素個(gè)數(shù)分別為|A|，|B|，根據(jù)集合運(yùn)算的定義，顯然以下各式成立。二、包含排斥原理1、定理3-3.1：設(shè)A1，A2為有限集合，其元素個(gè)數(shù)分別為|A1|，|A2|，則|A1A2|=|A1|+|A2|-|A1A2|，此定理被稱作包含排斥原理。證明：a)當(dāng)A1A2=，則|A1A2|=|A1|+|A2|b)

2、若A1A2，則|A1|=|A1A2|+|A1A2|，|A2|=|A1A2|+|A1A2|所以|A1|+|A2|=|A1A2|+|A1A2|+ |A1A2|+|A1A2| =|A1A2|+|A1A2|+2|A1A2|而|A1A2|+|A1A2|+|A1A2|=|A1A2|故|A1A2|=|A1|+|A2|-|A1A2| 解：設(shè)A為從1到500的整數(shù)中，能被3除盡的數(shù)的集合。 B為從1到500的整數(shù)中，能被5除盡的數(shù)的集合。則 A=500/3=166 （x表示不超過x的最大整數(shù)） B=500/5=100 AB=500/（3*5）=33由包含排斥原理：AB=A+B-AB=166+100-33=233

3、即從1到500的整數(shù)中，能被3或5除盡的數(shù)有233個(gè)。 例1：求從1到500的整數(shù)中，能被3或5除盡的數(shù)的個(gè)數(shù)。例題2 假設(shè)在10名青年中有5名是工人，7名是學(xué)生，其中兼具工人和學(xué)生雙重身份的青年有3名，問有幾名既不是工人又不是學(xué)生。解：設(shè)工人的集合為W，學(xué)生的集合為S。則根據(jù)題設(shè)有|E|=10，W=5，S=7，WS=3，則或者是工人或者是學(xué)生的為 WS=W+S-WS=5+7-3=9，則 (WS)=E-WS=10-9=1。有1名既不是工人又不是學(xué)生。 2、三個(gè)集合的包含排斥原理：對(duì)于三個(gè)集合A1，A2和A3，其元素個(gè)數(shù)分別為|A1|，|A2|，|A3|，則|A1A2A3|=|A1|+|A2|+

4、|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|例題3 在某工廠裝配30輛汽車，可供選擇的設(shè)備是收音機(jī)、空氣調(diào)節(jié)器和對(duì)講機(jī)。已知其中有15輛汽車有收音機(jī)，8輛有空氣調(diào)節(jié)器，6輛有對(duì)講機(jī)，而且其中有3輛汽車這三樣設(shè)備都有。我們希望至少有多少輛汽車沒有任何設(shè)備。解：設(shè)A1，A2和A3分別表示配有收音機(jī)、空氣調(diào)節(jié)器和對(duì)講機(jī)的汽車集合。因此|A1|=15，|A2|=8，|A3|=6， |A1A2A3|=3，故|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|=15+8+6 -|A1A2|-|A1A3|-|A2A3|+3=32 -|A1A2|-|A1A3|-|A2A3|因?yàn)閨A1A2|A1A2A3|，|A1A3|A1A2A3|，|A2A3|A1A2A3|所以|A1A2A3|32-3-3-3=23即至多有23輛汽車有一個(gè)或幾個(gè)選擇的設(shè)備，因此至少有7輛汽車不提供任何可選擇的設(shè)備。 練習(xí)： 某年級(jí)有59名學(xué)生，期末考高等數(shù)學(xué)、線性代數(shù)和英語(yǔ)三門課。已知高等數(shù)學(xué)、線性代數(shù)和英語(yǔ)各門課的及格人數(shù)分別為47人、49人和50人。其中高等數(shù)學(xué)、英語(yǔ)都及格的有43人，線性代數(shù)和英語(yǔ)都及格的有42人，三門課都及格的有40人，三門課都不及格的有1人。問高等