# Chapter6 - 計數 Counting

## 計數基礎
* 基本原則 : 假設任務一的解決方法有 $m$ 種；任務二的解決方法有 $n$ 種
* 加法原則 : 解決任務一**或**任務二的方法有 $m+n$ 種
* 乘法原則 : 解決任務一**和**任務二的方法有 $m \times n$ 種
* 例題 : 從一個包含 $m$ 個元素的集合到一個包含 $n$ 個元素的集合，有多少個一對一函數？
$Ans: n(n-1)(n-2) \ldots (n-m+1)$ 當 $n>m$ 時
* 例題 : 每個電腦系統者都可設定一組由小寫字母和數字所組成的六位或八位密碼，每組密碼至少要有一個數字，請問密碼有幾種可能?
$Ans: P = P_6 + P_7 + P_8 = (36^6-26^6) + (36^7-26^7) + (36^8-26^8)$

* 排容原理
* $|A \cup B| = |A| + |B| - |A \cap B|$
* $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$
* 例題 : 一個電腦公司收到350個碩士的履歷表來應徵工作。假定其中有220個主修電腦科學；147個主修商業管理；而有51個人雙主修電腦科學與商管。有多少應徵者的主修既非電腦科學也非商業管理？
$Ans:$
令 $A$ 為主修電腦科學； $B$ 為主修商業管理
$|A \cup B| = |A| + |B| - |A \cap B| = 220 + 147 - 51 = 316$

* 樹狀圖
* 可能的結果用葉節點代表
* 例題 : 請用樹狀圖定義{3, 7, 9, 11, 24} 的子集合，滿足以下條件：子集元素總和小於 28
$Ans(1):$

$Ans(2):$

## 鴿洞定理 The Pigeonhole Principle
> 假設有13鴿子要飛入12個鴿洞裡棲息，則12鴿鴿洞裡至少有一個鴿洞內住著兩隻鴿子
> | :bird: | :bird: | :bird: | :bird: | | **分** | | :bird: | **null** | :bird::black_bird: | :bird: |
> |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
> | :bird: | :bird: | :bird: | :bird: | | **界** | | :bird: | :bird::black_bird: | :bird: | :bird: |
> | :bird: | :bird: | :bird: | :bird::black_bird: | | **線** | | :bird: | :bird: | :bird: | **null** |

* 鴿洞原理(鴿籠原理)
* 如果將 $≥k+1$ 個物體分配到 $k$ 個盒子中，則至少有 $1$ 個盒子必須分配 $≥2$ 個物體，例:
* 在367個人中，一定會有兩個人同一天生日，因為一年最多只有366天
* 在27個英文單字中，至少有兩個單字以同一個字母開頭， 因為英文字母只有26個字母

* 例題 : 證明每個正整數 $n$ 都存在 $n$ 的倍數，使得其十進制只包含0和1

$Ans:$ 令 $n$ 為一正整數，考慮 $n+1$ 個整數 $1, \ 11, \ 111, \ldots, \ 1111 \cdots 1$ (最後一個是有 $n+1$ 個1的整數)。把一個整數除以 $n$ 時，可能的餘數有 $n$ 個，而這裡有 $n-1$ 個整數，由鴿洞原理可知，必有兩個整數除以 $n$ 時會有相同的餘數。這兩個整數的差都是由0和1所組成，且能被 $n$ 整除

* 廣義鴿洞定理 : 如果將 $N$ 個物件分配到 $k$ 個位置，那麼至少有一個位置必定會被分配到至少 $\left \lceil \frac{N}{K} \right \rceil$ 個物件。例 : 課堂上有280位學生，一年有52週，因此至少有一週，至少有 $\left \lceil \frac{280}{52} \right \rceil = \left \lceil 5.38 \right \rceil = 6$ 位學生生日 ($N=280, \ k=52$)

* 一些優雅的應用 : 一個籃球隊每天至少比賽一次，但一個月(30天)不超過45次。證明必然存在某個連續天數，使得這支球隊在這段時間內正好打14場比賽。

$Ans:$
* 令 $a_j$ 為在這個月第 $j$ 天前的比賽次數，因此 $a_1, a_2, \cdots, a_{30}$ 是一個不同整數的遞增序列，且 $1 \leq a_j \leq 45$，所以 $a_1+14, a_2+14, \cdots , a_{30}$ 也是一個不同整數的遞增序列，且$15 \leq a_j+14 \leq 59$。
* 這樣有60個正整數 $a_1, a_2, \cdots a_{30}, a_1+14, a_2+14, \cdots , a_{30}+14$ 全部都小於59，根據鴿洞定理，至少有兩個數字會相同。由於 $a_j$ 和 $a_j+14$ 兩組數字完全不同，因此必定有一 $i$ 和 $j$ 使 $a_i=a_j+14$ 成立，這代表這14場比賽從第 $j+1$ 天開始持續到 第 $i$ 天結束

* 拉姆齊定理 Ramsey theory
* 拉姆齊數 $R(m,n)$ : 聚會中至少要有 $m$ 個共同朋友或 $n$ 個共同敵人，則該聚會最少有多少人
* 例題 : 假設有六個人，每兩個人會組成一對朋友或一對敵人。證明這群人中，不是有三組朋友，就是有三組敵人

$Ans:$
令 $A$ 為其中一人，而在其他五人中，總有三個以上的人和 $A$ 是朋友或敵人。根據鴿洞定理，五個物件被放到兩個集合中，則其中一個集合內至少含有 $\left \lceil \frac{5}{2} \right \rceil = 3$ 個物件。在這個例子中，假設 $B$、$C$、$D$ 是 $A$ 的朋友，或者 $B$、$C$、$D$ 是 $A$ 的敵人。在後一種情況下，即 $A$ 有三個或更多敵人時，證明過程類似。

## 排列組合
* $P^n_r = \frac{n!}{(n-r)!}$
* 定義 : 從 $n$ 個相異物中取出 $r$ 個，並且講究順序
* 例題 : 從100名參賽者中，可能產生的第1、2、3名的組合有幾種?
$Ans: P^{100}_3 = 100 \times 99 \times 98 = 97200$(種)

* $C^n_r = \frac{P^n_r}{P^r_r} = \frac{n!}{r!(n-r)!}$
* 定義 : 從 $n$ 個相異物中取出 $r$ 個，但是不講究順序
* 例題 : 一個含有10位球員的網球隊要挑出5位成員參賽，有幾種挑出的方式?
$Ans: C^{10}_5 = \frac{10!}{5! \times 5!} = 252$(種)

## 二項式定理
$$
\begin{align*}
(x+y)^n & = (x+y)(x+y)\dots(x+y) \\
& = \sum_{j=0}^n C_j^n x^{n-j}y^j \\
& = C_0^nx^n + C_1^nx^{n-1}y + C_2^nx^{n-2}y^2+\cdots+C_{n-1}^nxy^{n-1} + C_n^ny^n
\end{align*}
$$
> 例 : $$
>\begin{align*}
>(x+y)^4 & = \sum_{j=0}^4 C_j^4 x^{4-j}y^j \\
>& = C^4_0x^4+C^4_1x^3y+C^4_2x^2y^2+C^4_3xy^3+C^4_4y^4 \\
>& = x^4+ 4x^3y+6x^2y^2+4xy^3+y^4
>\end{align*}
>$$

* 帕斯卡三角形 Pascal's triangle : $C^{n+1}_k = C^n_{k-1}+C^n_k$

> 由 perplexity.ai 創作

## 廣義排列組合
* 常出現的關鍵字
1. 重複排列 Permutations with Repetition
2. 重複組合 Combinations with Repetition
3. 不可區分件的排列 Permutations with Indistinguishable Objects
4. 將物件分配至箱子中 Distributing Objects into Boxes

* 定理 :
1. 允許重複的 $n$ 個物件的 $r$ 排列數為 $n^r$
2. 當元素重複時，從包含 $n$ 個元素的集合中找出 $r$ 個組合的數量為 $C^{n+r-1}_r = C^{n+r-1}_{n-1}$
3. 當 $n_k$ 個類型有 $k$ 個不可區分的對象，其中 $k = \frac{n!}{n_1!n_2!\cdots n_k}$
4. 將 $n$ 個不同的物件放入 $k$ 個不同箱子的方法數，其中第 $i$ 個箱子放 $n_i$ 個物件，其中 $n_i = \frac{n!}{n_1!n_2!\cdots n_k}$