题干逐字取自原书 PDF 第 218–220 页（印刷 p203–p205），解答逐字取自答案书第 8 章「习题解答与分析」（PDF p145–p151，印刷 p133–p139）. 题干与原书解答均不进入折叠块；只有 AI 补充的额外说明才放进
:details，且标题标注「AI 生成，非原书」.
8.1 从去掉大小王的 52 张扑克牌中取出 5 张牌，若其中有 4 张点数一样，则有多少种取法？若第一张牌是红桃，第二张牌不是 K，则有多少种取法？
解 先选 4 张点数一样的牌，有 13 种选法. 然后再选另一张牌，有 48 种选法，因此 5 张牌中有 4 张点数一样的选法数是 13 \times 48 = 624.
若第一张牌是红桃 K，则第二张牌只能从除去所有 K 剩下的 48 张牌选取，有 48 种选法. 若第一张牌不是红桃 K，那么第一张有 12 种选择，第二张牌有 47 种可能的选法. 综合上述，总选法数是 48 + 12 \times 47 = 612.
8.2 从集合 \{1, 2, \cdots, 1000\} 中选 3 个数使得其和是 4 的倍数，问有多少种方法？
解 将 1～1000 中的数按照除以 4 的余数分别为 0、1、2、3，划分成集合 A、B、C、D. 将选法分成下面几类：3 个数都取自 A，有 C(250, 3) 种方法；2 个数取自 B，1 个数取自 C（或 2 个数取自 D，1 个数取自 C，或 2 个数取自 C，1 个数取自 A）有 C(250, 2)C(250, 1) 种方法；A、B、D 中各取 1 个数，有 C(250, 1)^3 种方法. 根据加法法则，所求方法数是
8.3 从 S = \{1, 2, \cdots, 20\} 中选出 4 个数使得其和是 3 的倍数，问有多少种选法？
解 将 1～20 中的数按照除以 3 的余数为 0、1、2 划分成集合 A、B、C. 其中 |A| = 6，|B| = |C| = 7. 将选法分成下面几类：
4 个数都取自 A，有 C(6, 4) = 15 种方法；
A 中取 2 个数，B 中取 1 个数，C 中取 1 个数，有 C(6, 2)C(7, 1)C(7, 1) = 735 种方法；
A 中取 1 个数，B 中取 3 个数，有 C(6, 1)C(7, 3) = 210 种方法；
A 中取 1 个数，C 中取 3 个数，有 C(6, 1)C(7, 3) = 210 种方法；
B 中取 2 个数，C 中取 2 个数，有 C(7, 2)C(7, 2) = 441 种方法.
根据加法法则，所求方法数是 15 + 735 + 210 + 210 + 441 = 1611.
8.4 有多少个十进制 3 位数的数字恰有一个 8 和一个 9？
解 先从 0, 1, \cdots, 7 中选择一个数字，有 C(8, 1) 种方法. 将这个数字与 8 和 9 组成 3 位数，有 3! 种排列. 其中，089 和 098 不符合题目要求. 因此，所求的 3 位数是 3! \times C(8, 1) - 2 = 46 个.
8.5 由 1, 2, 3, 4 这 4 种数字能构成多少个大于 230 的 3 位数？
解 若第 1 位是 3 或 4，则第 2 位和第 3 位每位有 4 种选择，共计 2 \times 4^2 = 32 种方式. 若第 1 位是 2，那么第 2 位可以是 3 或 4 有 2 种选择，第 3 位可以有 4 种选择，总共 8 种方法. 于是，大于 230 的 3 位数有 32 + 8 = 40 个.
8.6 从集合 \{1, 2, \cdots, 9\} 中选取不同数字构成 7 位数，如果 5 和 6 不相邻，则有多少种方法？
解 从 \{1, 2, \cdots, 9\} 选出 7 个数字进行排列有 P(9, 7) 种方法. 考虑其中 5 和 6 相邻的方式数. 将 5 与 6 看成 1 个大数字，构成这个大数字的方式数就是 5 与 6 的排列数，有 2 种；剩下的 5 个数字从 \{1, 2, 3, 4, 7, 8, 9\} 中选择，有 C(7, 5) 种选法，将这些数字与 5 和 6 的大数字进行全排列，就构成了 5 与 6 相邻的方式. 因此 5 与 6 相邻的方式有 2 \times 6! \times C(7, 5) 种，于是所要求的数恰好有 P(9, 7) - 2 \times 6! \times C(7, 5) = 151\,200 个.
8.7 在 1～1000 之间（包括 1 和 1000 在内）有多少个整数的各位数字之和小于 7？
解 设百位、十位、个位数字分别为 x, y, z，那么 x + y + z = r，r = 1, 2, \cdots, 6. 该方程的非负整数解个数是 C(r + 3 - 1, r) = C(r + 2, 2). 除此之外，1000 本身也满足要求. 于是所求的数的个数是
8.8 用数字 0, 1, 2, 3, 4, 5 能组成多少个没有重复数字且比 34521 大的 5 位数？
解 如果第 1 位是 4，那么后面的 4 个数字构成 \{0, 1, 2, 3, 5\} 的 4-排列，有 P(5, 4) 种方式，类似地，若第 1 位是 5，也有相同的结果. 如果第 1 位是 3，为了使得这个数大于 34 521，那么第 2 位只能取 5，剩下的后 3 位构成 \{0, 1, 2, 4\} 的 3-排列，有 P(4, 3) 种方式. 于是所求的数有 2P(5, 4) + P(4, 3) = 264 个.
8.9 有多少个大于 5400，不含 2 和 7，且各位数字不重复的整数？
解 如果这个数是 i + 1 位数，i = 4, 5, 6, 7，那么它的最高位可能为 1、3、4、5、6、8、9，有 7 种可能. 设最高位为 j，其余的位构成集合 \{0, 1, \cdots, 9\} - \{2, 7, j\} 的 i 排列. 根据乘法法则与加法法则，这些数的个数是
如果这个数是 4 位数，那么当最高位为 6、8、9 时，其他各位为剩下的 7 个数的 3-排列，有 3P(7, 3) 种构成方法. 如果最高位为 5，次高位只能是 4、6、8、9，其余部分是 6 个数字的 2-排列，因此有 4P(6, 2) 种构成方法. 根据加法法则，这样的 4 位数有 3P(7, 3) + 4P(6, 2) = 750 个. 从而得到所求的数的个数是
8.10 设有 k 种明信片，每种张数不限. 现在要分别寄给 n 个朋友，k \geqslant n，若给每个朋友寄 1 张明信片，有多少种寄法？若给每个朋友寄 1 张明信片，但每个人得到的明信片都不相同，则有多少种寄法？若给每个朋友寄 2 张不同的明信片（不同的人可以得到相同的明信片），则有多少种寄法？
解 因为每人得到 1 张明信片有 k 种不同的可能，因此 n 个人有 k^n 种可能. 如果每个人都得到 1 张不同的明信片，相当于从 k 张明信片中选出 n 张进行排列，有 P(k, n) 种方法. 若使得每个人都得到 2 张不同的明信片，那么先从 k 张明信片中选出 2 张，有 C(k, 2) 种选法，每个人得到的 2 张明信片可能属于任何一种选法. 于是所求的方法数是 (C(k, 2))^n.
8.11 设有 k 类明信片，且第 i 类明信片的张数是 A_i，i = 1, 2, \cdots, k. 把它们全部送给 n 个朋友，问有多少种方法？
解 第 i 种明信片有 \dbinom{A_i + n - 1}{A_i} 种送出的方法，因此总方法数为
8.12 由满足不等式 x_1 + x_2 + x_3 < 5 的非负整数解 x_1，x_2，x_3 构成的有序三元组 \langle x_1, x_2, x_3 \rangle 的个数是多少？
解 考虑方程 x_1 + x_2 + x_3 = r，r = 0, 1, \cdots, 4 的非负整数解的个数，即 C(6, 2) + \cdots + C(2, 2) = 35.
8.13 把 10 个不同的球放到 6 个不同的盒子里，允许空盒，且前 2 个盒子球的总数至多是 4，则有多少种方法？
解 从 10 个球中先选出放入前两个盒子的 k 个球，k = 0, 1, 2, 3, 4. 然后将这些球放入前两个盒子. 由于每个球有 2 种放法，根据乘法法则，总放法是 C(10, k)2^k 种. 剩下的 10 - k 个球需要放入后 4 个盒子，每个球有 4 种选择，共 4^{10-k} 种放法. 使用乘法法则并对 k 求和，最终得到
8.14 书架上有 24 卷百科全书，从其中选 5 卷使得任何 2 卷都不相邻，问这样的选法有多少种？
解 使用一一对应的方法，将所有书的集合记作 S = \{1, 2, \cdots, 24\}，选出的 5 卷不相继的书为 i_1, i_2, \cdots, i_5，其中 i_1 < i_2 < \cdots < i_5，且 i_j + 1 \neq i_{j+1}，j = 1, 2, 3, 4. 令 k_j = i_j - j + 1，j = 1, 2, 3, 4, 5. 例如 i_1, i_2, \cdots, i_5 是 2, 5, 7, 13, 15，那么 k_1, k_2, \cdots, k_5 是 2, 4, 5, 10, 11. 显然，i_1, i_2, \cdots, i_5 与 k_1, k_2, \cdots, k_5 之间是一一对应的. \{k_1, k_2, \cdots, k_5\} 恰好是 \{1, 2, \cdots, 20\} 的 5 组合，因此所求选法数是 C(20, 5) = 15\,504.
8.15 由集合 \{5 \cdot a, 1 \cdot b, 1 \cdot c, 1 \cdot d, 1 \cdot e\} 中的全体元素构成字母序列，求
（1）没有 a 相邻的序列个数.
（2）b, c, d, e 中的任何两个字母都不相邻的序列个数.
解 （1）如果没有 a 相邻，那么在 5 个 a 中间必须插入 b、c、d、e 4 个字母. 插入的方法数是这 4 个字母的排列数，即 4! = 24.
（2）方法 1 将 5 个 a 看成格子的边界，形成 6 个格子，从其中选出 4 个格子放 b、c、d、e 4 个字母有 P(6, 4) = 6 \times 5 \times 4 \times 3 = 360 种方法.
方法 2 先放 b、c、d、e，有 4! 种方法. 然后，在其中每两个字母中间插入 1 个 a. 剩下的 2 个 a，可以放在以 b、c、d、e 作为格子边界的 5 个格子中. 设这 5 个格子中 a 的个数分别为 x_1, x_2, \cdots, x_5，那么方法数等于方程 x_1 + x_2 + \cdots + x_5 = 2 的非负整数解个数，即 C(5 + 2 - 1, 2) = C(6, 2) = 15. 根据乘法法则，所求的方法数是 15 \times 4! = 360.
8.16 满足不等式 x_1 + x_2 + x_3 \leqslant 7 的非负整数解的个数是多少？
解 方程 x_1 + x_2 + x_3 = i 的非负整数解的个数是 \dbinom{i + 3 - 1}{i}，对 i = 0, 1, \cdots, 7 求和就得到所求的计数，这个结果等于
8.17 设 S = \{1, 2, \cdots, n+1\}，从 S 中选择 3 个数构成有序三元组 \langle x, y, z \rangle 使得 z > x 且 z > y.
（1）证明：若 z = k+1，则这样的有序三元组恰为 k^2 个.
（2）将所有的有序三元组按照 x = y，x < y，x > y 分成 A，B，C 三组，证明
（3）由（1）和（2）证明恒等式
解 （1）z = k + 1，则 x, y 各有 k 种选择，故不同三元组有 k^2 个.
（2）当 x = y 时，不同的三元组数为从 1, 2, \cdots, n+1 选择 2 个数的选法数，即 \dbinom{n+1}{2}. 当 x < y 时，对于 z = 3, 4, \cdots, n+1，x 与 y 的选法数为 C(z - 1, 2). 使用加法法则，则不同的三元组数为 C(2, 2) + C(3, 2) + \cdots + C(n, 2) = \dbinom{n+1}{3}. 类似的分析可以知道，当 x > y 时，不同的三元组数也是 \dbinom{n+1}{3}.
（3）利用（1）和（2）的结果，再使用加法法则就可以得到
8.18 有 n 个整数 a_1, a_2, \cdots, a_n，满足 a_1 < a_2 < \cdots < a_n. 从中选出两组数，每组至少含 1 个数，且要求第一组的最小数大于第二组的最大数，问有多少种方案？
解 先选 k 个数，2 \leqslant k \leqslant n，然后把 k 个数分成两组，共 k - 1 种分法，根据乘法法则与加法法则得到计数结果，再利用组合公式化简得
8.19 根据 IPv4 网络协议，每个计算机的地址是 32 位二进制数字构成的串. 其中 A 类地址第一位是 0，接着 7 位是网络标识，再接着 24 位是主机标识. B 类地址前两位是 10，接着 14 位网络标识，再接着 16 位主机标识. C 类地址前 3 位是 110，接着 21 位网络标识，再接着 8 位主机标识. 此外，A 类地址中全 1 不能做网络标识，在三类地址中全 0 和全 1 都不能作为主机标识. 问按照 IPv4 协议，在 Internet 中有多少个有效的计算机地址？
解 A 类地址的网络标识有 2^7 - 1 = 127 种，主机标识有 2^{24} - 2 = 16\,777\,214 种；B 类地址的网络标识有 2^{14} = 16\,384 种，主机标识有 2^{16} - 2 = 65\,534 种；C 类地址的网络标识有 2^{21} = 2\,097\,152 种，主机标识有 2^8 - 2 = 254 种. 于是，有效地址总数为
8.20 假设计算机系统的每个用户有一个 4～6 个字符的登录密码，每个字符是大写字母或者十进制数字，且每个密码必须至少包含一个数字. 问有多少个可能的登录密码？
解 将密码按照字符个数进行分类，包含 4 个字符的有 (4^{36} - 4^{26}) 个，包含 5 个字符的有 (5^{36} - 5^{26}) 个，包含 6 个字符的有 (6^{36} - 6^{26}) 个. 因此，登录密码总数为
8.21 从 S = \{\infty \cdot 0, \infty \cdot 1, \infty \cdot 2\} 中取 n 个数做排列，若不允许相邻位置的数相同，问有多少种排法？
解 第 1 位数可以有 3 种选法，第 2 位数只有 2 种选法，因为它不能选择第 1 位的数. 按照这样的安排，从第 2 位到第 n 位，每位都有 2 种选法，根据乘法法则，选择的方法有 3 \times 2^{n-1} 种.
8.22 给出多重集 \{2 \cdot a, 1 \cdot b, 3 \cdot c\} 的所有的 3-排列与 3-组合.
解 3-组合：\{a, a, b\}，\{a, a, c\}，\{a, b, c\}，\{a, c, c\}，\{b, c, c\}，\{c, c, c\}
3-排列：aab，aba，baa，aac，aca，caa，abc，acb，bac，bca，cab，cba，acc，cac，cca，bcc，cbc，ccb，ccc
8.23 有 3 只蓝球，2 只红球，2 只黄球排成一列，若黄球不相邻，则有多少种方法？
解 令 S = \{3 \cdot b, 2 \cdot r, 2 \cdot y\}，其中 b, r, y 分别代表蓝球、红球、黄球. 先考虑 S 的全排列，有 \dfrac{7!}{3!2!2!} 种方法. 若黄球相邻，那么将两个相邻的黄球看成 1 个球，相当于 \{3 \cdot b, 2 \cdot r, 1 \cdot y\} 的全排列，有 \dfrac{6!}{3!2!1!} 种方法，于是所求的方法数是 \dfrac{7!}{3!2!2!} - \dfrac{6!}{3!2!1!} = 150.
8.24 由 m 个 A 和 n 个 B 构成序列，其中 m, n 为正整数. 如果要求每个 A 后面至少跟着 1 个 B，问有多少个不同的序列？
解 方法 1 先放 m 个 AB，只有一种方法. 然后在由这 m 个 AB 构成的 m + 1 个空格中加入 n - m 个 B. 这相当于方程
的非负整数解的个数，因此
方法 2 将 B 看作格子分界，形成了 n + 1 个空格. 除了最后一个空格之外，从其他 n 个空格中选择 m 个空格放 A，有 C(n, m) 种方法.
8.25 A = \{1, 2, \cdots, n\}，S \subseteq A，其中 n 为给定正整数. 如果 S 的每个元素都不小于 S 的元素个数 |S|，就称 S 是饱满的（这里认为空集是饱满的）. 令 N(n) 表示 A 的饱满子集的个数.
（1）导出关于 N(n) 的公式.
（2）计算 N(8).
解 （1）A 中大于等于 k 的元素个数为 n - k + 1，因此含 k 个元素的饱满子集有 C(n - k + 1, k) 个，于是饱满子集总数为
（2）N(8) = \sum_{k=0}^{8}\dbinom{9 - k}{k} = 55.
8.26 证明：
（1）\sum\limits_{k=0}^{n}\dbinom{n}{k}2^k = 3^n.
（2）\sum\limits_{k=0}^{n}(-1)^k\dbinom{n}{k}3^{n-k} = 2^n.
（3）\sum\limits_{k=1}^{n+1}\dfrac{1}{k}\dbinom{n}{k-1} = \dfrac{2^{n+1}-1}{n+1}.
解 （1）方法 1 由二项式定理有
在上式中令 x = 1 即可.
方法 2 对 n 归纳，则
n = 1，\sum\limits_{k=0}^{1}\dbinom{1}{k}2^k = 2^0 + 2^1 = 3，命题为真.
假设命题对于 n 为真，考虑 n + 1 的情况，则
由归纳法，命题为真.
（2）由二项式定理有
在上式中令 x = 1 即可.
（3）方法 1 由二项式定理得 (1 + x)^n = \sum\limits_{k=0}^{n}\dbinom{n}{k}x^k，对两边积分得
于是得到
在上式中令 x = 1，得到
方法 2 利用主教材 p194～195 的公式(2)和公式(4)得到
8.27 求和：
（1）\sum\limits_{k=0}^{m}\dbinom{n-k}{m-k}.
（2）\dbinom{r+0}{0}\dbinom{m-0}{n-0} + \dbinom{r+1}{1}\dbinom{m-1}{n-1} + \cdots + \dbinom{r+n}{n}\dbinom{m-n}{n-n}.
解 （1）方法 1 利用主教材 p194 和 p196 的公式(1)和公式(8)得到
方法 2 利用 Pascal 公式，得
（2）如图 8.1 所示，考虑从 (0, 0) 点到 (m-n+r+1, n) 点的非降路径数，将这些路径按照经过 x = r 直线上不同的点 (r, k) 向右进行分类，其中 k = 0, 1, \cdots, n. 从 (0, 0) 点到 (r, k) 点的非降路径有 \dbinom{r+k}{k} 条，从 (r+1, k) 点到 (m-n+r+1, n) 点的非降路径有 \dbinom{m-k}{n-k} 条. 因此从 (0, 0) 点经过 (r, k) 点向右到达 (m-n+r+1, n) 点的非降路径数是 \dbinom{r+k}{k}\dbinom{m-k}{n-k}. 对 k = 0, 1, \cdots, n 求和即得 \dbinom{m+r+1}{n}.
8.28 证明组合恒等式：
（1）\sum\limits_{k=2}^{n-1}(n-k)^2\dbinom{n-1}{n-k} = n(n-1)2^{n-3} - (n-1)^2.
（2）\sum\limits_{k=0}^{n}(-1)^k\dbinom{n}{k}\dbinom{k}{r} = 0.
证明 （1）利用主教材 p195 中的公式(7)得到
（2）利用主教材 p195 和 p196 中的公式(5)和公式(9)得到
8.29 证明：\sum\limits_{k=0}^{n-1}\dbinom{n}{k}\dbinom{n}{k+1} = \dfrac{(2n)!}{(n-1)!(n+1)!}.
证明 利用主教材 p194 和 p197 中的公式(1)和公式(10)得到
8.30 求和：\sum\limits_{k=0}^{n}C(2n, 2k).
解 利用主教材 p195 中的公式(4)和公式(5)得到
n = 0，\sum\limits_{k=0}^{0}C(2n, 2k) = 1
n > 0，
8.31 设 3n+1 个球中恰好有 n 个相同，证明从这 3n+1 个球中选 n 个球的方案数是 2^{2n}.
证明 令 S = \{1 \cdot a_1, 1 \cdot a_2, \cdots, 1 \cdot a_{2n+1}, n \cdot b\}，求 S 的 n 组合数，按照含多少个 b 分类处理.
不含 b：C(2n+1, n)
含 1 个 b：C(2n+1, n-1)
\vdots
含 n 个 b：C(2n+1, 0)
根据加法法则有
解得