22.01 计数原理、排列与组合

🟦 计数原理、排列与组合专题

核心心法

“分类用加法，分步用乘法；有序选排列，无序选组合”。计数原理是解决“有多少种可能”的底层逻辑。排列关注的是元素的位置顺序，而组合关注的是元素的选取结果。掌握排列组合数之间的倍数关系（$A_n^m=C_n^m\cdot m!$），能帮助你理清复杂计数问题中的逻辑层次。

---

一、 计数原理 (Counting Principles)

1. 分类加法计数原理

• 定义：完成一件事有 $n$ 类办法，各步方法相互独立。
• 公式：$N=m_1+m_2+\cdots +m_n$。
• 特点：每种方法都能直接独立完成这件事。

2. 分步乘法计数原理

• 定义：完成一件事需要分成 $n$ 个必经步骤，各步相互依存。
• 公式：$N=m_1\times m_2\times \cdots \times m_n$。
• 特点：必须完成所有步骤，这件事才算完成。

---

二、 排列 (Permutation)

1. 定义与排列数

• 排列：从 $n$ 个不同元素中取出 $m$ 个，$\ast \ast 按照一定顺序\ast \ast$ 排成一列。
• 排列数：所有不同排列的个数，用 $A_n^m$ 表示。

2. 排列数公式

• 一般公式：$A_n^m=n(n-1)\dots (n-m+1)=\frac{n!}{(n-m)!}$ （$m\le n$）。
• 全排列：$A_n^n=n!$。规定 $0!=1$。

3. 排列数的性质

• ① $n\cdot A_n^n=(n+1)!-n!$
• ② $\frac{n}{(n+1)!}=\frac{1}{n!}-\frac{1}{(n+1)!}$ （常用于数列裂项求和）

---

三、 组合 (Combination)

1. 定义与组合数

• 组合：从 $n$ 个不同元素中取出 $m$ 个$\ast \ast 合成一组\ast \ast$（不考虑顺序）。
• 组合数：所有不同组合的个数，用 $C_n^m$ 表示。

2. 组合数公式

• 计算式：$C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$ （$m\le n$）。
• 规定：$C_n^0=1$。

3. 组合数的性质

• ① 对称性：$C_n^m=C_n^{n-m}$。
  • 若 $C_n^x=C_n^y$，则 $x=y$ 或 $x+y=n$。
• ② 递推性 (杨辉三角基础)：$C_n^m+C_n^{m-1}=C_{n+1}^m$。

---

四、 排列数与组合数的关系

$A_n^m=C_n^m\cdot A_m^m$

• 理解：从 $n$ 个中取 $m$ 个的排列过程，可以看作先“组合”（取出 $m$ 个），再“排列”（将这 $m$ 个全排列）。

---

⚠️ 考场避坑与做题技巧

“有序”还是“无序”的判定

拿到题目先自问：“换个位置，结果变吗？”。如果换位置结果变了（如排队、发职务、组数字），用排列 $A$；如果换位置结果不变（如选代表、抽样检查、配菜），用组合 $C$。

防止重复与遗漏

分类计数时，要确保各类别之间不重不漏；分步计数时，要确保各步骤之间连续且完整。

处理排列组合的常用模型

• 相邻问题：捆绑法（将相邻元素视为一个大元素）。
• 不相邻问题：插空法（先排其他元素，再将不相邻元素插入空位）。
• 定序问题：除法倍数法（总排列数除以定序全排列）。
• 至多/至少问题：反难则易（使用间接法，总数减去不符合要求的情况）。