[TOC]
# 集合的運算
## 并、交、補、差
### 概念
* 并：∪
* 交：∩
* 補：^或～或
* 差: -
:-: 
### 例題
1. 設全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，則集合（A ∩ B）∪ ~C 為（????? ）。
A） 空集??? B） {1}???C） {3，5}???D）{1，5}???? **E） {1，3，5}**
2. 設全集I = {a, b, c, d, e, f, g, h}， 集合B ∪ A= {a, b, c, d, e, f}， C ∩ A= {c, d, e}，A ∩ ~B = {a, d}， 那么集合C ∩ B ∩ A 為（ ）。
**A）{c, e} ** B) {d, e} C) {e} D) {c, d, e} E) {d, f}
## 容斥原理
### 概念
* 在計數時，為了使重疊部分不被重復計算，人們研究出一種新的計數方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內容中的所有對象的數目先計算出來，然后再把計數時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復，這種計數的方法稱為**容斥原理**。
* 對有限集合S，用表示S的元素個數。
* 容斥原理的第一形式：設A，B是有限集合，則
:-: 
* 容斥原理的第二形式：設A、B、C是有限集合，則
:-: 
### 例題
1. 75名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有多少名兒童沒有玩過其中任何一種。
> **700/5=140人次
> 140-20*3=80人次（玩2種+玩1種）
> 55-20=35人（玩2種）
> 80-35*2=10人次（玩1種）
> 75-20-35-10=10人（一種都沒玩）**
2. 某學校足球隊有球衣30件，籃球隊有球衣15件，排球隊有球衣18件，三隊隊員總數為50人，其中有2人同時參加3個隊，那么同時只參加兩個隊的隊員有多少？
> ** 分析：
> A+B+C-(A與B重合+A與C重合+B與C重合)+A、B、C重合=總數
> 30+15+18-(A與B重合+A與C重合+B與C重合)+2=50
> (A與B重合+A與C重合+B與C重合)=30+15+18+2-50=15人 **
3. 例題：分母是1001的最簡分數一共有多少個？
> **分析：
> 1001=7×11×13
> 分子中不能含有質因數7、11、13
> 即1至1001中，不能被7、11、13整除的數有多少個？
> 1001÷7=143
> 1001÷11=91
> 1001÷13=77
> 1001÷[7,11]=13, [7,11]----7和11的最小公倍數
> 1001÷[7,13]=11, -------
> 1001÷[11,13]=7, -----
> 1001÷[7,11,13]=1
> 143+91+77-(13+11+7)+1=281個
> 不能被7，11，13整除的數有 1001-281=720個**
# 排列與組合
## 排列的定義
* 排列的定義：從n個不同元素中,任取m個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列。
* 排列數公式:
* 全排列問題：n個不同的元素排成一排，排列方法有：
## 組合的定義
* 組合的定義：從n個不同元素中，任取m個元素，并成一組，叫做從n個不同元素中取出m個元素的一個組合。
* 組合數公式：
>[danger]排列與組合的區別與聯系：與順序有關的為排列問題，與順序無關的為組合問題。
# 加法原理和乘法原理
## 加法原理
做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有`$ m_{n} $`種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。每一種方法都能夠直接達成目標。
## 乘法原理
做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有`$ m_{n} $`種不同的方法，那么完成這件事共有N=m1×m2×m3×…×mn種不同的方法。
從A到C共有多少中走法？
## 例題
1. 學校師生合影，共8個學生，4個老師，要求老師在學生中間，且老師互不相鄰，共有多少種不同的合影方式？
> 解：先排學生共有`$ P_{8}^{8} $`種排法，然后把老師插入學生之間的空檔，共有7個空檔可插，選其中的4個空檔,共有`$ P_{7}^{4} $`種選法.根據乘法原理,共有的不同坐法為`$ P_{8}^{8} P_{7}^{4} $`種。
> 插入法：對于某兩個元素或者幾個元素要求不相鄰的問題，可以用插入法。即先排好沒有限制條件的元素，然后將有限制條件的元素按要求插入排好元素的空檔之中即可。
2. 書架上有21本書，編號從1到21，從其中選4本，其中每兩本的編號都不相鄰的選法一共有多少種？
> 插空法：假如書架上現已放好了17本書，現要將4本書插入進去且使之任意兩本不相鄰，即在18個空中插入4本書，列式為：`$ C_{18}^{4} $`=3060。
3. 5個男生3個女生排成一排，3個女生要排在一起,有多少種不同的排法？
> 解：因為女生要排在一起，所以可以將3個女生看成是一個人，與5個男生作全排列,有`$ P_{6}^{6} $`種排法，其中女生內部也有`$ P_{3}^{3} $`種排法，根據乘法原理，共有`$ P_{6}^{6} P_{3}^{3} $`種不同的排法。
> 捆綁法：要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內部也可以作排列。
4. 袋中有不同年份生產的5分硬幣23個,不同年份生產的1角硬幣10個,如果從袋中取出2元錢,有多少種取法？
> 分析 此題是一個組合問題,若是直接考慮取錢的問題的話,情況比較多,也顯得比較凌亂,難以理出頭緒來.但是如果根據組合數性質考慮剩余問題的話,就會很容易解決問題.
> 解：把所有的硬幣全部取出來,將得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個5分或1個5分與1個1角,所以共有`$ C_{23}^{3}+C_{21}^{1}+C_{10}^{1} $`
> 剩余法:在組合問題中,有多少取法,就有多少種剩法,他們是一一對應的,因此,當求取法困難時,可轉化為求剩法.
5. 學校安排考試科目9門,語文要在數學之前考,有多少種不同的安排順序?
> 對于任何一個排列問題,就其中的兩個元素來講的話,他們的排列順序只有兩種情況,并且在整個排列中,他們出現的機會是均等的,因此要求其中的某一種情況,能夠得到全體,那么問題就可以解決了.并且也避免了問題的復雜性.
> 解：不加任何限制條件,整個排法有`$ P_{9}^{9} $`種,“語文安排在數學之前考”,與“數學安排在語文之前考”的排法是相等的,所以語文安排在數學之前考的排法共有`$ (1/2)*P_{3}^{3} $`。
> 對等法:在有些題目中,它的限制條件的肯定與否定是對等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.
6. 某個班級共有43位同學,從中任抽5人,正、副班長、團支部書記至少有一人在內的抽法有多少種?
> 分析 此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就可以簡化計算過程.
> 解:43人中任抽5人的方法有`$ C_{43}^{5} $`種,正副班長,團支部書記都不在內的抽法有`$ C_{40}^{5} $`種,所以正副班長,團支部書記至少有1人在內的抽法有`$ C_{43}^{5}-C_{40}^{5} $`種.
> 排異法:有些問題,正面直接考慮比較復雜,而它的反面往往比較簡捷,可以先求出它的反面,再從整體中排除.
