形式陈述

设 $A$$A$ 是有限集且 $0\le k\le|A|$$0\le k\le |A|$。$A$$A$ 的一个 $k$$k$-组合就是满足 $C\subseteq A$$C\subseteq A$ 且 $|C|=k$$|C|=k$ 的子集。所有 $k$$k$-组合组成的集合常记为

$$ \binom{A}{k}=\{C\subseteq A:|C|=k\}. $$$$(\genfrac{}{}{0ex}{}{A}{k})=\{C\subseteq A:|C|=k\}.$$

直觉

组合只记录选中了哪些元素，不记录选择顺序。先选 $a$$a$ 后选 $b$$b$ 与先选 $b$$b$ 后选 $a$$a$ 表示同一个二元素子集。

例子与边界

从十名学生中选三人委员会，每个结果是一个三元素子集。$(a,b,c)$$(a,b,c)$ 与 $(c,a,b)$$(c,a,b)$ 是不同有序表，却对应同一组合。标准 $k$$k$-组合不允许重复选择；允许重复时需要多重集合或“可重复组合”的另一模型。

推论与应用

$n$$n$ 元集合的 $k$$k$-组合数是二项式系数 $\binom nk$$(\genfrac{}{}{0ex}{}{n}{k})$。组合用于委员会选择、无序样本、图的边集、固定大小搜索空间和超图中的均匀边。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018, Chapter 15.
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019, §6.3.