第 04 篇、排列組合 & 排容原理

高中就已有上過，這份筆記相對輕量👍👍

# 基本計數原理

• 乘法原理: 獨立且連續事件: $m \times n$
• 加法原理: 互斥事件: $m+n$

# 排列

# 常見公式

1. $n$ 件相異物，取$r$ 件物品排列 (不重複排列)$\Rightarrow \frac{n!}{(n-r)!} = P^n_r$
2. $n$ 件相異物，取$r$ 件物品排列 (允許重複排列)$\Rightarrow n^r$
3. $n$ 件相異物，全排列$\Rightarrow n!$
4. $n$ 件相異物，環狀排列$\Rightarrow \frac{n!}{n} = (n-1)!$
5. $n$ 件不全相異的物品，共有$r$ 種，第一種有$n_1$ 個，第二種有$n_2$ 個，...，第$r$ 種有$n_r$ 個，
   全排列$\Rightarrow \frac{n!}{n_1!n_2!...n_r!}$

# 組合

# 常見公式

1. $n$ 件相異物，取$r$ 件物品組合 (不允許重複)$\Rightarrow \frac{P^n_r}{r!} = \frac{n!}{(n-r)!r!} = C^n_r = \binom{n}{r}$
2. $n$ 件相異物，取$r$ 件物品組合 (允許重複)$\Rightarrow \binom{n+r-1}{r} = H^n_r$
3. $x_1 + x_2 +...+x_n=r$ 之正整數解$\Rightarrow \binom{r-1}{n-1}$

# 巴斯卡三角形

$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$

# 二項式定理

$(x+y)^n = \sum_{r=0}^{n}\binom{n}{r}x^ry^{n-r}$

# 系理

$(x_1+x_2+...+x_k)^n = \sum\binom{n}{n_1,n_2,...,n_k}x_1^{n_1}x_2^{n_2}...x_k^{n_k}$

# 排容原理

$N(\overline{a_1}\overline{a_2}...\overline{a_n}) = |U| - \sum_{i=1}^nN(a_i)+\sum_{1\ge i \ge j \ge n}^nN(a_ia_j) - \sum_{1\ge i \ge j \ge k \ge n}^nN(a_ia_ja_k)...(-1)^nN(a_1...a_n) = S_0-S_1+S_2...(-1)^nS_n$，其中$S_r$ 含有$\binom{n}{r}$項之和

# 定理

$|A| = m,|B|=n, m\ge n$
$A$ 至$B$ 的 onto 函數各數為$onto(m,n) = \sum^n_{i=0}(-1)^i\binom{n}{i}(n-i)^m$
= $m$ 個相異物放在$n$ 個相異箱子，不允許空箱的方法數 (分析誰為空箱)

# 定理

$S(m+1,n) = S(m,n-1) + nS(m,n)$