組合數學/集合的子集 - 二項式係數

現在我們嘗試計算給定集合的子集個數。如果一個集合包含n個元素，我們就稱之為n階集合。

我們將要證明的第一個結果涉及給定n階集合的子集總數。我們斷言它等於$2^{n}$。為了證明這一點，首先取一個包含n個元素的集合X及其子集Y。現在考慮以下函式

$f_{Y}(n)={\begin{cases}1,\ n\in Y\\0,\ n\notin Y\end{cases}}$

這樣的函式被稱為指示函式。如果$X=\{0,1\cdots n-1\}$，那麼我們可以用n元組$(f(0),f(1)\cdots f(n-1))$來表示上述函式。這個n元組可以充分描述Y。透過觀察n元組，可以很容易地推斷出Y，對應於1的位置是其成員。反之，給定Y，我們總是可以構造出這個n元組。因此，每個子集恰好對應一個n元組。

現在把這個n元組看成一個二進位制整數

$N=f(n-1)2^{n-1}+f(n-2)2^{n-2}\cdots f(1)2+f(0)$.

每個n元組對應於一個唯一的整數（因為每個n元組的係數都是唯一的），因此對應於X的一個唯一的子集。最小的，即0，對應於全為零的n元組，它又對應於空集；最大的，即$2^{n-1}+2^{n-2}\cdots 2+1=2^{n}-1$，對應於全為一的n元組，它又對應於X。在0和$2^{n-1}$之間（包括0和$2^{n-1}$）存在$2^{n}$個這樣的整數，因此X的子集總數為$2^{n}$。

現在讓我們把注意力轉向二項式係數。給定一個非負整數n和一個整數k，二項式係數定義為自然數

${n \choose k}={\frac {n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1}}={\frac {n!}{k!(n-k)!}}\quad {\mbox{if}}\ 0\leq k\leq n\qquad (1)$

並且

${n \choose k}=0\quad {\mbox{if }}k<0{\mbox{ or }}k>n$

其中n!表示n的階乘。

${n \choose k}$ 讀作 “n 選 k”。

關於二項式係數最重要的結果如下：

定理：令 X 為一個 n 階集合。那麼它的 k 階子集的數量是 ${n \choose k}$

證明：令 $X=\{1,2\cdots n\}$。這些數字可以以各種順序排列，稱為排列。有 n! 種排列，因為第一項可以是 n 個數字中的任何一個，第二項可以是剩下的 n-1 個數字中的任何一個，依此類推。

現在讓我們用不同的方式計算這些排列。然後我們將應用上一章中描述的雙重計數。

令 Y 是 X 的一個有 k 個元素的子集。那麼 Y 的元素有 k! 種排列。類似地，不在 Y 中的元素有 (n-k)! 種排列。如果我們將 (n-k)! 中的任何一種排列附加到 k! 中的任何一種排列的右側，那麼由此得到的 n 個元素的順序序列就是 X 的排列之一。要獲得 X 的所有排列，我們用 Y 替換每個 k 階子集，重複此過程。因此，可能的總排列數將是 T.k!(n-k)!，其中 T 是 k 階子集的數量。那是因為總排列數 = 將 k!(n-k)! 加上等於 k 階子集數量的次數 = T.k!(n-k)!。現在這個數字必須等於 n!，所以我們有 T = X 的 k 階子集的數量 = ${\frac {n!}{k!(n-k)!}}={n \choose k}$。證畢。

上面的證明保證 ${n \choose k}$ 是一個自然數，因為它的簡單原因是它代表從 n 階子集中選擇 k 階子集的方法數量。通常，當我們有 n 種選擇，並且必須選擇 k 種時，我們宣告進行此操作的方法數量是 ${n \choose k}$。在那一刻，我們實際上是在 n 階集的選擇和元素之間建立平行關係。

如果我們沒有在這裡寫下關於帕斯卡三角形的註釋，那麼這裡討論將是不完整的。

帕斯卡定律是重要的關係

${n \choose k}+{n \choose k+1}={n+1 \choose k+1},\qquad (3)$

它直接來自定義

${\begin{aligned}{n \choose k}+{n \choose k+1}&{}={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k+1)!(n-(k+1))!}}\\&{}=\left({\frac {n!(k+1)}{k!(n-k)!(k+1)}}+{\frac {n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}}\right)\\&{}=\left({\frac {n!(k+1+n-k)}{(k+1)!(n-k)!}}\right)\\&{}={\frac {(n+1)!}{(k+1)!((n+1)-(k+1))!}}\\&{}={n+1 \choose k+1}\end{aligned}}$

帕斯卡法則導致了帕斯卡三角形

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

第n行包含數字C(n, k)，其中k = 0,…,n。它的構造方法是從外部開始用 1，然後始終將兩個相鄰的數字相加並將和直接寫到下方。這種方法可以快速計算二項式係數，而不需要分數或乘法。例如，透過檢視三角形的第 5 行，可以快速讀出 ${5 \choose 0}=1,\ {5 \choose 1}=5\ {5 \choose 2}=10$ 等等。這是因為上面證明的帕斯卡關係。

其他對角線上元素之間的差值是前一個對角線上的元素，這是上面帕斯卡關係的結果。