小蓝书 16.1 题解
传送门：小蓝书 16.1
一、加法原理和乘法原理
例1
从 \(1,2,3,\cdots,100\) 中取 \(3\) 个数，使这 \(3\) 个数恰好成等差数列的不同取法有_______种。
解法1：
设取出的 \(3\) 个数构成首项为 \(a\) ，公差为 \(d\) 的等差数列： \[ a,a+d,a+2d \quad (a,d \in \mathbb{Z}_+) \] 则 \(a+2d \le 100\) ，则 \[ 1 \le d \le \left\lfloor{\dfrac{100-a}{2}}\right\rfloor \le \left\lfloor{\dfrac{100-1}{2}}\right\rfloor = 49 \] 整理一下就是 \[ 1\le d \le 49 \\ a\le 100-2d \] 对于每个确定的 \(d\) ，\(a\) 都有 \(100-2d\) 种取法，则答案为 \[ \sum_{d=1}^{49}(100-2d) = 49\times 100 -2 \times \frac{49(49+1)}{2} = 2450 \] 解法2
设取出的 \(3\) 个数分别为 \(a_1,a_2,a_3\) ，它们构成公差为 \(d\) 的等差数列
于是 \(a_2=\dfrac{a_1+a_3}{2}\) 可被 \(a_1,a_3\) 唯一确定，且 \(a_1,a_3\) 的奇偶性相同
- 若 \(a_1\) 与 \(a_3\) 同为偶数，则有 \(\mathrm{C}_{50}^{2}\) 种取法
- 若 \(a_1\) 与 \(a_3\) 同为计数，则有 \(\mathrm{C}_{50}^{2}\) 种取法
则共有 \(2 \times \mathrm{C}_{50}^2\) 种取法。
例2
已知集合 \(A = \{x \mid 5x - a \le 0\}, B = \{x \mid 6x - b > 0\}, a,b \in \mathbb{N}\) 且 \(A\cap B\cap\mathbb{N} = \{2,3,4\}\) ，求整数对 \((a,b)\) 的个数。
解：根据 \(A,B\) 定义，可以得到 \[ 4 \le \frac{a}{5} < 5,~1 \le \frac{b}{6} < 2 \] 即 \[ 20\le a \le 25, ~6 \le b \le 12 \] 所以答案就是 \(\mathrm{C}_{5}^1\mathrm{C}_6^{1} = 30\) 。
二、无重复的排列与组合
例3
现安排 \(7\) 名同学参加 \(5\) 个运动项目，要求甲、乙两同学不能参加同一项目，每个项目都有人参加，每人只能参加一个项目，则满足上述要求的不同安排方案数为 __________ 。
解法1：
分类讨论（其实这里广泛用到了容斥原理，或者说俗称的“间接法”）
有一个项目有 \(3\) 人参加时，若不考虑甲乙是否参加同一项目，则有 \(\mathrm{C}_{7}^3\times 5!\) 种方案。
其中甲乙两人都参加 \(3\) 人项目时，有 \(\mathrm{C}_5^1\times 5!\) ，故这种情况的方案数为 \[ \mathrm{C}_{7}^3\times 5! - \mathrm{C}_5^1\times 5! = 3600 \]
有两个项目各有 \(2\) 人参加时，若不考虑甲乙是否参加同一项目，则有 \(\frac{1}{2}\mathrm{C}_{7}^2\mathrm{C}_{5}^2\times5!\) 种方案
其中甲乙两人参加同一项目时，共有 \(\mathrm{C}_{5}^2\times 5!\) ，故这种情况的方案数为 \[ \frac{1}{2}\mathrm{C}_{7}^2\mathrm{C}_{5}^2\times5!-\mathrm{C}_{5}^2\times 5! = 11400 \]
因此总方案数为 \(3600 + 11400 = 15000\) 种。
解法2：
小蓝书上这种解法有点过于麻烦和重复了，我就不写了。
解法3：
哎，每次都只会这个，啥时候改改。（\(S\) 表示第二类斯特林数） \[ 5!\times S(7,5) - 5! \times S(6,5) = 15000 \]
三、可重复的排列与组合
例4
共有 \(7\) 种面额的某国纸币（每种数量不限），求取 \(10\) 张纸币的方案数。
解：套可重组合数公式 \[ H_{7}^{10} = \binom{10 + 7 - 1}{10 - 1} = 8008 \]
例5
将 \(3\) 面红旗、\(4\) 面蓝旗、\(2\) 面黄旗一次悬挂在旗杆上，问可以组成多少种不同的标志
解：套多重组合数公式 \[ \binom{9}{3,4,2} = \frac{9!}{3!\,4!\,2!} = 1260 \]
例6
从 \(n(n \ge 6)\) 名乒乓球选手中选拔出 \(3\) 对选手准备参加双打比赛，问共有多少种不同的方案。
提示：本题中 \(3\) 对选手没有标号之分。
解：套多组组合公式 \[ \frac{1}{3!}\times \binom{n}{6}\binom{6}{2,2,2} = \frac{n!}{48(n-6)!} \]
未完待续
