组合
zǔ hé
组合是从一组物体中选取若干个、且不考虑顺序的选取方式。
Formula
C(n, r) = \dfrac{n!}{r!(n-r)!}
Definition
组合是从一组事物中选取若干个而不考虑顺序的方式；它计算有多少种不同的选取方式。从 $n$ 个物品中取 $r$ 个的组合是一种无序选取：$C(n,r) = n!/(r!(n-r)!)$，也写作"$n$ 选 $r$"；由于顺序不重要，$C(n,r) = P(n,r)/r!$，除以 $r!$ 是为了消除同一组 $r$ 个物品的重复排序。形式上，二项式系数 $C(n,r)$ 计算一个 $n$ 元集合中 $r$ 元子集的数量；帕斯卡恒等式 $C(n,r) = C(n-1,r-1)+C(n-1,r)$ 递归生成帕斯卡三角，二项式定理指出 $(x+y)^n = \sum_{r=0}^{n} C(n,r)x^r y^{n-r}$。
Example
从 $5$ 名学生中选 $2$ 名组成委员会，有多少种方式？$C(5,2) = 10$，因为选择 Alice 和 Bob 与选择 Bob 和 Alice 是一样的。一场需要从 $1$-$49$ 中选出 $6$ 个数字的彩票有 $C(49,6) = 13{,}983{,}816$ 种可能的组合，每张彩票都是一种组合，无论选取顺序如何。在二项分布 $B(n,p)$ 中，恰好 $r$ 次成功的概率是 $C(n,r)p^r(1-p)^{n-r}$，其中 $C(n,r)$ 计算了在 $n$ 次试验中排列 $r$ 次成功和 $(n-r)$ 次失败的方式数。
Key Insight
当顺序不重要时使用组合：选择披萨配料就是一种组合，因为意大利辣香肠加蘑菇和蘑菇加意大利辣香肠是一样的，而且 $C(n,r) = C(n,n-r)$，选择包含 $r$ 个物品和选择排除 $n-r$ 个物品的计数相同，这一对称性意味着 $C(10,3) = C(10,7) = 120$。范德蒙德恒等式 $C(m+n,r) = \sum_{k=0}^{r} C(m,k)C(n,r-k)$ 将来自两个不相交集合的子集组合起来，在组合数学、生成函数和超几何函数中都有应用。