排列与组合——计数的艺术
从日常选课到密码设置，排列与组合是解决计数问题的核心工具。本文从班级选举实例切入，系统讲解加法与乘法原理，推导排列与组合公式，深入剖析分组分配、错位排列等难点，配合树状图与杨辉三角图形，通过三类典型例题训练分步分类思维，帮助你攻克计数问题。
一、从“选班长和副班长”说起
假设班级有5名候选人：A、B、C、D、E。现在要选出1名班长和1名副班长（两人不能兼任）。问有多少种不同的选拔结果？
如果只是选出2名代表（不区分职务），又有多少种不同结果？
第一个问题：班长有5种选择，班长选定后副班长有4种选择，所以总共有 $5 \times 4 = 20$ 种。这种有序的选取方式就是排列。
第二个问题：若只选2人，不考虑顺序，则从5人中任选2人的组合数为 $\binom{5}{2} = 10$。这种无序的选取方式就是组合。
这两个看似相似的问题，答案却不同，原因在于顺序是否重要。排列与组合是计数问题的两大基石。
二、两个基本原理
1. 加法原理（分类计数）
完成一件事有 k 类不同方案，第 i 类方案有 $m_i$ 种方法，则总方法数为 $m_1 + m_2 + \cdots + m_k$。
关键：每类方案互不重叠，且都能独立完成事件。
2. 乘法原理（分步计数）
完成一件事需要 k 个步骤，第 i 步有 $n_i$ 种方法，则总方法数为 $n_1 \times n_2 \times \cdots \times n_k$。
关键：各步骤相互独立，缺一不可。
三、排列
1. 排列的概念
从 $n$ 个不同元素中，任意取出 $m$（$m \le n$）个元素，按照一定的顺序排成一列，称为从 $n$ 个不同元素中取出 $m$ 个元素的排列。所有不同排列的个数记作 $A_n^m$（或 $P_n^m$）。
2. 排列数公式推导
考虑第1个位置有 $n$ 种选法，第2个位置有 $n-1$ 种，……，第 $m$ 个位置有 $n-m+1$ 种。由乘法原理：
$$A_n^m = n \times (n-1) \times \cdots \times (n-m+1) = \frac{n!}{(n-m)!}$$
特别地，全排列 $A_n^n = n!$。
3. 示例
5人选班长和副班长（有序）：$A_5^2 = 5 \times 4 = 20$。
四、组合
1. 组合的概念
从 $n$ 个不同元素中，任意取出 $m$（$m \le n$）个元素组成一组（不计顺序），称为从 $n$ 个不同元素中取出 $m$ 个元素的组合。组合数记作 $C_n^m$ 或 $\binom{n}{m}$。
2. 组合数公式推导
每一种组合（无序）对应着 $m!$ 种排列（因为选出的 $m$ 个元素可以全排列）。因此：
$$A_n^m = C_n^m \times m! \quad \Rightarrow \quad C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$$
3. 组合数的性质
- 对称性：$C_n^m = C_n^{n-m}$
- 递推公式（帕斯卡公式）：$C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}$
- 特殊值：$C_n^0 = 1$，$C_n^1 = n$，$C_n^n = 1$
五、典型例题
例题1（中等）—— 相邻问题（捆绑法）
6人排成一排，要求甲、乙两人必须相邻，有多少种不同的排法？
思路：将甲、乙捆绑视为一个整体（内部可交换顺序），与其余4人共5个元素全排列，再乘以内部排列数。
步骤：
① 把甲、乙看作一个整体，内部有 $2! = 2$ 种顺序（甲乙或乙甲）。
② 整体（1个） + 剩余4人 = 5个元素，全排列 $A_5^5 = 5! = 120$。
总排法：$120 \times 2 = 240$ 种。
易错点：忘记内部排列，或者误用组合。
例题2（较难）—— 顺序唯一确定（转化为组合）
从数字1,2,3,...,9中任选4个不同的数字，组成一个四位数，要求千位数字 > 百位数字 > 十位数字 > 个位数字。这样的四位数有多少个？
思路：一旦选出4个数字，它们的大小顺序是唯一确定的（降序排列）。因此，只需计算从9个数字中任选4个的组合数。
步骤：$C_9^4 = \frac{9\times8\times7\times6}{4\times3\times2\times1} = 126$。
关键：将“有序排列”转化为“无序组合”，避免了直接排列的复杂分类。
例题3（困难）—— 分组分配问题
有6本不同的书，分给甲、乙、丙三位同学，每人至少1本，有多少种不同的分法？
思路：先将6本书分成三组（非空），再将三组书分配给三个不同的人（全排列）。分组时需考虑人数分配方案：1-1-4, 1-2-3, 2-2-2。
步骤：
① 分组情况：
- 方案A：1,1,4 组。先选4本书一堆：$C_6^4$，剩下2本各一堆但两堆相同（1,1）需除以 $2!$。故分组数 $\frac{C_6^4 \cdot C_2^1 \cdot C_1^1}{2!} = \frac{15 \times 2 \times 1}{2} = 15$。
- 方案B：1,2,3 组。三堆数量全不同，无须除：$C_6^1 \times C_5^2 \times C_3^3 = 6 \times 10 \times 1 = 60$。
- 方案C：2,2,2 组。三堆相同，需除以 $3!$：$\frac{C_6^2 \times C_4^2 \times C_2^2}{3!} = \frac{15 \times 6 \times 1}{6} = 15$。
② 每组分配给人：每种分组对应 $3! = 6$ 种分配方式。
③ 总方法：$(15 + 60 + 15) \times 6 = 90 \times 6 = 540$ 种。
易错点：分组时未考虑堆是否相同而漏除或错除。
六、常见误区
- 混淆排列与组合：判断顺序是否重要。如“选代表”是组合，“选职位”是排列。
- 分步计数时漏乘或重复：乘法原理每一步必须独立且完整。
- 忘记边界条件：如 $0! = 1$，$C_n^0 = 1$。
- 分组问题中忽略均匀组的除法：当有几组元素个数相同，分组数要除以相同组数的阶乘。
七、学习建议
1. 先定性，后公式：仔细审题，判断是排列还是组合，再考虑是否需要分类或分步。
2. 多用树状图或列举法：遇到复杂问题先穷举小规模，理解规律后再推广。
3. 记住常见模型：相邻问题捆绑法、不相邻问题插空法、定序问题倍缩法、名额分配隔板法等。
4. 反复练习分组分配：这是高考和竞赛的高频难点，掌握“先分组后分配”的套路。
八、知识链接
- 概率：古典概型中利用排列组合计算样本空间和事件数。
- 二项式定理：$(a+b)^n = \sum_{k=0}^n C_n^k a^{n-k}b^k$，组合数是展开式的系数。
- 杨辉三角：组合数的直观展示，也是递推关系的几何表达。
- 数列与数学归纳法：某些排列组合递推关系可用归纳法证明。
九、习题自测
- 从7名男生和3名女生中选出5人组成代表队，要求至少有2名女生，有多少种选法？
- 用0,1,2,3,4,5组成无重复数字的四位数，其中个位数字小于十位数字的有多少个？
- 将4个相同的小球放入3个不同的盒子，每个盒子至少一个球，有多少种放法？（提示：隔板法）
参考答案
- 分类：2女+3男：$C_3^2 \cdot C_7^3 = 3 \times 35 = 105$；3女+2男：$C_3^3 \cdot C_7^2 = 1 \times 21 = 21$；总和 126。
- 先不考虑条件，四位数的总数：千位不能为0，有5种选法，后面三位从剩下5个数字中选3个排列：$5 \times A_5^3 = 5 \times 60 = 300$。其中个位 < 十位的与个位 > 十位的情况各占一半（因为个位和十位是对称的），所以 $300 \div 2 = 150$。
- 隔板法：4个球之间有3个空隙，插入2个隔板将球分成3份（非空），$C_3^2 = 3$ 种。