跳到主要内容

组合初步 (Preliminary Combinatorics)

计数不仅是列举，更是一种逻辑。通过分类与分步，我们可以高效地解决生活中的选择与排列问题。

1. 计数基本原理​

1.1 加法原理 (分类计数)​

如果完成一件事有 nn 类办法，在第一类办法中有 m1m_1 种不同的方法，在第二类办法中有 m2m_2 种不同的方法... 在第 nn 类办法中有 mnm_n 种不同的方法。那么完成这件事共有： N=m1+m2+⋯+mnN = m_1 + m_2 + \dots + m_n 关键词：一步到位，非此即彼。

1.2 乘法原理 (分步计数)​

如果完成一件事需要 nn 个步骤，完成第一个步骤有 m1m_1 种不同的方法，完成第二个步骤有 m2m_2 种不同的方法... 完成第 nn 个步骤有 mnm_n 种不同的方法。那么完成这件事共有： N=m1×m2×⋯×mnN = m_1 \times m_2 \times \dots \times m_n 关键词：环环相扣，缺一不可。

2. 排列与组合基础​

2.1 排列 (Permutation)​

从 nn 个不同元素中取出 mm 个元素，并 按照一定顺序 排成一列。 Anm=n(n−1)…(n−m+1)=n!(n−m)!A_n^m = n(n-1)\dots(n-m+1) = \frac{n!}{(n-m)!}

2.2 组合 (Combination)​

从 nn 个不同元素中取出 mm 个元素，并 成一组（不考虑顺序）。 Cnm=Anmm!=n!m!(n−m)!C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}

区分排列与组合

顺序 是唯一的判别标准。

  • 选 3 人分别当班长、副班长、学习委员 →\rightarrow 排列。
  • 选 3 人当班代表 →\rightarrow 组合。

3. 抽屉原理 (Pigeonhole Principle)​

如果把 n+1n+1 只鸽子放进 nn 个鸽笼，那么至少有一个鸽笼里有 两只或两只以上 的鸽子。

最不利原则

解决“至少...才能保证...”这类问题时，先考虑最倒霉、最极端的情况（差一个就满），再加 1 即可。

4. 启发式练习​

练习 1：乘法原理应用

题目：从 A 地到 B 地有 3 条路，从 B 地到 C 地有 4 条路。请问从 A 地经 B 地到 C 地共有多少种走法？ 解析： 这是一个分两步完成的任务： 第一步：从 A 到 B（3 种）； 第二步：从 B 到 C（4 种）。 根据乘法原理：3×4=123 \times 4 = 12 种。

练习 2：组合数计算

题目：一个班有 5 名候选人，要选出 2 名作为志愿者，有多少种选法？ 解析： 因为志愿者之间没有职位差别（不分顺序），使用组合公式： C52=5×42×1=10 种C_5^2 = \frac{5 \times 4}{2 \times 1} = 10 \text{ 种}

练习 3：抽屉原理应用

题目：一个黑盒子里有红球 10 个，蓝球 8 个。至少摸出多少个球，才能保证摸出的球中一定有红球？ 解析： 利用 最不利原则：

  1. 运气最坏的情况：摸出的全是蓝球（8 个）。
  2. 再摸 1 个球，必然是红球。
  3. 因此：8+1=98 + 1 = 9 个。