计数原理与排列组合

本节导读

排列组合解决的是「有多少种」的问题，也是后面计算概率的基础。题目里的数字一般不大，难点不在运算，而在判断：这件事要分类还是分步，顺序有没有关系。

试卷里，这部分的考法有：直接计算排列数、组合数；用两个计数原理求方法数；判断一个问题是排列还是组合，再列式计算。学完这一节，你应该能分清分类和分步，会用公式算 $A_n^m$Anm​ 和 $C_n^m$Cnm​，会处理「特殊元素」「相邻」「至少」这几类常见的限制。

分类加法计数原理与分步乘法计数原理

• 分类加法计数原理：完成一件事有 $n$n 类办法，第 1 类有 $m_1$m1​ 种方法，第 2 类有 $m_2$m2​ 种方法，……，第 $n$n 类有 $m_n$mn​ 种方法，其中每一种方法都能独立完成这件事，那么共有 $N = m_1 + m_2 + \cdots + m_n$N=m1​+m2​+⋯+mn​ 种方法。
• 分步乘法计数原理：完成一件事需要分成 $n$n 个步骤，每一步都做完才算完成，第 1 步有 $m_1$m1​ 种方法，第 2 步有 $m_2$m2​ 种方法，……，第 $n$n 步有 $m_n$mn​ 种方法，那么共有 $N = m_1 \times m_2 \times \cdots \times m_n$N=m1​×m2​×⋯×mn​ 种方法。

判断的关键，是看「一次做完」还是「要做几步才完成」：做一次就完成，用加法，叫分类；要一步一步都做完才完成，用乘法，叫分步。分类时各类之间不重复、不遗漏，分步时各步之间相互独立、缺一不可。

例如，从甲地到乙地有 3 班火车和 2 班汽车，选任意一班就能到，共有 $3 + 2 = 5$3+2=5 种走法。如果从甲地到乙地有 3 条路，从乙地到丙地有 2 条路，从甲地经乙地到丙地要两段都走完，共有 $3 \times 2 = 6$3×2=6 种走法。

排列与排列数

从 $n$n 个不同元素中取出 $m$m 个（$m \le n$m≤n），按照一定的顺序排成一列，叫做一个排列。所有不同排列的个数叫排列数，记作 $A_n^m$Anm​，公式是

$$A_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}$$Anm​=n(n−1)(n−2)⋯(n−m+1)=(n−m)!n!​

乘积从 $n$n 开始，往下连乘 $m$m 个数。当 $m = n$m=n 时叫全排列，$A_n^n = n! = n(n-1)\cdots 2 \cdot 1$Ann​=n!=n(n−1)⋯2⋅1，并规定 $0! = 1$0!=1。例如 $A_5^3 = 5 \times 4 \times 3 = 60$A53​=5×4×3=60，$A_4^4 = 4! = 24$A44​=4!=24。

排列的特点是有顺序：同样的元素，顺序不同就是不同的排列。三种常用的处理办法：

• 特殊元素优先。例如 6 个人排成一排，甲不能站排头：先排排头，有 5 种选法，再排其余 5 个位置，有 $A_5^5 = 120$A55​=120 种，共 $5 \times 120 = 600$5×120=600 种。
• 相邻用捆绑。6 个人排成一排，甲、乙必须相邻：先把甲乙看成一个整体，与其余 4 人一起排，有 $A_5^5 = 120$A55​=120 种，再排整体内部，有 $A_2^2 = 2$A22​=2 种，共 $120 \times 2 = 240$120×2=240 种。
• 不相邻用间接法。还是这 6 个人，甲、乙不相邻：总数 $A_6^6 = 720$A66​=720，减去相邻的 240，得 480 种。

组合与组合数

从 $n$n 个不同元素中取出 $m$m 个（$m \le n$m≤n）并成一组，不考虑顺序，叫做一个组合。所有不同组合的个数叫组合数，记作 $C_n^m$Cnm​，公式是

$$C_n^m = \frac{A_n^m}{A_m^m} = \frac{n(n-1)\cdots(n-m+1)}{m!} = \frac{n!}{m!(n-m)!}$$Cnm​=Amm​Anm​​=m!n(n−1)⋯(n−m+1)​=m!(n−m)!n!​

组合数有这样的性质：$C_n^m = C_n^{n-m}$Cnm​=Cnn−m​，$C_n^0 = 1$Cn0​=1，$C_n^n = 1$Cnn​=1。第一条在 $m$m 比较大时可以化简，例如 $C_{10}^8 = C_{10}^2 = \dfrac{10 \times 9}{2 \times 1} = 45$C108​=C102​=2×110×9​=45。

排列和组合的区别在于有没有顺序。判断方法：取出元素后，交换其中两个的位置，结果是不是不同。不同是排列，相同是组合。例如从 5 个人中选 2 人当正、副组长，是排列，$A_5^2 = 20$A52​=20；选 2 人去参加会议，是组合，$C_5^2 = 10$C52​=10。每个组合对应 $A_m^m$Amm​ 个排列，所以 $A_n^m = C_n^m \cdot A_m^m$Anm​=Cnm​⋅Amm​，这里 $20 = 10 \times 2$20=10×2。