# 排列組合與機率

<font size = 5><br>
:::info
想當初在學機率之前就對機率有很大的興趣了，還因此在自主學習時段去Coursera修葉教授開的「頑想學概率」，結果上到懷疑人生。還記得在第一堂課教授就有講學機率的用意：因為我們對世界上某些事情仍然了解不夠，只能用一些機率的模型去model。比方說你丟一枚硬幣，假如你可以像No Game No Life最後一集的巫女一樣使用「血壞」獲得超強的動態視力，你就可以馬上判斷硬幣落下後的運動了。（連結在此，可以直接跳到14:50看就可以知道我在講什麼了：https://youtu.be/Te08PqgZk-Y?si=QzB8fYNnriRiZeBi）
但是我們普遍都沒有這麼厲害的眼睛，因此就會需要算正、反面朝上的機率，再推測結果，機率的用意就是在這裡！
:::
</font>

## (1)笛摩根定律

<font size = 5><br>
$$De Morgan's Law:(A\cup B)^C = A^C\cap B^C$$
$$1.令X\in(A\cup B)^C \Rightarrow X\notin A\;and\;X\notin B$$
$$\Rightarrow X\in A^C\;and\;X\in B^C \Rightarrow X\in A^C\cap B^C \Rightarrow(A\cup B)^C\subseteq A^C\cap B^C$$
$$2.令X\in A^C\cap B^C \Rightarrow X\in A^C\;and\;B^C$$
$$If\;X\notin(A\cup B)^C\Rightarrow X\in A\cup B\Rightarrow X\in A\;or\;X\in B$$可以發現此結果和假設矛盾，因此$$X\in(A\cup B)^C \Rightarrow(A^C\cap B^C)\subseteq(A\cup B)^C$$
結合1.和2.的結論，我們可得$$(A\cup B)^C = A^C \cap B^C$$
事實上，我們也可以用以下文氏圖來簡單理解
</font>

## (2)全機率定理

<font size = 5><br>
在證全機率定理之前，我們得先理解條件機率的定義：在事件$B$發生的條件下，事件$A$發生的機率為$$P(A|B) = \frac{P(A\cap B)}{P(B)}$$
我們一樣可以用文氏圖來理解
$P(A|B)$即為事件$B$(藍色範圍)當中$A\cap B$(紅色範圍)發生的機率。
接著，藉由移項可以得到$$P(A|B)P(B) = P(A\cap B)$$
同理：$$P(B|A)P(A) = P(A\cap B)$$
這時候就可以開始證明全機率定理啦!
令$C_1, C_2, ... C_n$皆互斥且$C_1\cup C_2\,\cup\,...\cup\, C_n = S$，則對於$S$當中的任意事件$A$:$$ A = A\cap (C_1\cup C_2\,\cup\,... \cup\, C_n)$$
$$ = (A\cap C_1)\cup(A\cap C_2)\cup\, ...\cup(A\cap C_n)$$
$$\Rightarrow P(A) = P[(A\cap C_1)\cup(A\cap C_2)\cup\, ...\cup(A\cap C_n)]$$
可以注意到因為$C_1, C_2, ... C_n$皆互斥，所以$(A\cap C_1), (A\cap C_2), ..., (A\cap C_n)$也都互斥
故$$P(A) = P(A\cap C_1)+P(A\cap C_2)+...+P(A\cap C_n) = \sum_{i=0}^n P(A\cap C_i)$$
$$P(A) = \sum_{i=0}^n P(A|C_i)P(C_i)$$

:::info
前兩個定理如果用文氏圖看應該會覺得蠻好理解的，但是證明依然不可或缺！有時候這種明顯的定理會反而不知道要從哪裡開始證明，這讓我想到當初在教某個國小生「圖形放大成n倍，面積會變成$n^2$倍」，比方說一個正方形的邊長放大成2倍，面積顯然就會變成4倍，因為正方形面積就是$(邊長)^2$嘛。但是如果是像百變怪一樣的不規則形狀呢？要怎麼解釋呢？這時就會發現要講清楚不容易，甚至很難，因此證明還是很重要的。
:::
</font>

## (3)貝氏定理

<font size = 5><br>
我們再來回頭看一次條件機率的定義:$$P(A|B) = \frac{P(A\cap B)}{P(B)}$$
若把條件機率的定義中的$P(A\cap B)$替換成$P(B|A)P(A)$，即可得到貝是定理:$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$
同時呢，我們可以做一點延伸:
令$C_1, C_2, ... C_n$皆互斥且$C_1\cup C_2\,\cup\,...\cup\, C_n = S$，則對於$S$當中的任意事件$A$:
$$P(C_k|A) = \frac{P(C_k\cap A)}{P(A)}\;, k = 1, 2, ..., n$$
從前面我們已經知道$P(C_k\cap A) = P(A|C_k)P(C_k)$，以及$P(A) = \sum_{i=0}^n P(A|C_i)P(C_i)$
因此我們可得:$$P(C_k|A) = \frac{P(A|C_k)P(C_k)}{\displaystyle\sum_{i=0}^n P(A|C_i)P(C_i)}$$
</font>

## (4)巴斯卡定理

<font size = 5><br>
首先我們先來看看巴斯卡定理的樣子
$$C_{m-1}^{n-1}+C_{m}^{n-1} = C_{m}^{n}$$
要證明其實不難，只要列出分式然後再通分就行了，不信我現在就寫給你看
$$左式 = \frac{(n-1)!}{(n-m)!(m-1)!}+\frac{(n-1)!}{(n-m-1)!m!}$$
$$ = \frac{(n-1)!\cdot m}{(n-m)!(m-1)!\cdot m}+\frac{(n-1)!(n-m)}{(n-m-1)!m!(n-m)}$$
可以發現在分子分母同乘某些東西，使得分母都變成了$(n-m)!m!$
$$ = \frac{(n-1)!\cdot m + (n-1)!(n-m)}{(n-m)!m!} = \frac{(n-1)!(m+n-m)}{(n-m)!m!} $$
$$ = \frac{n!}{(n-m)!m!} = C_m^n = 右式$$
雖說證明不難，但這公式看起來挺無理頭的啊，到底用處為何呢？
這邊幫大家舉一個生活中可能會遇到的例子。
假設你某天正在和朋友開心地吃著蛋炒飯的時候，結果老闆不小心在裡面加了卡羅萊納死神辣椒，你頓時感到你的嘴吧、舌頭、食道通通都燒起來了，你朋友為了不讓你辣到休克，馬上跑到一間冰淇淋店替你買冰淇淋解辣。
「你要幾球啊？」你朋友透過電話問你
「唔...我...快厶」你感到痛不欲生，正在腦袋裡飛快的想好遺言
「五？你想吃五球哦？嘿嘿，沒想到你也挺奢侈的嘛！」
冰淇淋店的玻璃冷凍櫃裡有20種口味，「20種口味當中取5種不重複...這樣是$C_5^{20}$...有$15504$種組合！」
這時你不禁慶幸你的朋友有學過珠心算，不然他等等可能就要拿出紙筆來算了「誒？等等，我記得你是不是喜歡榴槤口味的冰淇淋？」「嘔...」到底是哪個蠢蛋會喜歡榴槤口味的冰淇淋啊，你忍不住在心裡吐槽「5種口味當中如果必須要有榴槤口味，那麼就是剩下的19種口味要選4種了，所以是$C_4^{19} = 3876$種！」
「哭...啊...榴槤...噁心死...了」你擠出剩下的最後一點力氣說到
「啊！拍謝，我記錯人了啦！哈哈，如果20種口味中選五種，而且不要榴槤的話，這樣是$C_5^{19} = 11628$種！」正當你疑惑他到底記成哪個怪人的時候，電話那頭又傳來朋友的聲音
「咦？等等」你珠心算很強的朋友突然發現一件事情「$11628+3876剛好就是15504$耶！」他拿出紙筆並寫下$C_4^{19}+C_5^{19} = C_5^{20}$，在你正要催他買快一點之前他就繼續說下去了「哦哦哦，原來我剛才就是把樣本空間以『榴槤口味』進行分割，總共選冰淇淋的方法數是$C_5^{20}$，包含榴槤口味的選法有$C_4^{19}$種，沒有榴槤口味的方法有$C_5^{19}$種，兩個加起來自然就是$C_5^{20}$了！太厲害了！這就是著名的巴斯卡定理喔！電視機前面的大朋友小朋友，數學是不是很有趣啊？」
「對...啦...好棒...棒」你已經不知道要從哪裡開始吐槽了，此時你只希望你朋友可以買快一點
「蛤？老闆你說五球要675?那我還是去買水好了」
你緊閉雙眼，心中暗暗決定要和這位朋友絕交

:::info
晚輔在打這個的時候不知道為何突然感覺來了就好想打東打西，不過其實還挺好玩的，就是有點花時間。總之希望這樣可以讓大家在想這個公式的時候能比較清楚，不要像我以前一樣每次都要想好久。
:::
</font>

## (5)二項式定理

<font size = 5><br>
國中時我們都學過這個乘法公式：$$(x+y)^2 = x^2+2xy+y^2$$
高中後則學過比較進階的：$$(x+y)^3 = x^3+3x^2y+3xy^2+y^3$$
那如果今天是$(x+y)^n$呢？
我們可以先試著換一種寫法：$$(x+y)^n = \underbrace{(x+y)(x+y)(x+y)...(x+y)}_{n}$$
這時候有兩種想法可以將這個式子展開：
</font>

### 想法一：

<font size = 5>\
$x^n$項就是要從$n$個括弧中選出$n個x$，$0個y$，有$C_n^n = C_0^n$種方法，因此$x^n$項的係數就是$C_n^0$
$x^{n-1}y$項就是要從$n$個括弧中選出$n-1個x和1個y$，有$C_{n-1}^n = C_{1}^n$種方法，因此$x^{n-1}y$項的係數就是$C_{1}^n$
依此類推，$x^{n-k}y^k$項就是要從$n$個括弧中選出$n-k$個$x$和$k$個$y$，有$C_{n-k}^nC_k^k = C_{n-k}^n = C_{k}^n$種選法，因此$x^{n-k}y^k$項的係數就是$C_{k}^n$
故$$(x+y)^n = \sum_{k=0}^n C_{k}^n(x^{n-k}y^k)$$
</font>

### 想法二：

<font size = 5>\
有$n$個括號，每個括號可以提出$x$或$y$，則$x^{n-k}y^k$項就是拿$n-k$個$x$以及$k$個$y$進行排列，則有$\frac{n!}{(n-k)!k!}$種排列方式，每種排列方式代表一個$x^{n-k}y^k$，因此係數即為$C_k^n$
故$$(x+y)^n = \sum_{k=0}^n C_k^n(x^{n-k}y^k)$$

:::info
要證明二項式定理最直接的方式應該還是大家熟知的數學歸納法，但是既然都放在排列組合這裡講了，我就想說還是以排列組合的想法來推導應該比較有意義。
在打這篇的時候是段考前一週的晚自習了，教室依然空蕩蕩的，雖說馬上就要段考了，但大家似乎都不太在意，真是的，雖然我也是。順帶一提，最近很喜歡King Gnu的Ceremony這張專輯，我現在也在聽，尤其是Hakujitsu和Small Planet這兩首，會讓人不自覺地跟著點頭，大家有空可以去聽聽看！
2024/3/18
:::
</font>