# 數學（二）
---
# 單元三：排列組合與機率
## 3-3 組合

---

### 主題一 組合(Combination)

#### 1. 組合：

(1) 在挑出 $k$ 個物品時不考慮取出的順序稱為**組合**，也可說這 $k$ 個物品取出的 $k!$ 種排列順序調換後，都只視為同一種組合。

(2) 用 $C_k^n$ 表示從 $n$ 個不同的物品中，挑出 $k$ 個不同物品的組合數（其中 $0 \le k \le n$）。
>也可記為$C(n,k)$，
>**(Combination of n choose k, or n choose k)**
>**The number of ways to choose 𝑘 distinct objects from 𝑛 distinct objects.**
>
(3) 組合公式：
$$C_k^n = \frac{P_k^n}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$$

#### 2. $C_k^n$ 的性質：

(1) $C_0^n = 1$, $C_n^n = 1$。
(2) $C_k^n = C_{n-k}^n$（其中 $0 \le k \le n$）。

#### 證明：

(1) $C_0^n = \frac{n!}{0!(n-0)!} = \frac{n!}{1 \cdot n!} = 1$。

$C_n^n = \frac{n!}{n!(n-n)!} = \frac{n!}{n! \cdot 0!} = 1$。

> **$\langle$另解$\rangle$**
>
> $C_0^n$ 表示從 $n$ 個不同物品中挑 $0$ 個的方法數，故有 $1$ 種方法。
>
> $C_n^n$ 表示從 $n$ 個不同物品中挑 $n$ 個的方法數，故有 $1$ 種方法。

(2) $C_{n-k}^n = \frac{n!}{(n-k)! [n-(n-k)]!} = \frac{n!}{(n-k)! k!} = C_k^n$。

> **$\langle$另解$\rangle$**
>
> $C_k^n$ 的意思是從 $n$ 個物品中挑 $k$ 個的方法數，這相當於挑 $(n-k)$ 個不要的方法數，因此 $C_k^n = C_{n-k}^n$。

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

---
### 主題二：二項式定理（Binomial Theorem）

#### 1. 將 $(x+y)$ 的任何冪次方展開成和的形式，稱為**二項式定理**。

#### 2. 若 $n$ 為非負整數，
$$(x+y)^n = C_0^n x^n y^0 + C_1^n x^{n-1} y^1 + \cdots + C_k^n x^{n-k} y^k + \cdots + C_n^n x^0 y^n$$
>**(x+y) to the nth power,(x+y) to the power of n**

>其中一般項為 $C_k^n x^{n-k} y^k$, $k=0, 1, 2, \cdots, n$， $C_k^n$ 稱為**二項式係數**。
>**(The binomial coefficient)**

>#### 說明：先觀察 $(x+y)^2$ 與 $(x+y)^3$ 的展開
>* **$(x+y)^2$ 的展開：**
$$(x+y)^2 = (x+y)(x+y) = \underline{xx} + \underline{xy} + \underline{yx} + \underline{yy}$$
$$= x^2 + 2xy + y^2$$

>* **$(x+y)^3$ 的展開：**
$$(x+y)^3 = (x+y)(x+y)(x+y) = \underline{xxx} + \underline{xxy} + \underline{xyx} + \underline{yxx} + \underline{xyy} + \underline{yxy} + \underline{yyx} + \underline{yyy}$$
$$= x^3 + 3x^2y + 3xy^2 + y^3$$

>觀察可得每一項的係數與對應個數的 $x$ 與 $y$ 的排列數相等，例如 $x^2y^1$ 項的係數為 $2$ 個 “$x$” 與 $1$ 個 “$y$” 的排列數。

>以此類推，可得 $(x+y)^n$ 中 $x^{n-k} y^k$ 項的係數等於 $n$ 個 “$x$” 與 $k$ 個 “$y$” 的排列數，即
$$\frac{n!}{[n-(n-k)]! k!} = C_k^n$$
因此
$$(x+y)^n = C_n^n x^n y^0 + C_{n-1}^n x^{n-1} y^1 + \cdots + C_{n-k}^n x^{n-k} y^k + \cdots + C_0^n x^0 y^n$$

#### 3. $C_k^n$ 性質的應用：

(1) 利用 $C_k^n = C_{n-k}^n$，可得：
$$(x+y)^n = C_0^n x^n y^0 + C_1^n x^{n-1} y^1 + \cdots + C_k^n x^{n-k} y^k + \cdots + C_n^n x^0 y^n$$
$$= C_n^n x^n y^0 + C_{n-1}^n x^{n-1} y^1 + \cdots + C_{n-k}^n x^{n-k} y^k + \cdots + C_0^n x^0 y^n$$

(2) 二項式定理中的 $x, y$ 可以替換為其他變數或式子。

#### 4.常用公式：
(1)$$ 2^n=(1+1)^n = C^n_0 + C^n_1 + C^n_2 + \cdots + C^n_n $$

(2)$$(1+x)^n = C^n_0 x^0 + C^n_1 x^1 + C^n_2 x^2 + \cdots + C^n_n x^n$$

例一： $$C^{10}_0 + C^{10}_1 + C^{10}_2 + \cdots + C^{10}_{10}=2^{10}$$

例二：$$ C^n_0 \times (\frac{1}{3})^0+C^n_1 \times (\frac{1}{3})^1+C^n_2 \times (\frac{1}{3})^2+\cdots+C^n_n \times (\frac{1}{3})^n=(1+\frac{1}{3})^n$$

</br>
</br>
</br>
</br>

</br>
</br>
</br>
</br>

---
### 主題三 巴斯卡三角形（Pascal's Triangle）

#### 1. 由二項式定理 $(x+y)^n$，其中 $n=0, 1, 2, 3, \cdots$，並將係數排列成如下三角形：

| 數字表示 | 組合數表示 | $n$ |
| :---: | :---: | :---: |
| | $C_0^0$ | $n=0$ |
| 1 1 | $C_0^1$ $C_1^1$ | $n=1$ |
| 1 2 1 | $C_0^2$ $C_1^2$ $C_2^2$ | $n=2$ |
| 1 3 3 1 | $C_0^3$ $C_1^3$ $C_2^3$ $C_3^3$ | $n=3$ |
| 1 4 6 4 1 | $C_0^4$ $C_1^4$ **$C_2^4$** $C_3^4$ $C_4^4$ | $n=4$ |
| 1 5 10 10 5 1 | $C_0^5$ $C_1^5$ $C_2^5$ $C_3^5$ $C_4^5$ $C_5^5$ | $n=5$ |
| 1 6 15 20 15 6 1 | $C_0^6$ $C_1^6$ $C_2^6$ $C_3^6$ $C_4^6$ $C_5^6$ $C_6^6$ | $n=6$ |

這稱為**巴斯卡三角形**（或**楊輝三角形**）。

#### 2. 性質：

(1) 數字呈現左右對稱，且兩端的數都是 $1$。這是因為 $C_k^n = C_{n-k}^n$，且 $C_0^n = C_n^n = 1$。

(2) 每個數等於其左上的數與右上數的和，即
$$C_k^n = C_k^{n-1} + C_{k-1}^{n-1} \quad (1 \le k \le n-1)$$
此式稱為**巴斯卡公式/巴斯卡恆等式/巴斯卡定則**
（Pascal's Formula/Pascal's Identity/ Pascal's Rule）。

>證明：計算在 $1, 2, \cdots, n$ 之中取出 $k$ 個相異數字的組合有幾種方法。考慮以下兩種算法：
>**(1) 顯然答案為 $C_k^n$ 種方法。**
>**(2) 按照 “$n$” 是否被選到分成兩類：**
>
> **① 若 “$n$” 被選到**，則還要從 $1, 2, \cdots, n-1$ 之中選出 $k-1$ 個，有 $C_{k-1}^{n-1}$ 種方法。
>
> **② 若 “$n$” 未被選到**，則還要從 $1, 2, \cdots, n-1$ 之中選出 $k$ 個，有 $C_k^{n-1}$ 種方法。
>
>因此，一共是 $C_{k-1}^{n-1} + C_k^{n-1}$ 種方法。
>
>由於 **①**、**②** 都是算同一個問題，答案必須一樣，所以 $C_k^n = C_k^{n-1} + C_{k-1}^{n-1}$。

</br>
</br>
</br>
</br>