U43 排列與組合 (P&C) 必考公式

乘法原理 (Multiplication Principle)

若完成一件事需要 $k$ 個步驟，而完成第 $1$ 步有 $n_1$ 種方法，完成第 $2$ 步有 $n_2$ 種方法，...，完成第 $k$ 步有 $n_k$ 種方法，且各步驟的方法選擇彼此獨立，則完成整件事共有 $n_1 \times n_2 \times \dots \times n_k$ 種方法。

加法原理 (Addition Principle)

若完成一件事有 $k$ 類互斥（即不能同時發生）的方法，而第 $1$ 類有 $m_1$ 種方法，第 $2$ 類有 $m_2$ 種方法，...，第 $k$ 類有 $m_k$ 種方法，則完成整件事共有 $m_1 + m_2 + \dots + m_k$ 種方法。

無重排列 (Permutation of Distinct Objects)

從 $n$ 件不同的物件中，選取 $r$ 件出來排列（考慮次序）。記作 $P_r^n$ 或 $_nP_r$。

特別地，當 $r = n$，即全排列，公式為 $P_n^n = n!$。

有重排列 (Permutation with Repetition)

若有 $n$ 件物件，其中第一類有 $a_1$ 件相同，第二類有 $a_2$ 件相同，...，第 $k$ 類有 $a_k$ 件相同，且 $a_1 + a_2 + \dots + a_k = n$，則這 $n$ 件物件的所有排列數目為：

圓形排列 (Circular Permutation)

將 $n$ 件不同的物件圍成一個圓圈的排列數目。由於旋轉後視為相同排列，因此數目為：

無重組合 (Combination of Distinct Objects)

從 $n$ 件不同的物件中，選取 $r$ 件出來，不考慮次序。記作 $C_r^n$ 或 $_nC_r$ 或 $\binom{n}{r}$。

重要性質：$C_r^n = C_{n-r}^n$，且 $C_0^n = C_n^n = 1$。

組合恆等式 (Combination Identities)

帕斯卡恆等式 (Pascal's Identity)：$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$，其中 $1 \le r \le n-1$。

二項式定理 (Binomial Theorem)：$(a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^{r}$。

區分排列與組合

關鍵在於「次序是否重要」。例如，選出一個主席和一個副主席是排列問題（$P_2^n$），因為職位不同；選出兩名代表則是組合問題（$C_2^n$），因為兩者角色相同。

「至少」或「至多」問題

常用補集法（complementary counting）或分類加法原理。例如，「從 $10$ 人中至少選 $3$ 人」的方法數為 $C_3^{10} + C_4^{10} + \dots + C_{10}^{10}$，或等於總數減去選 $0, 1, 2$ 人的情況：$2^{10} - (C_0^{10}+C_1^{10}+C_2^{10})$。

分配與分組問題

若將 $n$ 件不同的物件分成 $k$ 組，每組數量分別為 $n_1, n_2, \dots, n_k$（$\sum n_i = n$），且組別本身沒有標籤（即組與組之間沒有次序），則分法數目為 $\frac{n!}{n_1! n_2! \dots n_k!}$。若組別有標籤（例如分給不同的人），則需再乘以 $k!$。