排列組合初步

04-01

0. 首先要知道……

本文常用符號：

1. 求和符號： $sum$ ，例如 $sum_{i=1}^n i^2$ 表示從 $1^2$ 一直累加到 $n^2$ ，即 $1^2+2^2+..+(n-1)^2+n^2$ 。

2. 求積符號： $prod$ ，例如 $prod_{i=1}^n i^2$ 表示從 $1^2$ 一直累乘到 $n^2$ ，即 $1^2*2^2*..*(n-1)^2*n^2$ 。

3. 階乘符號： $!$ ，例如 $n!$ 表示 $1*2*..*(n-1)*n$ ，特殊地，我們規定 $0!=1$ 。

1. 加法原理

若完成事件 $A$ 有 $n$ 類不同的方式，第 $i$ 種方式有 $m_i$ 種不同的方法，則完成該事件總共有 $sum_{i=1}^{n} m_i$ 種不同的方法。

2. 乘法原理

若完成事件 $A$ 有 $n$ 個步驟，第 $i$ 個步驟有 $m_i$ 種不同的方法，則完成該事件有 $prod_{i=1}^{n} m_i$ 種不同的方法。

3. 排列

排列是什麼？

從 $n$ 個不同元素中取出 $m$ 個元素按照一定順序排成一列，稱為其排列。從 $n$ 個不同元素中取出 $m$ 個元素的所有不同排列種數，記為 $A_n^m$ 。

排列數公式為：

$A_n^m=frac{n!}{(n-m)!}$

如何證明？

選擇第一個元素時有 $n$ 種不同情況，選擇第二個元素時有 $n-1$ 種不同情況，以此類推，選擇第 $m$ 個元素時有 $n-m+1$ 種不同情況。根據乘法原理可得，總共有 $prod_{i=0}^{m-1} n-i$ 種不同情況，即 $frac{n!}{(n-m)!}$ 種不同情況。

特殊情形

當 $n=m$ 時出現了特殊情形，即 $n$ 個不同元素取出全部元素的排列。我們稱之為全排列。全排列的排列數公式為：

$A_n^n=n!$

同樣可以用上述方法證明。

4. 組合

組合是什麼？

從 $n$ 個不同元素中取出 $m$ 個元素組成一組，稱為其組合。從 $n$ 個不同元素中取出 $m$ 個元素的所有不同組合種數，記為 $C_n^m$ 。

組合數公式為：

$C_n^m=frac{n!}{m!(n-m)!}$

如何證明？

利用剛剛的排列數公式，首先從 $n$ 個不同元素中取出 $m$ 個元素，不同順序視為不同情況。對於組合，不同順序視為同一情況，如何去除順序的影響呢？對於元素相同的排列，按順序編號，可以得到一個有 $m$ 個元素的全排列。即使元素不斷交換位置，所有可能的排列的種數都是有限的，即 $m$ 個元素的全排列數。

那麼，我們只需要用排列數除以 $m$ 個元素的全排列數，就可以得到組合數了。即：

$C_n^m=frac{A_n^m}{A_m^m}=frac{frac{n!}{(n-m)!}}{m!}=frac{n!}{m!(n-m)!}$

一個特殊的性質

不妨觀察組合數公式，可以發現：

$C_n^m=C_n^{n-m}$

其中，等式左側展開為 $C_n^m=frac{n!}{m!(n-m)!}$ ，等式右側展開為 $C_n^{n-m}=frac{n!}{(n-m)![n-(n-m)]!}=frac{n!}{(n-m)!(n-n+m)!}=frac{n!}{m!(n-m)!}$ 。

另一個特殊的性質

$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$

證明：

$egin{align}C_{n-1}^{m-1}+C_{n-1}^{m}&=frac{(n-1)!}{(m-1)![n-1-(m-1)]!}+frac{(n-1)!}{m!(n-1-m)!}\&=frac{(n-1)!}{(m-1)!(n-m)!}+frac{(n-1)!}{m!(n-m-1)!}\&=frac{m(n-1)!}{m!(n-m)!}+frac{(n-m)(n-1)!}{m!(n-m)!}\&=frac{(m+n-m)(n-1)!}{m!(n-m)!}\&=frac{n!}{m!(n-m)!}\&=C_n^mend{align}$

楊輝三角？

不妨設楊輝三角第 $i$ 行，第 $j$ 列表示為 $Delta_i^j$ ，行列皆從 $0$ 開始編號。邊界條件為 $Delta_x^0=1(xge 0)$ 。楊輝三角每個位置的值等於其上方兩個值之和，那麼遞推公式為 $Delta_i^j=Delta_{i-1}^{j-1}+Delta_{i-1}^{j}$ 。

再觀察剛剛的性質 $C_i^j=C_{i-1}^{j-1}+C_{i-1}^j$ ，可以發現兩條式子是一樣的。對於邊界條件，二者也是一樣的，所以 $Delta_i^j=C_i^j$ 。

二項式定理？

二項式定理公式：

$(a+b)^n=sum_{i=0}^n C_n^i a^{n-i}b^i$

那麼問題來了， $(a+b)^n$ 的展開與組合數有什麼關係呢？不妨寫成另一種形式： $(a+b)(a+b)..(a+b)$ （ $n$ 個 $(a+b)$ 相乘），從每個 $(a+b)$ 中選取一個 $a$ 或一個 $b$ 相乘，總共有多少種可能使得選取的 $a$ 與 $b$ 相乘得到 $a^{n-i}b^i$ 呢？

可以發現，從 $n$ 個 $(a+b)$ 中選取 $i$ 個 $b$ ，剩下的選取 $a$ 肯定是合法的。問題便轉化成了求從 $n$ 個 $(a+b)$ 中選取 $i$ 個 $b$ 所有組合種數，即 $C_n^i$ 。當然，從選取 $a$ 的角度出發可以得到另一個答案 $C_n^{n-i}$ ，還記得之前的特殊性質嗎？ $C_n^i=C_n^{n-i}$ 。