小蓝书 16._

小蓝书 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)!}$$

---

未完待续