组合

组合 (Combinations)

组合是组合数学中的基本计数概念，指从一个包含 $n$ 个不同元素的集合中，不考虑顺序地选取 $k$ 个元素的方式数，记作 $\binom{n}{k}$、$C(n,k)$ 或 $C_n^k$。它与排列的核心区别在于：排列关心元素的顺序，而组合只关心元素是否被选中。例如，从 $\{A,B,C\}$ 中选 2 个字母，组合认为 $\{A,B\}$ 与 $\{B,A\}$ 是同一结果，因此共有 $\binom{3}{2}=3$ 种组合，而非 $P(3,2)=6$ 种排列。

定义与基本公式

组合数的标准定义为：

其中 $n!$ 表示 $n$ 的阶乘。该公式的推导逻辑为：先从 $n$ 个元素中选出 $k$ 个并进行排列，共有 $n!/(n-k)!$ 种方式（即排列数 $P(n,k)$），再除以 $k!$ 以消除选出的 $k$ 个元素内部的顺序差异。规定 $\binom{n}{0} = \binom{n}{n} = 1$，且当 $k > n$ 或 $k < 0$ 时，$\binom{n}{k} = 0$。

组合数具有对称性：$\binom{n}{k} = \binom{n}{n-k}$。这一性质反映了"选出 $k$ 个元素"与"留下 $n-k$ 个元素"之间的等价关系。另一核心恒等式为帕斯卡恒等式：

该递推关系构成了帕斯卡三角形（杨辉三角）的基础，使得组合数可从较小的 $n$ 递推计算。组合数还与二项式定理紧密关联：$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$，因此组合数也常被称为二项式系数。

推广形式

当允许重复选取同一元素时，得到可重组合（multiset combinations），其计数公式为 $\binom{n+k-1}{k}$，等价于"将 $k$ 个不可区分的球放入 $n$ 个可区分的盒子"的星棒问题（stars and bars）。这一扩展在抽样分布和统计力学（如玻色-爱因斯坦统计中玻色子的状态计数）中均有直接应用。

将组合数推广到任意实数或复数上标，可定义广义二项式系数：

这是牛顿二项式级数 $(1+x)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k$（$|x|<1$）的系数，在无穷级数和负二项分布的概率质量函数中经常出现。

在概率论与统计学中的应用

组合数是古典概型的基石。若从 $n$ 个元素中等概率随机抽取 $k$ 个，每个特定的 $k$-组合被抽中的概率为 $1/\binom{n}{k}$。这一原理直接导出超几何分布的概率质量函数：

该分布描述的是从包含 $K$ 个"成功"元素的总体 $N$ 中不放回抽取 $n$ 个时，获得 $k$ 次成功的概率，广泛应用于抽样调查、质量控制和审计抽样。

二项分布的概率 $\binom{n}{k} p^k (1-p)^{n-k}$ 同样以组合数为骨架：$\binom{n}{k}$ 计数了在 $n$ 次独立伯努利试验中恰好获得 $k$ 次成功的位置选择方式。在贝叶斯统计中，组合数构成组合先验的基础，尤其在处理有限总体抽样问题时。此外，排列检验和精确检验（如Fisher精确检验）的 p 值计算也直接依赖组合枚举。

近似与计算

当 $n$ 很大时，直接按定义计算组合数面临数值溢出问题。斯特林公式 $n! \approx \sqrt{2\pi n}\,(n/e)^n$ 提供了渐近近似。对于固定的 $k$，有 $\binom{n}{k} \approx n^k/k!$。当 $n$ 很大且 $k \approx n/2$ 时，可以使用正态近似：$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{2(k-n/2)^2}{n}\right)$，这是中心极限定理在组合数上的体现。实际编程中，常使用递推或对数-指数变换（计算 $\ln\binom{n}{k} = \ln(n!) - \ln(k!) - \ln((n-k)!)$）来保持数值稳定性。