combination · C(n, k) = P(n, k) / k!

组合 C(n, k)

仍是从 $n$ 个不同元素里取 $k$ 个，但这次不计次序， $\{A, B, C\}$ 与 $\{C, B, A\}$ 是同一个组合。这样的方案数记作组合数 $C(n, k)$ ，中文教材写作 $C_n^k$ ，也常写成二项式系数 $\binom{n}{k}$ 。它与排列只差一个因子：把排列里那 $k!$ 种「同一组元素的不同顺序」压成一种，就得到组合。

1 · 折叠掉 k 阶乘种顺序

C(n, k) = P(n, k) / k! = n! / (k!·(n−k)!)

同一组 $k$ 个元素能排成 $k!$ 种不同顺序，它们在排列里各算一个、在组合里只算一个。所以把排列数除以 $k!$ 即得组合数：

C(n, k) = \frac{P(n, k)}{k!} = \frac{n!}{k!\,(n-k)!}

图 1-1 · 取头

k

个字母作一组，列出它的全部

k!

种顺序，观察它们如何折叠成一个组合。

2 · 枚举与对称性

enumerate · C(n, k) = C(n, n−k)

无序取 $k$ 个的全部组合共 $C(n, k)$ 个。另有一条常用性质：选出 $k$ 个等价于丢掉 $n-k$ 个，每挑一个大小为 $k$ 的子集就唯一对应一个大小为 $n-k$ 的补集，于是 $C(n, k) = C(n, n-k)$ 。

图 2-1 · 无序取

k

个的全部组合。可拖动滑块，观察

C(n, k)

与

C(n, n-k)

始终相等。

两个常用的边界值： $C(n, 0) = C(n, n) = 1$ ，取空集或取全体各只有一种； $C(n, 1) = C(n, n-1) = n$ ，取一个或丢一个。把 $k$ 从 $0$ 拉到 $n$ ，组合数先增后减、关于中间对称，这正是 Pascal 三角每一行的形状。

3 · 参考文献

Combination. Wikipedia. 组合、二项式系数与常用恒等式。https://en.wikipedia.org/wiki/Combination
Binomial coefficient. Wikipedia. $C(n, k)$ 的多种写法、对称性与求和公式。https://en.wikipedia.org/wiki/Binomial_coefficient