组合数学/集合的子集 - 二项式系数

现在我们尝试计算给定集合的子集个数。如果一个集合包含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$ 等等。这是因为上面证明的帕斯卡关系。

其他对角线上元素之间的差值是前一个对角线上的元素，这是上面帕斯卡关系的结果。