离散数学 组合法

在数学中，组合（Combination）是从一个较大的集合中选取一部分元素，而不考虑选取的顺序。这与排列（Permutation）形成对比，排列需要考虑选取的顺序。

核心概念：顺序不重要

这是理解组合最关键的一点。

举个例子：假设有三个字母 {A, B, C}，我们想从中选出两个。

• 组合：只关心选出了哪两个字母。

  • {A, B}

  • {A, C}

  • {B, C}

    总共有 3 种组合。注意，选出 {A, B} 和选出 {B, A} 被视为同一种组合。

• 排列：关心选出了哪两个字母，并且关心它们的排列顺序。

  • {A, B} 和 {B, A} 是两种

  • {A, C} 和 {C, A} 是两种

  • {B, C} 和 {C, B} 是两种

    总共有 6 种排列。

组合的计算公式

我们通常用 C(n,k) 或 (kn​) 来表示组合。它的意思是：从 n 个不同元素中，取出 k 个元素的组合数。

计算公式如下：

C(n,k)=(kn​)=k!(n−k)!n!​

其中：

• n 是可供选择的元素总数。

• k 是要选取的元素个数。

• ! 是阶乘符号。例如，5!=5×4×3×2×1=120。

公式解析：

这个公式可以理解为：

1. 首先计算从 n 个元素中选 k 个的排列数 P(n,k)=(n−k)!n!​。

2. 因为组合不考虑顺序，所以需要除去这 k 个元素自身可以产生的所有排列情况，也就是 k! 种。

3. 因此，用排列数除以 k!，就得到了组合数。

计算示例

问题： 某班有10名学生，要从中选出3人组成一个学习小组。有多少种不同的组队方式？

分析：

• 这是一个组合问题，因为选出张三、李四、王五，和选出李四、王五、张三，是同一个学习小组，顺序不重要。

• 这里，n = 10 (总学生数)，k = 3 (要选的人数)。

计算：

C(10,3)=(310​)=3!(10−3)!10!​=3!7!10!​=(3×2×1)(7×6×5×4×3×2×1)10×9×8×7×6×5×4×3×2×1​

为了简化计算，我们可以消掉 7!：

=3×2×110×9×8​=6720​=120

答案： 共有 120 种不同的组队方式。

组合法的应用场景

当遇到需要从一个集合中“选取”、“抽取”、“分组”等问题，并且不关心所选元素的内部顺序时，就应该使用组合法。

• 彩票： 从33个红球中选6个，顺序无所谓，是一个典型的组合问题 C(33,6)。

• 组建委员会/团队： 从50名员工中选5人组成项目组。

• 抽样检查： 从100件产品中随机抽取10件进行质量检查。

• 纸牌游戏： 在一副52张的扑克牌中，拿到特定牌型（如“同花顺”）的组合数。

总结

Google Gemini