本节对应原书 PDF 第 202–208 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

下面考虑选取问题（组合计数模型 1）.

设 n 元集合 S，从 S 中选取 r 个元素. 那么不同的选法有多少种？如表 8.1 所示，根据选取元素是否有序，是否允许重复，可以将选取问题分为 4 个子类型：集合的排列、集合的组合、多重集的排列和多重集的组合.

例如，从 20 个人中选出 10 个人排成一排，那么这是一个有序的、不允许重复的选取问题，因为选出的人排列的位置不一样对应于不同的选法，而且每个人在排列中至多出现 1 次. 如果选出的 10 个人不是排成一排，而是组成一个兴趣小组，那么唯一确定选法的是哪些人参加小组，而与选择的顺序无关. 这是一个无序的、不允许重复的选取问题. 如果被选择的不是人而是字母，例如从英文字母中选择 6 个字母组成字符序列，并且允许序列中的字符重复出现，那么这是一个有序的允许重复选取问题. 如果只是选出一组 6 个字符，并且允许字符重复出现，那么就变成一个无序的允许重复的选取问题. 对不同类型的选取问题计数的方法不一样. 对于集合的排列与组合问题，可以通过加法法则与乘法法则得到相应的计数公式. 对于多重集的排列与组合，只能对某些特殊情况得到计数公式，一般性的求解方法将在后面两章讨论.

表 8.1

重复＼次序不重复选取重复选取
有序选取集合的排列多重集的排列
无序选取集合的组合多重集的组合

8.2.1 集合的排列与组合

下面考虑集合的排列与组合.

定义 8.1 从 n 元集 S 中有序、不重复选取的 r 个元素称为 S 的一个 r-排列，S 的所有 r-排列的个数记作 P(n,r).

引入阶乘符号 n!=n\times(n-1)\times(n-2)\cdots 2\times 1，规定 0!=1，那么定理 8.1 给出了 P(n,r) 的值.

定理 8.1 设 n,r 为自然数，则

P(n,r)=\begin{cases}\dfrac{n!}{(n-r)!}&n\geqslant r\\[6pt]0&n<r\end{cases}

证明 显然当 n<r 时不存在满足条件的排列. 下面考虑 n\geqslant r 的情况. 首先确定排列中的第一个元素，有 n 种选择的方式. 然后确定排列的第二个元素，它只能取自剩下的 n-1 个元素，有 n-1 种选法. 类似地，选择第三个元素，第四个元素，\cdots\cdots，第 r 个元素的方式数依次为 n-2,n-3,\cdots,n-r+1. 根据乘法法则，总的选法数为

n(n-1)(n-2)\cdots(n-r+1)=\dfrac{n!}{(n-r)!}

当 r=n 时，称排列为 S 的全排列. 容易看出全排列数等于 n!.

上面的排列均指线排列. 如果规定选出的元素不是按照顺序排成一列，而是排成一个圆圈，那么这种排列称为环排列. 设线排列的 r 个元素依次为 a_1,a_2,\cdots,a_r，将 a_1 接在 a_r 的后边组成一个环排列. 按照这种方法，线排列 a_2,a_3,\cdots,a_r,a_1 也可以构成相同的环排列. 只要相邻关系不变，这 r 个元素中的任何一个作为线排列的首元素，首尾相连所构成的环排列都相同. 因此环排列数是线排列数的 1/r. 从而得到 n 元集 S 的 r-环排列数满足下面的公式：

S\text{ 的 }r\text{-环排列数}=\dfrac{P(n,r)}{r}

定义 8.2 从 n 元集 S 中无序、不重复选取的 r 个元素称为 S 的一个 r-组合，S 的所有 r-组合的个数记作 C(n,r).

定理 8.2 给出了关于 C(n,r) 的公式.

定理 8.2 设 n,r 为自然数，则

C(n,r)=\begin{cases}\dfrac{P(n,r)}{r!}=\dfrac{n!}{r!(n-r)!}&n\geqslant r\\[6pt]0&n<r\end{cases}

证明 用分步处理的方法构成 r-排列. 首先无序地选出 r 个元素，然后再构造这 r 个元素的全排列. 无序选择 r 个元素的方法数是 C(n,r)，针对每种选法，能构造 r! 个不同的全排列，根据乘法法则，不同的 r-排列数满足

P(n,r)=C(n,r)r!

定理得证.

推论 设 n,r 为正整数，则

(1) C(n,r)=\dfrac{n}{r}C(n-1,r-1).

(2) C(n,r)=C(n,n-r).

(3) C(n,r)=C(n-1,r-1)+C(n-1,r).

证明 (1) 将定理 8.2 的公式代入即可.

(2) 证明一：将定理 8.2 的公式代入，化简后两边相等.

也可以采用组合分析的方法给出公式(2)的证明. 所谓组合分析方法就是设计出一个组合计数问题，使得公式两边都对应于这个问题的计数结果. 下面给出这个公式的组合证明.

证明二（组合证明）：设 S=\{1,2,\cdots,n\} 是 n 元集合，对于 S 的任意 r-组合 A=\{a_1,a_2,\cdots,a_r\}，都存在一个 S 的 n-r 组合 S-A 与之对应. 显然不同的 r 组合对应了不同的 n-r 组合，反之也对，因此 S 的 r 组合数恰好与 S 的 (n-r)-组合数相等.

(3) 利用定理 8.2 得

\begin{aligned} C(n-1,r-1)+C(n-1,r)&=\dfrac{(n-1)!}{(r-1)!(n-r)!}+\dfrac{(n-1)!}{r!(n-1-r)!}\\ &=\dfrac{(n-1)!}{(r-1)!(n-r-1)!}\left[\dfrac{1}{n-r}+\dfrac{1}{r}\right]\\ &=\dfrac{n}{r(n-r)}\dfrac{(n-1)!}{(r-1)!(n-r-1)!}\\ &=\dfrac{n!}{r!(n-r)!}\\ &=C(n,r) \end{aligned}

以上推论可以看作是递推的公式，它可以把对应于较大的 n 或 r 的组合数 C(n,r) 用对应于较小的 n' 或 r' 的组合数来表示. (3)中的公式称作 Pascal 公式，它的图形表示就是著名的杨辉三角形. 利用这个公式可以由较小的组合数逐步求出所有的较大的组合数. 图 8.2 给出了这种求法的示意图. 例如 C(5,3)，其上层相邻的位置恰好为 C(4,2)=6，C(4,3)=4，于是有 C(5,3)=6+4=10.

原书图8.2

图 8.2

利用上述的排列组合公式能够解决不重复的选取问题.

例 8.5 从 1\sim 300 中任取 3 个数使得其和能被 3 整除有多少种方法？

解 令

\begin{aligned} A&=\{1,4,\cdots,298\}\\ B&=\{2,5,\cdots,299\}\\ C&=\{3,6,\cdots,300\} \end{aligned}

根据问题的要求将选法分成以下几类.

\begin{aligned} &\text{分别取自 }A,B,C\text{ 中的一个集合：}\qquad &\text{各 }C(100,3)\\ &A,B,C\text{ 各取 1 个：}\qquad &C(100,1)^3 \end{aligned}

根据加法法则和乘法法则，总选法数

N=3C(100,3)+100^3=1\ 485\ 100

例 8.6 (1) m 个男孩，n 个女孩排成一排，如果女孩不相邻，有多少种方法？

(2) 如果排成一个圆圈，结果又是什么？

解 (1) 先排好男孩，这对应于 m 元集合的全排列问题，有 m! 种方法. 为使得女孩不相邻，将男孩看作格子分界，将女孩放入格子中间，m 个男孩构成了 m+1 个格子（包含男孩的全排列之外的头尾两个位置在内），从中选出 n 个放入女孩，选法数是 P(m+1,n). 根据乘法法则所求的方法数是 m!\ P(m+1,n).

(2) 与(1)不同的是，这里的排列是环排列. m 个元素的环排列数是 (m-1)!，这就是男孩排列成圆圈的方法数. 接着放入女孩，环排列构成的格子数是 m 个，因此放女孩的方法数为 P(m,n)，那么所求的方法数为 (m-1)!\ P(m,n).

例 8.7 设 A 为 n 元集，问

(1) A 上的自反关系有多少个？

(2) A 上的反自反关系有多少个？

(3) A 上的对称关系有多少个？

(4) A 上的反对称关系有多少个？

(5) A 上既不对称也不是反对称的关系有多少个？

解 (1) 在 A 上自反关系对应的关系矩阵中，主对角线元素都是 1，其他位置的元素可以是 1，也可以是 0，每个位置有 2 种选择. 这种位置有 n^2-n 个，根据乘法法则，自反关系的个数是 2^{n^2-n}.

(2) 与(1)类似，反自反关系也有 2^{n^2-n} 个.

(3) 考虑 A 上对称关系的矩阵. 采用分步处理的方法，先考虑主对角线上的元素. 对于主对角线的每个位置，元素可以选择 0 或者 1，有 2 种选法，总共有 2^n 种方法. 再考虑不在主对角线位置的元素，它们的值的选择并不是完全独立的. 因为矩阵是对称的，i 行 j 列的元素 r_{ij} 必须与 j 行 i 列的元素 r_{ji} 相等. 因此当矩阵的上三角元素（或者下三角元素）的值确定以后，另一半对称位置的元素就完全确定了. 这种能够独立选择 0 或者 1 的位置有 (n^2-n)/2 个. 因此根据乘法法则，构成矩阵的方法数是 2^n2^{\frac{n^2-n}{2}}=2^{\frac{n^2+n}{2}}.

(4) 类似于(3)的分析，也采用分步处理的方法，区别在于对非主对角线位置元素取值的约束条件不一样. 将这些位置分成 (n^2-n)/2 组，每组包含处在对称位置的两个元素 r_{ij} 和 r_{ji}，其中 i\neq j. 根据反对称的性质，r_{ij} 与 r_{ji} 的取值有以下 3 种可能：① r_{ij}=1，r_{ji}=0；② r_{ij}=0，r_{ji}=1；③ r_{ij}=r_{ji}=0.

因此所有这些位置元素的选择方法数为 3^{\frac{n^2-n}{2}}. 由乘法法则，考虑到主对角线元素的选取，总方法数为 2^n3^{\frac{n^2-n}{2}}.

(5) 可以按照下面的方法计算 A 上既不是对称也不是反对称关系的数目. 先找出 A 上所有关系的总数，然后减去 A 上对称关系的数目和反对称关系的数目. 这样，对于那些既对称的也反对称的关系，就被减去两次，因此应该再加上这种关系的个数. A 上的关系总数为 2^{n^2}；既对称也反对称的关系都是恒等关系的子集，有 2^n 个；从而得到所求的关系个数是 2^{n^2}-\left(2^{\frac{n^2+n}{2}}+2^n3^{\frac{n^2-n}{2}}\right)+2^n.

解读：例 8.7 把关系计数全部翻译成「矩阵里有几个格子可以自由填」——自反/反自反固定主对角线，对称固定一个三角，反对称让每个对称位置有 3 种填法。第(5)问用的是容斥：既对称又反对称的关系被减了两次，要加回来一次。

例 8.8 问：1000! 的末尾有多少个 0？

解 1000!=1000\times 999\times 998\times\cdots\times 2\times 1

将上面的每个因子进一步分解，若 1000! 的分解式中有 i 个 5，j 个 2，那么 \min(i,j) 就是 0 的个数.

1,\cdots,1000 中有 500 个数是 2 的倍数，因此 j>500. 再考虑 i. 1,2,\cdots,1000 中有 200 个数是 5 的倍数，其中 40 个是 25 的倍数. 而一个数是 25 的倍数则意味着它的分解式中至少含有 2 个 5. 因此在 1000! 的分解式中还需要增加 40 个 5. 类似地，还有 8 个是 125 的倍数，这就需要再增加 8 个 5；1 个数是 625 的倍数，再增加 1 个 5. 总计 1000! 的分解式中含有 i=200+40+8+1=249 个 5. 从而得到 \min(i,j)=249.

8.2.2 多重集的排列与组合

设多重集 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}，其中含有 k 种元素，对于 i=1,2,\cdots,k，n_i 表示第 i 种元素 a_i 在 S 中出现的次数，一般 0<n_i\leqslant+\infty. 多重集用于处理允许重复的选取问题，当 n_i=+\infty 时表示有足够多的 a_i 以备选取. 关于允许重复的选取，只有某些特殊情况可以得到计数公式，一般情况下只能利用生成函数或包含排斥原理来求解，这些技术将在后面两章给予介绍.

设多重集 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}，且 n=n_1+n_2+\cdots+n_k，称 S 的全体元素组成的排列为 S 的全排列. 下面讨论 S 的 r-排列在特殊情况下的一些结果.

定理 8.3 (1) 当 r=n 时，S 的全排列数

N=\dfrac{n!}{n_1!n_2!\cdots n_k!}

(2) 若 r\leqslant n_i，i=1,2,\cdots,k 时，S 的 r-排列数是 k^r.

证明 (1) 在 n 个位置中先选择 n_1 个位置放 a_1，有 C(n,n_1) 种方法；再从剩下的 n-n_1 个位置选择 n_2 个位置放 a_2，有 C(n-n_1,n_2) 种方法；\cdots；最后在 n-n_1-n_2-\cdots n_{k-1} 个位置中选择 n_k 个位置放 a_k，有 C(n-n_1-n_2-\cdots n_{k-1},n_k) 方法. 根据乘法法则，

\begin{aligned} N&=C(n,n_1)C(n-n_1,n_2)\cdots C(n-n_1-n_2-\cdots-n_{k-1},n_k)\\ &=\dfrac{n!}{n_1!(n-n_1)!}\dfrac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdots\dfrac{(n-n_1-\cdots-n_{k-1})!}{n_k!0!}\\ &=\dfrac{n!}{n_1!n_2!\cdots n_k!} \end{aligned}

(2) r 个位置中的每个位置都有 k 种选法，由乘法法则得 k^r.

多重集 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\} 的全排列数也记作 \dbinom{n}{n_1n_2\cdots n_k}，其中 n=n_1+n_2+\cdots+n_k. 这个数也称作多项式系数. 关于它的性质在 8.4 节还会进一步讨论.

再考虑多重集 S 的 r-组合.

定理 8.4 当 r\leqslant n_i，i=1,2,\cdots,k 时，多重集 S 的 r-组合数 N=C(k+r-1,r).

证明 可以使用一一对应的思想来证明这个定理.

S 的一个 r-组合为 S 的一个子多重集 \{x_1\cdot a_1,x_2\cdot a_2,\cdots,x_k\cdot a_k\}，其中

x_1+x_2+\cdots+x_k=r,\quad x_i\text{ 为非负整数},\quad i=1,2,\cdots,k

这个方程称为不定方程，可以在它的非负整数解 x_1,x_2,\cdots,x_k 和 r 个 1、k 个 0 的排列之间建立一一对应：对于解 x_1,x_2,\cdots,x_k，排列具有下述形式：

\underbrace{11\cdots 1}_{x_1\text{ 个}}0\underbrace{11\cdots 1}_{x_2\text{ 个}}0\cdots 0\underbrace{11\cdots 1}_{x_k\text{ 个}}

其中 k-1 个 0 将 r 个 1 分成 k 段，每段含有 1 的个数分别为 x_1,x_2,\cdots,x_k. 不难看出，这个排列是多重集 S=\{r\cdot 1,(k-1)\cdot 0\} 的全排列，根据定理 8.3，这样的排列有

N=\dfrac{(r+k-1)!}{r!(k-1)!}=C(k+r-1,r)

个，因此 S 的 r-组合数是 C(k+r-1,r).

解读：定理 8.4 的「一一对应」是本节的枢纽：一个 r-组合对应一组非负整数解，而一组解又对应一个由 1 和 0 组成的排列。两跳之后，「从 k 种元素里可重复地选 r 个」就变成了「把 r 个 1 和 k-1 个 0 全排列」，直接套定理 8.3。

下面是使用选取模型或者不定方程解的计数模型来处理组合问题的实例. 解题的关键在于将实际问题与适当的计数模型之间建立对应关系，然后应用相应的计数公式.

例 8.9 r 个相同的球放到 n 个不同的盒子里，每个盒子球数不限，求放球的方法数.

解 设 n 个不同盒子的球数依次记为 x_1,x_2,\cdots,x_n，则满足下述方程

x_1+x_2+\cdots+x_n=r,\quad x_1,x_2,\cdots,x_n\text{ 为非负整数}

根据不定方程的解的个数公式，放球方法数是

N=C(n+r-1,r)

例 8.10 排列 26 个字母，使得 a 与 b 之间恰有 7 个字母，求排列的方法数 N.

解 采用分步处理的方法. 先固定 a 和 b，中间插入 7 个字母，构成一个结构，有 2P(24,7) 种方法. 将这个结构看作一个大字母与其余 17 个字母进行全排列，有 18! 种排列的方法. 根据乘法法则，N=2P(24,7)18!.

例 8.11 把 2n 个人分成 n 组，每组 2 人，求不同的分法数 N.

解 先计数 n 个不同的组的分法，然后除以组的排列数，就得到所求的分法数.

将 2n 个不同的人分到 n 个不同的组，先从 2n 个人中选 2 个人分入第一组；然后从剩下的 2n-2 个人中选 2 个人分入第二组，\cdots，最后从 2n-(2n-2)=2 个人中选 2 个人分入第 n 组. 根据乘法法则，分法数是

\begin{aligned} &C(2n,2)C(2n-2,2)\cdots C(2,2)\\ &=\dfrac{2n!}{(2n-2)!2}\dfrac{(2n-2)!}{(2n-4)!2}\cdots\dfrac{2!}{0!2}=\dfrac{(2n)!}{2^n} \end{aligned}

所求的方法数是

N=\dfrac{(2n)!}{2^n n!}

例 8.12 9 本不同的书，其中 4 本红皮，5 本白皮.

(1) 9 本书的排列方式有多少种？

(2) 若白皮书必须放在一起，那么有多少种方法？

(3) 若白皮书必须放在一起，红皮书也必须放在一起，那么有多少种方法？

(4) 若白皮和红皮书必须相间，有多少种方法？

解 (1) 9 本书的全排列数 9!.

(2) 先放白皮书有 5! 方法，将这些白皮书看成一个整体，与 4 本红皮书进行全排列，有 5! 种排列的方法，根据乘法法则所求的方法数是 5!5!.

(3) 白皮书的放法数是 5!，红皮书的放法数是 4!，将所有的红皮书看成一本书，所有的白皮书也看成一本书，进行排列的方法数是 2!. 由乘法法则，所求的方法数为 5!4!2!.

(4) 先放白皮书，有 5! 种方法. 每本红皮书只能放在两本白皮书之间，有 4! 种方法. 总计有 5!4! 种方法.

例 8.13 从 S=\{1,2,\cdots,n\} 中选择 k 个不相邻的数，有多少种方法？

解 使用一一对应的思想求解这个计数问题. 设 a_1,a_2,\cdots,a_k 是选出的 k 个数，由这 k 个数对应生成另外的 k 个数 b_1,b_2,\cdots,b_k. 产生规则是 b_i=a_i-(i-1)，i=1,2,\cdots,k. 例如原来的数是 3,6,8,14；那么生成的数为 3,5,6,11. 不难看出，对于两组不同的 k 个数 a_1,a_2,\cdots,a_k 与 a'_1,a'_2,\cdots,a'_k，生成的两组数 b_1,b_2,\cdots,b_k 与 b'_1,b'_2,\cdots,b'_k 也不相同. 反之，如果生成的两组数不相同，那么原来的两组数也不相同. 它们之间存在一一对应关系. 只需计数生成的序列 b_1,b_2,\cdots,b_k 有多少个，就可以得到原来问题的解. 由于所有的 b_i 允许相邻，且 b_k 至多是 n-(k-1)，因此这些序列的个数就是从 \{1,2,\cdots,n-(k-1)\} 中无序选取 k 个元素的方法数，从而得到问题的解是 C(n-(k-1),k)=C(n-k+1,k).

利用组合公式也可以证明一些涉及整除的命题.

例 8.14 证明 k 个连续正整数的乘积可以被 k! 整除.

证明 设这 k 个连续正整数为 n+1,n+2,\cdots,n+k. 从 n+k 个不同的元素中选取 k 个元素的方法数是 C(n+k,k)，即

N=\dfrac{(n+k)!}{n!k!}=\dfrac{(n+1)(n+2)\cdots(n+k)}{k!}

因为 N 是对方法的计数，一定是正整数，命题得证.

解读：例 8.13 的变换 b_i=a_i-(i-1) 把「互不相邻」拉直成「允许相邻」，于是问题退回普通的组合选取；例 8.14 则是反过来把「整除」翻译成「这是个计数结果，必须是整数」，都是同一个思想的两种用法。