###### tags: `離散數學`

:::info
[回共筆首頁](https://hackmd.io/zrsmsRtEQ-OrnGslDxT0NQ)
[回科目首頁](https://hackmd.io/OwMjUy0fRq2kEuCRiMwtkQ)
:::
- [上課簡報](https://moodle2.ntust.edu.tw/pluginfile.php/229341/mod_resource/content/1/Chapter6_m.pdf)

[TOC]
# 6. Counting
## Product Rule
### Definition
如果要依序做兩個任務 $t_1,t_2$，而 $t_1$ 有 $n_1$ 種方法， $t_2$ 有 $n_2$ 種方法
那麼我們會有 $n_1\times n_2$ 種處理任務的方法

用在不會互相影響的方法上，像是 AND 的邏輯

### Example
電話號碼的每一位都是獨立的，但是有不同的限制
像是某些位置只能出現 0~9 或者是 2~9 甚至只有 0 跟 1
那我們就針對每一位可以出現的數字數量去相乘就好

### Term of Sets
對一些有限集合做 Cartesian product 後的元素個數
會等於每一個集合的元素個數相乘
$|A_1\times A_2\times\cdots\times A_m|=|A_1|\cdot|A_2|\cdot\;\cdots\;\cdot|A_m|$

## Sum Rule
如果要做一個任務，而要不透過 $n_1$ 種方法，或者是透過 $n_2$ 種方法
那麼我們總共會有 $n_1+n_2$ 種方法來完成這個任務

用在有選擇的時候(不是這個就是那個)，像是 OR 的邏輯

### Term of Sets
假設有兩個集合而他們是 disjoint 的
兩個集合做聯集(Union)後的數量
會等於兩個集合的元素個數相加
$|A\cup B|=|A|+|B|$

更廣泛的寫法：
$|A_1\cup A_2\cup\cdots\cup A_m|=|A_1|+|A_2|+\cdots+|A_m|$
$\text{when}\;A_i\cap A_j=\varnothing\;\text{for all}\;i,j$

## Subtraction Rule
排容原理

在介紹 Sum Rule 的時候有提到兩個集合必須要是 disjoint
而當兩個集合有重複的東西時，我們就需要把重複計算的扣掉
$|A\cup B|=|A|+|B|-|A\cap B|$

當兩個事件並不會互斥的時候，就需要用排容原理扣掉重複計算的東西

### Example
有一個長度為 8 的 bit string，開頭是 1 或者 00 結尾的 bit string 有多少個？

要計算下列幾種的方法數
- 開頭是 1 的 ($128$)
- 結尾是 00 的 ($64$)
- 開頭是 1，且結尾是 00 的 ($32$)

所以答案是 $128+64-32=160$

## Division Rule
### Definition
如果我們要排除重複的值，就要使用除法去除

### Example
常見例子：
1. 圓桌排列，因為繞成一個圓，所以用直線的方式去算的話會算到重複的
2. 當一個 array 裡面有元素是重複的
而我們想要去排序他，就會計算到重複的值
[來源](https://math.stackexchange.com/questions/1536479/how-to-explain-the-division-rule-in-counting-problem-in-a-easy-way)

## Pigeonhole Principle
鴿籠原理

如果有 $k + 1$ 隻鴿子，k 個籠子
把 $k + 1$ 隻鴿子都放進籠子裡面，就會有一個籠子裡有 $2$ 隻鴿子
因為籠子的個數比鴿子少，所以一定會有一個籠子有超過 $1$ 隻鴿子

### Corollary
我們可以利用鴿籠原理來證 function $f$ 是不是 one-to-one
假設有 $k+1$ 個元素的集合 $A$ 要對應到 $k$ 個元素的集合 $B$
而根據鴿籠原理，$B$ 至少會有一個元素被 $A$ 對應到不只一次
所以 $f$ 不能是 one-to-one

### Generalized Pigeonhole Principle
如果有 $N$ 個 object 要放到 $k$ 個箱子裡
則至少一個箱子會有 $\lceil\frac Nk\rceil$ 個 object

舉例來說，
有 $100$ 個人，至少會有 $9$ 人會在同一個月出生
因為 $\lceil\frac{100}{12}\rceil=9$
- 100 個人 -> 100 個 object
- 12 個月 -> 12 個箱子

舉一反三，
我們也可以逆著推回去
假設有一副撲克牌 ($52$ 張)
> 要抽出多少張牌，才可以確保出現三張同樣花色的牌？

我們只要想好誰是鴿子，誰是籠子就好了
- 籠子 -> 四個花色
- 鴿子 -> ？
- 一個籠子裡面至少要有多少鴿子 -> 三張同樣花色

根據剛剛的公式 $\lceil\frac N{4}\rceil\geq 3$
就可以算出來 $N$ 最小要是 $9$

> 要抽出多少張牌，才可以確保至少三張紅心被選到？

一種花色總共有 13 張，那如果我們選了 39 張(其他花色)，
假設最壞的情況發生，39 張都沒有出現紅心，
那麼只要再選 3 張，就一定能選到 3 張紅心。

## Permutations
排列

排列跟順序有關，不同順序會被當成兩個不一樣的情況
$P(n,r)$：總共有 $n$ 個，要排 $r$ 個

公式推導過程：
$P(n,r)=n(n-1)(n-2)\cdots(n-r+1)$ (選完 $r$ 個就停)

$P(n,r)=\frac{n!}{(n-r)!}$ (先全選，再把多選的除掉)

## Combinations
組合

組合跟順序無關，不同順序會被當成同一種情況
也就是說，組合在意的是**有沒有選到**
$C(n,r)=\binom nr$ (可以被表示成二項式係數)
$C(n,r)=\frac{n!}{(n-r)!r!}$

跟剛剛的排列比起來，下面多除了一個 $r!$
我們要去除重複的，因為順序不重要

## Binomial Theorem
二項式定理

給一個式子 $(x+y)^n$
在 $n$ 不同的情況下，我們想要去計算 $x$ 跟 $y$ 前面的係數是多少
公式：

我們可以想成總共有 $n$ 個選擇，
而對於第 $j$ 項，它可以選多少個 $x$ 跟多少個 $y$

舉例來說，第一項
選了 $n$ 個 $x$，選了 $0$ 個 $y$

### Corollary
當 $n\geq0$ 時

$\sum_{k=0}^n\binom nk=2^n$

看起來是很酷的性質，但其實不難理解
我們可以把剛剛的 $x$ 跟 $y$ 都帶 $1$ 進去
就會變成 $(1+1)^n=2^n$

### Pascal’s Identity
當 $n$ 跟 $k$ 是整數的時候
且 $n\geq k\geq 0$
則 $\binom{n+1}k=\binom n{k-1}+\binom nk$

我們可以利用集合內的元素個數來想
一個集合 $S$ 裡面有 $n$ 個元素
而另一個集合 $T=S$ 想要新增一個 $a$ 元素進去

所以 $T$ 會有 $\binom{n+1}k$ 個擁有 $k$ 個元素的 subset
而這些 subset 由兩種情況組成
- 選了 $a$，且有其他 $k-1$ 個元素
- 不選 $a$，只有其他 $k$ 個元素

酷酷的帕斯卡三角形
當前這項可以用簡單的加法從上一層推出來
不用做繁瑣的階乘運算