排列与组合详解

基本计数原理

计数问题问的是某件事有多少种发生方式。它的基础是基本计数原理（乘法原理）：如果第一个选择有 $m$ 种方式，第二个相互独立的选择有 $n$ 种方式，那么两个选择合在一起就有 $m \times n$ 种方式。这个思想可以推广到任意多个步骤。

如果你有 3 件衬衫、4 条裤子和 2 双鞋，就能搭配出 $3 \times 4 \times 2 = 24$ 套不同的服装。用数字 0 到 9 组成的四位密码，允许数字重复，共有 $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ 种可能。本文的每个公式都是这种乘法的简便算法，所以当一道题看起来很陌生时，回到逐步计数总是稳妥的退路。

阶乘

把 $n$ 个不同的物体全部排成一行，第一个位置有 $n$ 种选择，第二个位置有 $n - 1$ 种，依此类推，直到 1。这个乘积称为 $n$ 的阶乘：

所以 $5! = 120$：五本书在书架上可以有 120 种排列顺序。按定义 $0! = 1$，这使下面的公式保持一致，因为把“什么都没有”排列起来恰好只有一种方式。阶乘增长得惊人地快：$10! = 3{,}628{,}800$，而一副洗过的扑克牌有 $52!$ 种可能的顺序，这是一个 68 位数。

排列：顺序重要

排列是从 $n$ 个不同物体中选出 $r$ 个并按顺序排好。由于顺序重要，“第一、第二、第三”与“第三、第二、第一”是不同的。排列数为

人们围坐在圆桌旁是一种特殊情况。让所有人都挪动一个座位，得到的是同一种安排，所以 $n$ 个人有 $(n-1)!$ 种不同的坐法。六个人围坐圆桌有 $5! = 120$ 种安排，而不是 720 种。

组合：顺序无关

组合是只看选中了谁的选取方式。选安娜、本和卡拉进入委员会，无论以什么顺序选，都是同一个委员会。每组 $r$ 个物体对应 $r!$ 种排列，所以要把它们除掉：

组合具有对称性：$\binom{n}{r} = \binom{n}{n-r}$，因为选 3 个人入选，等同于选 5 个人落选。组合数也是杨辉三角（帕斯卡三角形）中的数，以及 $(a + b)^n$ 二项展开式中的系数。

如何判断该用哪一个

只需问一个问题：如果交换两个被选中的对象，结果会不同吗？如果会，顺序就重要，需要用排列；如果不会，就用组合。

• 名次、排名、密码、座次表和日程安排：用排列。
• 队伍、委员会、手中的一手牌、彩票号码和比萨配料：用组合。
• 群体内部的角色，例如主席和财务，会使顺序变得重要，即使这些人都来自同一个候选群体。

一个快速检验：排列数总是组合数的 $r!$ 倍。如果你的两个答案不满足这个关系，其中一个就错了。

可重复计数与重复字母

当物品可以重复使用时，公式会改变。可重复的有序选取共有 $n^r$ 种，就像密码的例子那样。可重复的无序选取，例如从 5 种口味中选 3 球冰淇淋，口味可以重复，其数目为

排列含有重复字母的单词还需要再调整一步：除以每个重复次数的阶乘，因为交换相同的字母不会带来任何变化。密西西比河英文名称的拼写共有 11 个字母，其中 I 出现 4 次、S 出现 4 次、P 出现 2 次，所以它有 $\frac{11!}{4!\,4!\,2!} = 34{,}650$ 种不同的排列。

用计数求概率

当各个结果的可能性相同时，概率就是有利结果的数目除以全部结果的数目，因此大部分工作都由排列和组合完成。这个比值的基础知识见概率基础。

纸牌游戏提供了更多练习。五张牌的一手牌共有 $\binom{52}{5} = 2{,}598{,}960$ 种可能。一手包含全部四张 A 的牌只需再从其余 48 张中选一张，所以概率为 $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$。

常见错误

• 对队伍或委员会使用排列，导致多算了 $r!$ 倍。
• 忘记 $0! = 1$，使 $\binom{n}{n}$ 之类的公式失效。
• 忽略相同的物品，例如在排列含有重复字母的单词时。
• 把不独立的步骤直接相乘，而没有调整后面步骤的计数。

排列组合计算器可以计算 ${}_nP_r$ 和 ${}_nC_r$ 并显示阶乘步骤，概率计算器则把这些计数转化为概率。

杨辉三角与子集

杨辉三角（帕斯卡三角形）中的每个数都等于它上方两个数之和，第 $n$ 行列出的是 $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$。第 4 行是 1、4、6、4、1，恰好是 $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$ 中的系数。构造这个三角形的规则本身就是一个计数事实：

要理解其中的道理，可以固定某一个特定物品。每一种选取 $r$ 个物品的方式，要么包含它，于是还需从其余 $n - 1$ 个中选 $r - 1$ 个；要么不包含它，于是需从其余 $n - 1$ 个中选全部 $r$ 个。把一整行相加得到 $2^n$，即含 $n$ 个元素的集合的子集总数，因为每个元素要么在子集中，要么不在。因此，一家有 8 种配料的比萨店可以做出 $2^8 = 256$ 种不同的比萨，其中包括什么都不加的那一种。

练习题

1. 从 7 本不同的书中选 4 本排在书架上，有多少种排法？答案：${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$。
2. 从 10 种配料中选 4 种，有多少种选法？答案：$\binom{10}{4} = 210$。
3. 由字母 A、A、A、B、N、N 组成的六字母排列共有多少种？答案：$\frac{6!}{3!\,2!} = 60$。
4. 如果允许字母重复，用 26 个字母可以组成多少个五字母代码？答案：$26^5 = 11{,}881{,}376$。

常见问题