组合

组合计数"从若干不同对象中选出一组（不计顺序）"的方案数，与排列互补：排列有序、组合无序。

定义

从 $n$ 个不同元素中取 $k$ 个组成一组，称为 $n$ 取 $k$ 的组合，其数目为

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

性质

• 对称性 $\binom{n}{k}=\binom{n}{n-k}$
• Pascal 递推 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
• $\sum_{k=0}^{n}\binom{n}{k}=2^n$（子集总数）
• $\binom{n}{k}$ 是二项式展开 $(1+x)^n$ 中 $x^k$ 的系数，见二项式系数

示例

从 5 名学生中选 2 名代表：$\binom{5}{2}=\frac{5!}{2!\,3!}=10$ 种。

组合计数常与容斥原理结合处理带限制的选择问题。