本节对应原书 PDF 第 230–232 页。习题题干逐字取自教材；答案逐字取自《离散数学习题解答与学习指导（第 3 版）》第 9 章「习题解答与分析」（PDF 第 154–159 页，印刷第 142–147 页）。AI 补充的中间步骤单独放在 details 折叠块中。
9.1 在 1 \sim 10\ 000 之间（包括 1 和 10 000 在内）不能被 4,5 和 6 整除的整数有多少个？
9.2 在 1 \sim 10\ 000 之间（包括 1 和 10 000 在内）既不是某个整数的平方，也不是某个整数的立方的整数有多少个？
9.3 一个学校有 507、292、312、344 个学生分别选了微积分、离散数学、数据结构、程序设计语言课，且有 14 人选了微积分和数据结构课，213 人选了微积分和程序设计语言课，211 人选了离散数学和数据结构课，43 人选了离散数学和程序设计语言课，没有学生同时选微积分和离散数学课，也没有学生同时选数据结构和程序设计语言课.问有多少学生在微积分、离散数学、数据结构或程序设计语言中选了课？
9.4 使用容斥原理求小于 200 的素数个数.
9.5 确定方程 x_1+x_2+x_3=14 的使得每个 x_i(i=1,2,3) 都不超过 8 的正整数解的个数.
9.6 有 3 只篮球，2 只红球，2 只黄球排成一列，若黄球不相邻，红球也不相邻，则有多少种方法？
9.7 求多重集 S=\{3 \cdot a,4 \cdot b,2 \cdot c\} 的排列数，使得在这些排列中同类字母的全体不能相邻（例如不允许 abbbbbccaa，但允许 aabbbacbc）.
9.8 设 S=\{2 \cdot a_1,2 \cdot a_2,\cdots,2 \cdot a_k\} 是多重集，如果在 S 的全排列中任意两个 a_i(i=1,2,\cdots,k) 都不相邻，问这样的全排列有多少个？
9.9 有 7 本书放在书架上，先把书拿下来然后重新放回书架，求满足以下条件的放法数.
（1）没有 1 本书在原来的位置上.
（2）至少有 1 本书在原来的位置上.
（3）至少有 2 本书在原来的位置上.
9.10 用恰好 k 种可能的颜色做旗子，使得每面旗子由 n 条彩带构成（n \geqslant k），且相邻的两条彩带都不相同，求不同的旗子数.
9.11 证明错位排列数 D_n 满足：n 为偶数当且仅当 D_n 为奇数.
9.12 n 对夫妻围圆桌就座，要求每对夫妻不相邻，问有多少种入座方式？
9.13 把 15 个人分到 3 个不同的房间，每个房间至少 1 个人，问有多少种分法？
9.14 使用数学归纳法证明容斥原理.
9.15 证明棋盘多项式具有以下性质.
（1）R(C)=xR(C_i)+R(\bar{C}_i).
（2）R(C)=R(C_1) \cdot R(C_2)，其中 C_1 和 C_2 不存在公共的行和列.
9.16 计算 R(\text{原书所示小棋盘}).
待核：习题 9.16 中 R 的自变量为原书手绘的小棋盘图形（3 个方格组成的图形），扫描件中为图形而非文字，无法逐字照抄；此处用文字代称。
9.3 习题解答与分析
9.1 被 4、5 和 6 整除的数的个数分别为
\lfloor 10\ 000/4 \rfloor=2500,\quad \lfloor 10\ 000/5 \rfloor=2\ 000,\quad \lfloor 10\ 000/6 \rfloor=1666
被 4 和 5、被 4 和 6、被 5 和 6 两个数同时整除的数的个数分别为
\lfloor 10\ 000/20 \rfloor=500,\quad \lfloor 10\ 000/12 \rfloor=833,\quad \lfloor 10\ 000/30 \rfloor=333
被 4、5、6 三个数整除的数的个数是
\lfloor 10\ 000/60 \rfloor=166
根据容斥原理，不能被 4、5 和 6 整除的数的个数是
N=10\ 000-(2500+2000+1666)+(500+833+333)-166=5334
9.2 在 1 到 10 000 之间是某个数的平方的数有 100 个.由于 21^3<10\ 000<22^3，是某个数的立方的数有 21 个.同理，由于 4096=4^6<10\ 000<5^6=125^2，因此既是某个数平方，也是某个数的立方的数有 4 个.根据容斥原理，所求的数的个数是
N=10\ 000-(100+21)+4=9883
9.3 设选修微积分、离散数学、数据结构、程序设计语言的学生集合分别为 A、B、C、D.根据题意得到
|A|=507,\ |B|=292,\ |C|=312,\ |D|=344
|A \cap C|=14,\ |A \cap D|=213,\ |B \cap C|=211,\ |B \cap D|=43
|A \cap B|=0,\ |C \cap D|=0
\begin{aligned}
|A \cap B \cap C| &= |A \cap B \cap D|=|A \cap C \cap D|\\
&= |B \cap C \cap D|=|A \cap B \cap C \cap D|=0
\end{aligned}
于是得到
N=(507+292+312+344)-(14+213+211+43+0+0)+0-0=974
9.4 由于 14^2<200<15^2，因此不超过 200 的数的最小素因子只可能是 \{2,3,5,7,11,13\} 中的数.设 1 到 200 之间能被 2,3,5,7,11,13 整除的数的集合分别记为 A,B,C,D,E,F.那么
|A|=100,\ |B|=66,\ |C|=40,\ |D|=28,\ |E|=18,\ |F|=15
|A \cap B|=33,\ |A \cap C|=20,\ |A \cap D|=14,\ |A \cap E|=9,\ |A \cap F|=7
|B \cap C|=13,\ |B \cap D|=9,\ |B \cap E|=6,\ |B \cap F|=5,\ |C \cap D|=5
|C \cap E|=3,\ |C \cap F|=3,\ |D \cap E|=2,\ |D \cap F|=2,\ |E \cap F|=1
|A \cap B \cap C|=6,\ |A \cap B \cap D|=4,\ |A \cap B \cap E|=3,\ |A \cap B \cap F|=2
|A \cap C \cap D|=2,\ |A \cap C \cap E|=1,\ |A \cap C \cap F|=1,\ |A \cap D \cap E|=1
|A \cap D \cap F|=1,\ |A \cap E \cap F|=0,\ |B \cap C \cap D|=1,\ |B \cap C \cap E|=1
|B \cap C \cap F|=1,\ |B \cap D \cap E|=0,\ |B \cap D \cap F|=0,\ |B \cap E \cap F|=0
|C \cap D \cap E|=0,\ |C \cap D \cap F|=0,\ |C \cap E \cap F|=0,\ |D \cap E \cap F|=0
剩下的子集都是空集.使用容斥原理得到
\begin{aligned}
N &= 200-(100+66+40+28+18+15)\\
&\quad +(33+20+14+9+7+13+9+6+5+5+3+3+2+2+1)\\
&\quad -(6+4+3+2+2+1+1+1+1+1+1+1)\\
&= 200-267+132-24=41
\end{aligned}
除了这 41 个数之外，还需要加上 2、3、5、7、11、13 这 6 个素数，还需要去掉 1，因此 200 以内的素数有 46 个.
9.5 根据题意，所有的非负整数解为 C(14+3-1,14)=C(16,2)=120 个，其中一个数超过 8 的非负整数解个数是 3C(5+3-1,5)=3C(7,2)=63 个，于是不超过 8 的非负整数解个数是 57.下面再考虑在这些解中含有的正整数解个数.在不超过 8 的非负整数解中，三个变量 x_1、x_2、x_3 中只可能有一个 x_i 取 0.在一个 x_i 为 0 时，其他的变量只有 6 和 8、7 和 7、8 和 6 三种可能的取值.因此包含 0 值的解有 9 种，从而得到所求的正整数解的个数为 N=57-9=48.
9.6 令 S=\{3 \cdot b,2 \cdot r,2 \cdot y\}，其中 b、r、y 分别代表蓝球、红球、黄球.先考虑 S 的全排列，有 \frac{7!}{3!2!2!} 种方法.若黄球相邻，那么将两个相邻的黄球看成 1 个球，相当于 \{3 \cdot b,2 \cdot r,1 \cdot y\} 的全排列，有 \frac{6!}{3!2!} 种方法.类似地，红球相邻也有 \frac{6!}{3!2!} 种方法.不仅黄球相邻、同时红球也相邻的方法数是 \frac{5!}{3!1!1!}.根据容斥原理，所求的方法数是
N=\frac{7!}{3!2!2!}-2 \times \frac{6!}{3!2!}+\frac{5!}{3!1!1!}=210-120+20=110
9.7 设 T=\{x|x 是 S 的全排列\}，A、B、C 是 T 的子集，且
A=\{x|x \in T \wedge x \text{ 含有 } aaa\}=\{x|x \text{ 是 } \{1 \cdot a',4 \cdot b,2 \cdot c\} \text{ 的全排列}\}
其中 a'=aaa.
B=\{x|x \in T \wedge x \text{ 含有 } bbbb\}=\{x|x \text{ 是 } \{3 \cdot a,1 \cdot b',2 \cdot c\} \text{ 的全排列}\}
其中 b'=bbbb.
C=\{x|x \in T \wedge x \text{ 含有 } cc\}=\{x|x \text{ 是 } \{3 \cdot a,4 \cdot b,1 \cdot c'\} \text{ 的全排列}\}
其中 c'=cc.
则
|T|=\binom{9}{3\ 4\ 2},\quad |A|=\binom{7}{1\ 4\ 2},\quad |B|=\binom{6}{3\ 1\ 2},\quad |C|=\binom{8}{3\ 4\ 1}
类似地有
|A \cap B|=\binom{4}{1\ 1\ 2},\quad |A \cap C|=\binom{6}{1\ 4\ 1}
|B \cap C|=\binom{5}{3\ 1\ 1},\quad |A \cap B \cap C|=\binom{3}{1\ 1\ 1}
\begin{aligned}
N &= \binom{9}{3\ 4\ 2}-\left[\binom{7}{1\ 4\ 2}+\binom{6}{3\ 1\ 2}+\binom{8}{3\ 4\ 1}\right]\\
&\quad +\left[\binom{4}{1\ 1\ 2}+\binom{6}{1\ 4\ 1}+\binom{5}{3\ 1\ 1}\right]-\binom{3}{1\ 1\ 1}\\
&= 1260-(105+60+280)+(12+30+20)-6=871
\end{aligned}
待核：9.7 的原书用的是竖排多重组合数记号（如把 9 写在中间、3 4 2 竖排在其下），扫描件中为三行叠排；此处按等价的写法 \binom{9}{3\ 4\ 2} 转录，数值与原书一致。
9.8 令 A=\{x|x 是 S 的全排列\}，A_i=\{x|x \in A 且含有两个相邻的 a_i\}，i=1,2,\cdots,k，则
|A|=\frac{(2k)!}{2^k}
|A_i|=\frac{(2k-1)!}{2^{k-1}},\quad i=1,2,\cdots,k
|A_i \cap A_j|=\frac{(2k-2)!}{2^{k-2}},\quad 1 \leqslant i<j \leqslant k
\vdots
|A_1 \cap A_2 \cap \cdots \cap A_k|=k!
根据容斥原理有
|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A}_k|=\sum_{r=0}^{k}(-1)^r\binom{k}{r}\frac{(2k-r)!}{2^{k-r}}
9.9 （1）相当于 7 个数的错位排列，于是
\begin{aligned}
D_7 &= 7!\left[1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}\right]\\
&= 2520-840+210-42+7-1=1854
\end{aligned}
（2）
N=7!-D_7=5040-1854=3186
（3）
\begin{aligned}
N &= 7!-D_7-7D_6\\
&= 3186-7 \cdot 6!\left[1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right]\\
&= 3186-(2520-840+210-42+7)=1331
\end{aligned}
9.10 使用对称筛公式.设 S 为至多用 k 种颜色涂色 n 条彩带但不允许相邻的彩带涂同色的方案的集合.S 的方案中没用到第 i 色的性质为 P_i，i=1,2,\cdots,k.那么有
|S|=k(k-1)^{n-1}=\binom{k}{0}(k-0)(k-1)^{n-1}
N_1=(k-1)(k-2)^{n-1}
N_2=(k-2)(k-3)^{n-1}
\vdots
N_i=(k-i)(k-i-1)^{n-1}
\vdots
N_k=(k-k)(k-k-1)^{n-1}=0
代入对称筛公式，得
N=\sum_{i=0}^{k-1}(-1)^i\binom{k}{i}(k-i)(k-i-1)^{n-1}=k\sum_{i=0}^{k-1}(-1)^i\binom{k-1}{i}(k-1-i)^{n-1}
本题也可以使用递推公式或第二类 Stirling 数的计数模型求解，相关的内容见第 10 章.可以证明用这几种方法得到的计数结果是相等的.
9.11 对 n 进行归纳.D_0=1，n=0 时命题为真.假设对一切小于 n 的自然数为真，考虑关于 D_n 的递推方程 D_n=(n-1)(D_{n-2}+D_{n-1}).若 n 为偶数，那么 n-1 为奇数，n-2 为偶数.根据归纳假设，D_{n-1} 为偶数，D_{n-2} 为奇数，它们的和为奇数，从而得到 D_n 为奇数.反之，设 D_n 为奇数.假若 n 为奇数，那么 n-1 为偶数.根据递推方程 D_n 也是偶数.与 D_n 为奇数矛盾.
9.12 设丈夫为 x_1,x_2,\cdots,x_n，妻子为 y_1,y_2,\cdots,y_n.x_i 与 y_i 相邻记为性质 p_i，i=1,2,\cdots,n.令 S 为 2n 个人的圆排列的集合，S 中满足性质 p_i 的子集为 A_i，i=1,2,\cdots,n.
|S|=(2n-1)!
|A_i|=2(2n-2)!,\quad i=1,2,\cdots,n
|A_i \cap A_j|=2^2(2n-3)!\quad 1 \leqslant i<j \leqslant n
\vdots
|A_1 \cap A_2 \cap \cdots \cap A_n|=2^n(n-1)!
由包含排斥原理有
\begin{aligned}
N &= (2n-1)!-\binom{n}{1}2(2n-2)!+\binom{n}{2}2^2(2n-3)!\\
&\quad -\binom{n}{3}2^3(2n-4)!+\cdots+(-1)^n\binom{n}{n}2^n(n-1)!\\
&= \sum_{k=0}^{n}(-1)^k\binom{n}{k}2^k(2n-k-1)!
\end{aligned}
9.13 令
S=\{x|x \text{ 是不加任何限制将 } 15 \text{ 个人分到 } 3 \text{ 个房间的方案}\}
A=\{x|x \in S,\text{且第一个房间没有人}\}
B=\{x|x \in S,\text{且第二个房间没有人}\}
C=\{x|x \in S,\text{且第三个房间没有人}\}
于是得到
|S|=3^{15},\quad |A|=|B|=|C|=2^{15}
|A \cap B|=|A \cap C|=|B \cap C|=1
|A \cap B \cap C|=0
使用容斥原理得到
N=3^{15}-3 \times 2^{15}+3-0=14\ 250\ 606
注意：本题还可以使用放球的计数模型求解，对应于 15 个不同的球恰好放到 3 个不同盒子的计数.放球模型的计数结果将在第 10 章给出.
9.14 m=2，|A_1 \cup A_2|=|A_1|+|A_2|-|A_1 \cap A_2| 成立.
假设对于任何正整数 m \geqslant 2，容斥原理及其推论成立，那么
\begin{aligned}
&|A_1 \cup A_2 \cup \cdots \cup A_{m+1}|=|(A_1 \cup A_2 \cup \cdots \cup A_m) \cup A_{m+1}|\\
=&|A_1 \cup A_2 \cup \cdots \cup A_m|+|A_{m+1}|-|(A_1 \cup A_2 \cup \cdots \cup A_m) \cap A_{m+1}|\\
=&\sum_{i=1}^{m}|A_i|-\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|+\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|-\cdots\\
&+(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m|+|A_{m+1}|\\
&-|(A_1 \cap A_{m+1}) \cup (A_2 \cap A_{m+1}) \cup \cdots \cup (A_m \cap A_{m+1})|\\
=&\sum_{i=1}^{m+1}|A_i|-\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j|+\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k|-\cdots\\
&+(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m|-\sum_{i=1}^{m}|A_i \cap A_{m+1}|\\
&+\sum_{1 \leqslant i<j \leqslant m}|A_i \cap A_j \cap A_{m+1}|-\sum_{1 \leqslant i<j<k \leqslant m}|A_i \cap A_j \cap A_k \cap A_{m+1}|+\cdots\\
&+(-1)^m|A_1 \cap A_2 \cap \cdots \cap A_m \cap A_{m+1}|\\
=&\sum_{i=1}^{m+1}|A_i|-\sum_{1 \leqslant i<j \leqslant m+1}|A_i \cap A_j|+\sum_{1 \leqslant i<j<k \leqslant m+1}|A_i \cap A_j \cap A_k|-\cdots\\
&+(-1)^m|A_1 \cap A_2 \cap \cdots \cap A_{m+1}|
\end{aligned}
9.15 （1）
R(C)=\sum_{k=0}^{\infty}r_k(C)x^k=r_0(C)+\sum_{k=1}^{\infty}r_k(C)x^k
=1+\sum_{k=1}^{\infty}[r_{k-1}(C_i)+r_k(\bar{C}_i)]x^k
=\sum_{k=1}^{\infty}r_{k-1}(C_i)x^k+1+\sum_{k=1}^{\infty}r_k(\bar{C}_i)x^k
=xR(C_i)+R(\bar{C}_i)
（2）
\begin{aligned}
R(C_1)R(C_2) &=\left(\sum_{k=0}^{\infty}r_k(C_1)x^k\right)\left(\sum_{l=0}^{\infty}r_l(C_1)x^l\right)\\
&=\sum_{k=0}^{\infty}\left(\sum_{i=0}^{k}r_i(C_1)r_{k-i}(C_2)\right)x^k\\
&=\sum_{k=0}^{\infty}r_k(C)x^k=R(C)
\end{aligned}
9.16 设给定棋盘为 C，则 R(C)=1+6x+7x^2+x^3.
解读：9.16 答案里 x 的系数 6 就是棋盘中单个方格的个数，x^2 的系数 7 是任取两个互不同行同列的方格的方法数，x^3 的系数 1 说明 3 个棋子只有一种布法。读出系数就能反推出棋盘形状。
习题 9.5 的补充说明（AI 生成，非原书）
原解答先算非负整数解：x_1+x_2+x_3=14 的非负解数为 \binom{16}{2}=120。再减去某个 x_i \geqslant 9 的情形：令 x_i'=x_i-9，则 x_i'+x_j+x_k=5 的非负解数为 \binom{7}{2}=21，三个变量共 3 \times 21=63 种。故 0 \leqslant x_i \leqslant 8 的非负解为 120-63=57。
题目要的是正整数解，还需从这 57 个里剔掉含 0 的解。三个变量和为 14 且都不超过 8 时，至多有一个变量为 0（若有两个为 0，第三个须为 14，超过 8）。设 x_3=0，则 x_1+x_2=14 且 1 \leqslant x_1,x_2 \leqslant 8，逐对列出为 (6,8),(7,7),(8,6) 共 3 组；三个变量各有 3 组，共 9 组。于是正整数解为 57-9=48。
可代回自检：\binom{16}{2}-3\binom{7}{2}-9=120-63-9=48。
习题 9.4 的补充说明（AI 生成，非原书）
N=41 数的是 1 \sim 200 中不被 2,3,5,7,11,13 中任何一个整除的数。这 41 个数里包含 1（它不是素数），却不包含 2,3,5,7,11,13（它们能被自身整除而被筛掉了），所以素数个数 =41+6-1=46。
可代回自检：1 \sim 200 中的素数为 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199，共 46 个。