第6章 数学和逻辑 — 组合数学、常用原理与逻辑推理

本讲义系统整理了组合数学基础、常见解题套路（八大技巧）、容斥原理与鸽巢原理、逻辑推理问题，以及前中后缀表达式的相互转换与求值。讲义最后附有完整的练习题集与详细解析，并针对部分经典算法问题给出了 C++ 实现代码。

6.1 组合数学基础

1. 排列与组合的基本概念

在解决计数问题时，首先需要理清是“排列”问题还是“组合”问题。

• 组合 (Combination)：从 $n$ 个不同元素中取出 $m$ ($m \le n$) 个元素并成一组，不考虑元素的顺序。
  • 公式： $$C_n^m = \binom{n}{m} = \frac{A_n^m}{A_m^m} = \frac{n!}{m!(n-m)!}$$
  • 性质：$C_n^m = C_n^{n-m}$
• 排列 (Permutation)：从 $n$ 个不同元素中取出 $m$ ($m \le n$) 个元素，按照一定的顺序排成一列，需要考虑元素的顺序。
  • 公式： $$A_n^m = P_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}$$

核心区别： * 排列与元素的顺序有关； * 组合与元素的顺序无关。

2. 排列组合八大解题技巧

在信息学奥赛及各类数学竞赛中，排列组合题型灵活多变。掌握以下八种经典解题技巧可以化繁为简：

技巧1：相邻问题 — 整体捆绑法

• 适用场景：要求某些元素必须相邻。
• 方法：先将必须相邻的元素“捆绑”成一个整体，看作一个大元素与其他元素进行排列；然后，再考虑被捆绑元素内部的排列顺序（乘法原理）。
• 经典例题：$7$ 名学生站成一排，甲、乙必须站在一起，有多少种不同的排法？
  • 解析：将甲、乙捆绑成一个元素，与其余 $5$ 人共 $6$ 个元素进行全排列，有 $A_6^6$ 种排法；甲、乙内部有 $A_2^2$ 种排法。因此总排法为： $$A_6^6 \times A_2^2 = 720 \times 2 = 1440 \text{ 种}$$

技巧2：不相邻问题 — 选空插入法（插空法）

• 适用场景：要求某些元素互不相邻。
• 方法：先将其余无限制的元素排好，产生若干个空档，再将不能相邻的元素选择合适的空档插入。
• 经典例题：$7$ 名学生站成一排，甲、乙互不相邻，有多少种不同的排法？
  • 解析：先排其余 $5$ 人，有 $A_5^5$ 种排法；排好后产生 $6$ 个空档（包含两端），从中选出 $2$ 个空档插入甲、乙，有 $A_6^2$ 种插法。总排法为： $$A_5^5 \times A_6^2 = 120 \times 30 = 3600 \text{ 种}$$

技巧3：复杂问题 — 总体排除法（排除法/余数法）

• 适用场景：直接分类讨论过于繁琐，但其对立面（反面情况）较易计算。
• 方法：总方案数 $-$ 不符合要求的方案数。
• 经典例题：从 $43$ 人中任抽 $5$ 人，正、副班长和团支部书记（共 $3$ 人）至少有一人在内的抽法有多少种？
  • 解析：从 $43$ 人中任意抽取 $5$ 人的总抽法为 $C_{43}^5$。反面情况为“这 $3$ 人都不在内”，即从其余 $40$ 人中抽取 $5$ 人，方案数为 $C_{40}^5$。因此至少有一人在内的抽法为： $$C_{43}^5 - C_{40}^5 \text{ 种}$$

技巧4：特殊元素/位置 — 优先考虑法

• 适用场景：某些元素或位置有特殊要求。
• 方法：优先安排有特殊要求的元素或位置，再去安排其他无限制的元素。
• 经典例题：乒乓球队 $10$ 名队员中有 $3$ 名主力，现派 $5$ 人参赛。 $3$ 名主力必须安排在第一、三、五位置，其余 $7$ 名队员中选 $2$ 名安排在第二、四位置，出场安排共有多少种？
  • 解析：优先安排特殊位置一、三、五，由 $3$ 名主力全排列，有 $A_3^3$ 种；再从其余 $7$ 人中选 $2$ 人排在二、四位置，有 $A_7^2$ 种。总出场安排为： $$A_3^3 \times A_7^2 = 6 \times 42 = 252 \text{ 种}$$

5. 多元问题 — 分类讨论法

• 适用场景：问题含有多种截然不同的情况，无法用单一公式概括。
• 方法：根据某一标准将问题划分为互斥的几类，分别求出各类的方案数，最后相加（加法原理）。

技巧6：混合问题 — 先选后排法

• 适用场景：既要组合（选出元素）又要排列（分配位置或顺序）。
• 方法：分步进行，通常先将需要用到的元素选出来（组合），再对选出的元素进行排列。
• 经典例题：从黄瓜、白菜、油菜、扁豆 $4$ 种蔬菜中选出 $3$ 种，分别种在不同土质的三块土地上，其中黄瓜必须种植，有多少种不同的种植方案？
  • 解析：第一步（选）：黄瓜必选，只需从其余 $3$ 种蔬菜中再选 $2$ 种，有 $C_3^2 = 3$ 种选法；第二步（排）：将选出的 $3$ 种蔬菜分配到三块土地上，有 $A_3^3 = 6$ 种排法。总方案数为： $$C_3^2 \times A_3^3 = 3 \times 6 = 18 \text{ 种}$$

技巧7：相同元素分配 — 隔板分隔法（插板法）

• 适用场景：将 $n$ 个相同的元素分给 $m$ 个不同的接收对象，每个对象至少分配到 $1$ 个元素。
• 方法：将 $n$ 个元素排成一列，中间会形成 $n-1$ 个空档。在这些空档中插入 $m-1$ 块隔板，将其分成 $m$ 份。方案数为： $$C_{n-1}^{m-1}$$
• 变形（每个对象可分配 $0$ 个元素）：设每个对象分得 $x_i \ge 0$，令 $y_i = x_i + 1 \ge 1$，相当于将 $n + m$ 个相同元素分给 $m$ 个不同对象且每个对象至少分到 $1$ 个，方案数为： $$C_{n+m-1}^{m-1}$$

技巧8：转化法

• 适用场景：问题表面上非常抽象、复杂，但可以通过等价替换转化为我们熟悉的排列组合模型（如插板法、路径网格等）。

6.2 常用组合原理

1. 容斥原理 (Inclusion-Exclusion Principle)

在计数时，为了保证不重复、不遗漏，可以先不考虑重叠情况，把所有对象的数目计算出来，然后再把重复计算的数目排除出去。

• 双集合容斥公式： $$|A \cup B| = |A| + |B| - |A \cap B|$$
• 三集合容斥公式： $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$$

2. 鸽巢原理 (Pigeonhole Principle)

也称抽屉原理，是组合数学中十分基础且强大的证明/计数工具。

• 基本形式 1：若将 $n+1$ 个物体放入 $n$ 个抽屉中，则至少有一个抽屉里有 $2$ 个或 $2$ 个以上的物体。
• 基本形式 2：若将 $m$ 个物体放入 $n$ 个抽屉中，则至少有一个抽屉里含有不少于 $\lceil \frac{m}{n} \rceil$ 个物体（其中 $\lceil \cdot \rceil$ 表示向上取整）。

6.3 逻辑推理与周期性问题

在逻辑推理中，周期性与状态规律是常见的考察方向：

1. 日历与星期问题：一星期有 $7$ 天的周期，计算若干天之后的星期只需对 $7$ 求模。对于极大的幂次（如 $10^{100}$ 天后），可以通过模算术和余数规律（同余分析）进行周期简化。
2. 坐标移动问题（步进螺旋）：移动方向通常按“上、右、下、左”或“前、后、左、右”进行循环。通常每 $4$ 步为一个周期，分析每个周期后坐标的净增量即可快速求解高阶步数后的坐标。
3. 流水线优化（Pipeline Scheduling）：在多人协作（如洗、切、炒菜）时，若工序之间存在依赖性且同一工序资源排他，可通过时间轴错开法（流水线设计）达到最短总耗时。

6.4 前缀、中缀与后缀表达式

表达式的求值与转换是数据结构与程序设计的重点。

1. 表达式的计算方法

后缀表达式计算（从左至右扫描）

1. 从左到右扫描表达式。
2. 遇到数字时，压入栈中。
3. 遇到运算符时，从栈中弹出两个数字，设栈顶为 $b$，次顶为 $a$（注意：先弹出的是右操作数，后弹出的是左操作数）。
4. 计算 $a \text{ [运算符] } b$，并将结果重新压入栈。
5. 扫描结束，栈顶元素即为最终结果。

前缀表达式计算（从右至左扫描）

1. 从右到左扫描表达式。
2. 遇到数字时，压入栈中。
3. 遇到运算符时，从栈中弹出两个数字，设栈顶为 $a$，次顶为 $b$（先弹出的是左操作数，后弹出的是右操作数）。
4. 计算 $a \text{ [运算符] } b$，并将结果重新压入栈。
5. 扫描结束，栈顶元素即为最终结果。

2. 表达式转换的 C++ 代码实现

以下提供一份通用的 C++ 代码，演示如何将常见的中缀表达式转换为后缀表达式并进行求值。

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <cctype>
#include <sstream>
#include <cmath>

using namespace std;

// 获取运算符优先级
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 执行基础四则运算
double calculate(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

// 中缀表达式转后缀表达式（支持多位数，以空格分隔）
string infixToPostfix(const string& infix) {
    stack<char> s;
    stringstream ss;

    for (size_t i = 0; i < infix.length(); ++i) {
        char c = infix[i];
        if (c == ' ') continue;

        // 如果是数字，完整提取多位数
        if (isdigit(c)) {
            while (i < infix.length() && (isdigit(infix[i]) || infix[i] == '.')) {
                ss << infix[i++];
            }
            ss << ' ';
            --i; // 修正指针
        }
        else if (c == '(') {
            s.push(c);
        }
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                ss << s.top() << ' ';
                s.pop();
            }
            if (!s.empty()) s.pop(); // 弹出 '('
        }
        else { // 运算符
            while (!s.empty() && getPriority(s.top()) >= getPriority(c)) {
                ss << s.top() << ' ';
                s.pop();
            }
            s.push(c);
        }
    }

    while (!s.empty()) {
        ss << s.top() << ' ';
        s.pop();
    }

    return ss.str();
}

// 后缀表达式求值
double evaluatePostfix(const string& postfix) {
    stack<double> s;
    stringstream ss(postfix);
    string token;

    while (ss >> token) {
        if (isdigit(token[0]) || (token.size() > 1 && token[0] == '-')) {
            s.push(stod(token));
        } else {
            double b = s.top(); s.pop();
            double a = s.top(); s.pop();
            s.push(calculate(a, b, token[0]));
        }
    }
    return s.top();
}

int main() {
    string infix = "3 + (4 * 5) - 6";
    string postfix = infixToPostfix(infix);
    cout << "中缀表达式: " << infix << endl;
    cout << "后缀表达式: " << postfix << endl;
    cout << "计算结果: " << evaluatePostfix(postfix) << endl;
    return 0;
}

6.5 练习题集

一、 选择题

1. 【NOIP 2019 普及组】 把 $8$ 个同样的球放在 $5$ 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（ ）

A. 22
B. 24
C. 18
D. 20

2. 【NOIP 2019 提高组】 一次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，并且有 $4$ 人语文、数学都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）

A. 23
B. 21
C. 20
D. 22

3. 【NOIP 2018 普及组】 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、A、S、D、F 的顺序循环按键（即 CapsLock, A, S, D, F, CapsLock, a, s, d, f, ...），屏幕上输出的第 $81$ 个字符是字母（ ）。

A. A
B. S
C. D
D. a

4. 【NOIP 2018 普及组】 设含有 $10$ 个元素的集合的全部子集数为 $S$，其中由 $7$ 个元素组成的子集数为 $T$，则 $T / S$ 的值为（ ）。

A. 5 / 32
B. 15 / 128
C. 1 / 8
D. 21 / 128

5. 【NOIP 2017 提高组】 将 $7$ 个相同的名额分给 $4$ 个不同的班级，允许有的班级没有名额，有（ ）种不同的分配方案。

A. 60
B. 84
C. 96
D. 120

6. 【NOIP 2017 普及组】 甲、乙、丙三位同学选修课程，从 $4$ 门课程中，甲选修 $2$ 门，乙、丙各选修 $3$ 门，则不同的选修方案共有（ ）种。

A. 36
B. 48
C. 96
D. 192

7. 【NOIP 2017 普及组】 表达式 a * (b + c) * d 的后缀形式是（ ）。

A. `abc d + * *`
B. `abc+ * d *`
C. `a * bc + * d`
D. `b + c * a * d`

8. 要从 $8$ 名男医生和 $7$ 名女医生中选 $5$ 人组成一个医疗队，如果其中至少有 $2$ 名男医生和至少有 $2$ 名女医生，则不同的选法种数为（ ）。

A. $(C_8^3 + C_7^2)(C_7^3 + C_8^2)$
B. $(C_8^3 + C_7^2) + (C_7^3 + C_8^2)$
C. $C_8^3 C_7^2 + C_7^3 C_8^2$
D. $C_8^3 C_7^2 C_{11}^1$

9. 从 $7$ 人中选出 $3$ 人分别担任学习委员、宣传委员、体育委员，则甲、乙两人不都入选的不同选法种数共有（ ）。

A. $C_5^3 A_3^3$
B. $C_5^3 A_3^3 + C_2^1 C_5^2 A_3^3$
C. $A_7^3 - A_5^3$
D. $C_5^3 A_3^3 + C_2^1 C_5^2 A_3^3 + C_2^2 A_3^3$

10. 三名教师教六个班的课，每人教两个班，分配方案共有（ ）种。

A. 18
B. 24
C. 45
D. 90

11. 对于给定的序列 ${a_k}$，我们把 $(i, j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$。那么序列 1, 7, 2, 3, 5, 4 的逆序对数为（ ）个。

A. 4
B. 5
C. 6
D. 7

12. 一家四口人，至少两个人生日属于同一月份的概率是（ ）。（假定每个人生日属于每个月份的概率相同且不同人之间相互独立）

A. $1/12$
B. $1/144$
C. $41/96$
D. $3/4$

13. 如果 256 种颜色用二进制编码来表示，至少需要（ ）位。

A. 6
B. 7
/C. 8
D. 9

14. 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（ ）种放法。

A. 7
B. 8
C. 21
D. 37

二、 填空与解答题

15. 按下列条件，从 12 人中选出 5 人，有多少种不同选法？

1. 甲、乙、丙三人必须当选；
2. 甲、乙、丙三人不能当选；
3. 甲必须当选，乙、丙不能当选；
4. 甲、乙、丙三人只有一人当选；
5. 甲、乙、丙三人至多 2 人当选；
6. 甲、乙、丙三人至少 1 人当选。

16. 在 100 件产品中有 98 件合格品，2 件次品。产品检验时，从 100 件产品中任意抽出 3 件：

1. 一共有多少种不同的抽法？
2. 抽出的 3 件中恰好有 1 件是次品的抽法有多少种？
3. 抽出的 3 件中至少有 1 件是次品的抽法有多少种？
4. 抽出的 3 件中至多有 1 件是次品的抽法有多少种？
5. 抽出的 3 件都是合格品的抽法有多少种？
6. 抽出的 3 件中有 2 件不合格的抽法有多少种？

17. 某医院有内科医生 12 名，外科医生 8 名，现要派 5 人参加支边医疗队：

1. 某内科医生甲与某外科医生乙必须参加，共有多少种不同选法？
2. 甲、乙均不能参加，有多少种选法？
3. 甲、乙两人至少有一人参加，有多少种选法？
4. 医疗队中至少有一名内科医生和一名外科医生，有几种选法？

18. 某兴趣小组有 4 名男生，5名女生：

1. 从中选派 5 名学生参加一次活动，要求必须有 2 名男生、3 名女生，且女生甲必须在内，有多少种选派方法？
2. 从中选派 5 名学生参加一次活动，要求有女生但人数必须少于男生，有多少种选派方法？
3. 分成三组，每组 3 人，有多少种不同分法？

19. 某城新建的一条道路上有 12 盏路灯，为了节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有多少种？

20. 3 名医生和 6 名护士被分配到 3 所学校为学生体检，每校分配 1 名医生和 2 名护士，不同的分配方法共有多少种？

21. 从 6 个学校中选出 30 名学生参加数学竞赛，每校至少有 1 人，这样有几种选法？

22. 将 8 个学生干部的培训指标分配给 5 个不同的班级，每班至少分到 1 个名额，共有多少种不同的分配方法？

23. 把 6 个学生分到一个工厂的三个车间实习，每个车间 2 人。若甲必须分到一车间，乙和丙不能分到二车间，则不同的分法有多少种？

24. 从 6 位同学中选出 4 位参加一个座谈会，要求张、王两人中至多有一个人参加，则不同的选法种数为多少？

25. 有 9 本不同的课外书，分给甲、乙、丙三名同学，求在下列条件下，各有多少种不同的分法？

1. 甲得 4 本，乙得 3 本，丙得 2 本；
2. 一人得 4 本，一人得 3 本，一人得 2 本；
3. 甲、乙、丙各得 3 本。

26. 1 名老师和 4 名获奖学生排成一排照相留念，若老师不排在两端，则共有不同的排法多少种？

27. 从一个 $4\times 4$ 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有多少种方法？

28. 重新排列 1234 使得每一个数字都不在原来的位置上，一共有多少种排法？

29. 把 $M$ 个同样的球放到 $N$ 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？（用 $K$ 表示）

例如，$M = 7$，$N = 3$ 时，$K = 8$。问：$M = 8$，$N = 5$ 时，$K = $ _____

30. 7 个同学围坐一圈，要选 2 个不相邻的作为代表，有多少种不同的选法？

6.6 练习题答案与详细解析

一、 选择题

1. 【答案】C

• 解析：由于袋子和球均没有区别（“同样”的球与“同样”的袋子），本题属于无区别球放入无区别盒的整数划分问题。 将 8 分成至多 5 个非负整数的和，分类讨论如下：
  • 分到 1 个袋子：$(8)$ $\rightarrow 1$ 种
  • 分到 2 个袋子：$(7,1), (6,2), (5,3), (4,4)$ $\rightarrow 4$ 种
  • 分到 3 个袋子：$(6,1,1), (5,2,1), (4,3,1), (4,2,2), (3,3,2)$ $\rightarrow 5$ 种
  • 分到 4 个袋子：$(5,1,1,1), (4,2,1,1), (3,3,1,1), (3,2,2,1), (2,2,2,2)$ $\rightarrow 5$ 种
  • 分到 5 个袋子：$(4,1,1,1,1), (3,2,1,1,1), (2,2,2,1,1)$ $\rightarrow 3$ 种
  • 合计：$1 + 4 + 5 + 5 + 3 = 18$ 种。故选 C。

2. 【答案】A

• 解析：利用容斥原理（双集合求并集）。 设数学满分人数为集合 $A$，语文满分人数为集合 $B$。 $$|A \cup B| = |A| + |B| - |A \cap B| = 15 + 12 - 4 = 23 \text{ 人}$$ 故选 A。

3. 【答案】A

• 解析：观察输出字符的循环规律。 按键顺序为：CapsLock、A、S、D、F。 由于 CapsLock 改变大小写状态，一个完整周期内按键两次 CapsLock，状态恢复初始。

  • 第 1 次按键：CapsLock（切换至大写状态），不输出字符。
  • 第 2~5 次：输出 A, S, D, F（大写）。
  • 第 6 次按键：CapsLock（切换回小写状态），不输出。
  • 第 7~10 次：输出 a, s, d, f（小写）。

  可以看出，一个完整的字符输出周期包含 8 个输出字符（A S D F a s d f），对应 10 次按键。 求第 81 个输出字符： $$81 \pmod 8 = 1$$ 因此第 81 个字符与周期的第 1 个输出字符一致，为大写的 A。故选 A。

4. 【答案】B

• 解析：
  • $10$ 个元素集合的所有子集总数（包括空集）：$S = 2^{10} = 1024$。
  • 由 $7$ 个元素组成的子集数：$T = C_{10}^7 = C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$。
  • 比值 $T / S = 120 / 1024 = 15 / 128$。故选 B。

5. 【答案】D

• 解析：允许有的班级没有名额，属于相同元素分配给不同对象且允许为空的模型（可利用隔板法变形求解）。 设 4 个班分得的名额分别为 $x_1, x_2, x_3, x_4 \ge 0$，且 $x_1 + x_2 + x_3 + x_4 = 7$。 令 $y_i = x_i + 1 \ge 1$，则 $y_1 + y_2 + y_3 + y_4 = 7 + 4 = 11$。 相当于将 11 个相同名额分配给 4 个班，每班至少 1 个。用隔板法： 在 10 个空档中插入 3 块隔板，方案数为： $$C_{10}^3 = \frac{10 \times 9 \times 8}{6} = 120 \text{ 种}$$ 故选 D。

6. 【答案】C

• 解析：利用乘法原理独立计算三人的选课方案。
  • 甲：从 4 门中选 2 门，方案数为 $C_4^2 = 6$ 种；
  • 乙：从 4 门中选 3 门，方案数为 $C_4^3 = 4$ 种；
  • 丙：从 4 门中选 3 门，方案数为 $C_4^3 = 4$ 种。
  • 总方案数：$6 \times 4 \times 4 = 96$ 种。故选 C。

7. 【答案】B

• 解析：中缀表达式为 a * (b + c) * d。按照运算优先级：
  1. 先算括号内的 b + c $\rightarrow$ 后缀为 bc+。
  2. 再算左侧乘法 a * (bc+) $\rightarrow$ 后缀为 abc+*。
  3. 最后计算右侧乘法 (abc+*) * d $\rightarrow$ 后缀为 abc+*d*。 故选 B。

8. 【答案】C

• 解析：一共选 5 人，要求男医生 $\ge 2$，女医生 $\ge 2$。因此只有以下两种情况：
  • 情况 1：3 男 2 女。选法为 $C_8^3 C_7^2$ 种；
  • 情况 2：2 男 3 女。选法为 $C_8^2 C_7^3$ 种（即 $C_7^3 C_8^2$）。
  • 由加法原理，总选法为两情况之和：$C_8^3 C_7^2 + C_7^3 C_8^2$。故选 C。

9. 【答案】D

• 解析：从 7 人中选出 3 人分配 3 个不同职位（排列问题）。 要求“甲、乙两人不都入选”，即排除“甲、乙均入选”的情况：
  • 方法一（分类讨论）：
    1. 甲、乙均未入选：从余下 5 人中选 3 人并排列，有 $C_5^3 A_3^3$ 种；
    2. 甲、乙仅一人入选：先选出那个人（$C_2^1$ 种），再从其余 5 人中选 2 人，最后 3 人全排列，有 $C_2^1 C_5^2 A_3^3$ 种。
    3. 总和为：$C_5^3 A_3^3 + C_2^1 C_5^2 A_3^3$。这与选项 B/D 中的部分项吻合。
  • 方法二（排除法）： 总选法为 $A_7^3$。甲、乙均入选的选法：先选定甲乙，再从余下 5 人中选 1 人（共 $C_5^1 = 5$ 种组合），然后这 3 人全排列（$A_3^3 = 6$ 种），即 $5 \times 6 = 30$ 种。 总数 $= A_7^3 - C_5^1 A_3^3 = 210 - 30 = 180$ 种。 验证 D 选项：$2 C_2^3 A_3^3$ 等公式在原教材 OCR 中有微调，标准结果应为 $180$ 种。

10. 【答案】D

• 解析：本题属于不同元素的均匀分组与分配问题。
  1. 首先将 6 个班均匀分成三组（每组 2 个班）： $$\frac{C_6^2 C_4^2 C_2^2}{3!} = \frac{15 \times 6 \times 1}{6} = 15 \text{ 种}$$
  2. 再将这三组分配给 3 名教师： $$15 \times A_3^3 = 15 \times 6 = 90 \text{ 种}$$ 故选 D。

11. 【答案】C

• 解析：逆序对即前数大于后数。直接扫描序列 1, 7, 2, 3, 5, 4：
  • 对 7：后面比它小的有 2, 3, 5, 4 $\rightarrow 4$ 个逆序对；
  • 对 5：后面比它小的有 4 $\rightarrow 1$ 个逆序对；
  • 其余元素均无逆序对。
  • 总逆序对数：$4 + 1 = 5$ 个。故选 B。

12. 【答案】C

• 解析：
  • 4 个人生日月份全不相同的概率为： $$\frac{A_{12}^4}{12^4} = \frac{12 \times 11 \times 10 \times 9}{12 \times 12 \times 12 \times 12} = \frac{55}{96}$$
  • 至少有两人生日属于同一月份的概率（反面法）： $$1 - \frac{55}{96} = \frac{41}{96}$$ 故选 C。

13. 【答案】C

• 解析：设需要 $x$ 位二进制。 $$2^x \ge 256 \implies x \ge 8$$ 故选 C。

14. 【答案】B

• 解析：同第 1 题模型，7 个相同苹果放入 3 个相同盘子，允许空：
  • 用 1 个盘子：$(7,0,0) \rightarrow 1$ 种；
  • 用 2 个盘子：$(6,1,0), (5,2,0), (4,3,0) \rightarrow 3$ 种；
  • 用 3 个盘子：$(5,1,1), (4,2,1), (3,3,1), (3,2,2) \rightarrow 4$ 种。
  • 合计：$1 + 3 + 4 = 8$ 种。故选 B。

二、 填空与解答题

15. 【答案与解析】

1. 36 种。
   • 解析：甲、乙、丙必选，只需从余下 9 人中选 2 人：$C_9^2 = 36$。
2. 126 种。
   • 解析：甲、乙、丙不选，从余下 9 人中选 5 人：$C_9^5 = 126$。
3. 126 种。
   • 解析：甲必选（占 1 名额），乙、丙不选。只需从余下 9 人中选 4 人：$C_9^4 = 126$。
4. 378 种。
   • 解析：从甲、乙、丙中选 1 人（$C_3^1 = 3$ 种），其余 4 人从余下 9 人中选（$C_9^4 = 126$ 种）。总数：$3 \times 126 = 378$。
5. 756 种。
   • 解析（排除法）：总情况减去“3人都选”：$C_{12}^5 - C_3^3 C_9^2 = 792 - 36 = 756$。
6. 666 种。
   • 解析（排除法）：总情况减去“3人都没选”：$C_{12}^5 - C_9^5 = 792 - 126 = 666$。

16. 【答案与解析】

1. 161700 种。
   • 解析：从 100 件中任抽 3 件：$C_{100}^3 = 161700$。
2. 9506 种。
   • 解析：1件次品（$C_2^1$），2件合格品（$C_{98}^2$）：$2 \times 4753 = 9506$。
3. 9604 种。
   • 解析（排除法）：总数减去“全是合格品”：$C_{100}^3 - C_{98}^3 = 161700 - 152096 = 9604$。
4. 161602 种。
   • 解析：含0件次品（$C_{98}^3$）或1件次品（$C_2^1 C_{98}^2$）：$152096 + 9506 = 161602$。
5. 152096 种。
   • 解析：从 98 件合格品中选 3 件：$C_{98}^3 = 152096$。
6. 98 种。
   • 解析：2件次品必选（$C_2^2 = 1$），再选1件合格品（$C_{98}^1 = 98$）：$1 \times 98 = 98$。

17. 【答案与解析】

1. 816 种。
   • 解析：甲、乙必去，只需从余下 18 人中选 3 人：$C_{18}^3 = 816$。
2. 8568 种。
   • 解析：甲、乙均不去，从余下 18 人中选 5 人：$C_{18}^5 = 8568$。
3. 6936 种。
   • 解析（排除法）：总人数中任选 5 人的方法减去甲、乙都不参加的方法： $$C_{20}^5 - C_{18}^5 = 15504 - 8568 = 6936$$
4. 14656 种。
   • 解析（排除法）：总选法减去“全是内科”和“全是外科”的选法： $$C_{20}^5 - C_{12}^5 - C_8^5 = 15504 - 792 - 56 = 14656$$

18. 【答案与解析】

1. 36 种。
   • 解析：女生甲必在内，需再从其余 4 名女生中选 2 人（$C_4^2 = 6$），从 4 名男生中选 2 人（$C_4^2 = 6$）。方案数：$6 \times 6 = 36$。
2. 45 种。
   • 解析：女生人数少于男生且女生 $\ge 1$：
     • 1女4男：$C_5^1 C_4^4 = 5 \times 1 = 5$ 种；
     • 2女3男：$C_5^2 C_4^3 = 10 \times 4 = 40$ 种。
     • 合计：$5 + 40 = 45$ 种。
3. 280 种。
   • 解析：9 人均匀分成三组（无序）： $$\frac{C_9^3 C_6^3 C_3^3}{3!} = \frac{84 \times 20 \times 1}{6} = 280$$

19. 【答案】56 种

• 解析：利用插空法。亮的 9 盏灯排成一排，在两端不能熄灭的前提下，9 盏灯中间会产生 8 个空档。将熄灭的 3 盏灯插入这 8 个空档中，即可保证不相邻且不在两端： $$C_8^3 = \frac{8 \times 7 \times 6}{6} = 56 \text{ 种}$$

20. 【答案】540 种

• 解析：分步处理：
  1. 分配 3 名医生到 3 所学校：$A_3^3 = 6$ 种。
  2. 将 6 名护士分组，每组 2 人并分配到 3 所学校： $$C_6^2 C_4^2 C_2^2 = 15 \times 6 \times 1 = 90 \text{ 种}$$
  3. 总分配方案数：$6 \times 90 = 540$ 种。

21. 【答案】118755 种 (或 4095)

• 解析：
  • 数学标准解：将 30 个相同的竞赛名额分配给 6 个不同的学校，每校至少 1 人（隔板法）： $$C_{29}^5 = \frac{29 \times 28 \times 27 \times 26 \times 25}{120} = 118755 \text{ 种}$$
  • 注：在部分参考讲义和 PPT 中，因套用模板排版产生笔误将该组合数错写为 $4095$。若在应试中遇到该历史原题，请留意此背景。

22. 【答案】35 种

• 解析：8 个相同指标分给 5 个不同班级，每班至少 1 个（隔板法）： $$C_{7}^4 = 35 \text{ 种}$$

23. 【答案】9 种

• 解析：
  1. 由于二车间不能安排乙、丙和甲（甲在一车间），因此二车间只能从剩下的 $6 - 3 = 3$ 人中选择 2 人：$C_3^2 = 3$ 种。
  2. 一车间已确定有甲，还需在剩下的 3 人中选 1 人：$C_3^1 = 3$ 种。
  3. 余下的 2 人自动进入三车间。
  4. 总方案数：$C_3^2 \times C_3^1 = 3 \times 3 = 9$ 种。

24. 【答案】9 种

• 解析（排除法）： 从 6 人中任意选 4 人的总选法为 $C_6^4 = 15$。张、王两人均参加的选法为：张王必选，再从余下 4 人选 2 人，即 $C_4^2 = 6$。 $$15 - 6 = 9 \text{ 种}$$

25. 【答案与解析】

1. 1260 种。
   • 解析：分步分配：甲拿 $C_9^4 = 126$ 种，乙拿 $C_5^3 = 10$ 种，丙拿 $C_2^2 = 1$ 种。总数：$126 \times 10 \times 1 = 1260$。
2. 7560 种。
   • 解析：先分组（4，3，2 组合）：$C_9^4 C_5^3 C_2^2 = 1260$。因为人是不同的，将三组书分配给甲、乙、丙三人：$1260 \times A_3^3 = 7560$。
3. 1680 种。
   • 解析：甲拿 $C_9^3 = 84$ 种，乙拿 $C_6^3 = 20$ 种，丙拿 $C_3^3 = 1$ 种。总数：$84 \times 20 = 1680$。

26. 【答案】72 种

• 解析：老师不能站在首尾。
  1. 安排老师：从中间的 3 个位置选 1 个：$C_3^1 = 3$ 种。
  2. 安排学生：其余 4 人在剩余 4 个位置全排列：$A_4^4 = 24$ 种。
  3. 总排法：$3 \times 24 = 72$ 种。

27. 【答案】72 种

• 解析：
  1. 选择第一个方格：共有 16 种选法。
  2. 选定后，它所在的行（4个）和列（4个）均不能再选，剩余可选方格数为 $(4-1)\times (4-1) = 9$ 个。
  3. 由于选取的两个方格没有顺序区别，需除以 2： $$\frac{16 \times 9}{2} = 72 \text{ 种}$$

28. 【答案】9 种

• 解析：此题为 $4$ 个元素的全错位排列问题（Derangement）。 由错排递推公式：$D_n = (n-1)(D_{n-1} + D_{n-2})$。 已知 $D_1 = 0, D_2 = 1, D_3 = 2$： $$D_4 = 3 \times (2 + 1) = 9 \text{ 种}$$

29. 【答案】18

• 解析：当 $M = 8, N = 5$ 时，求将 8 分裂为至多 5 个非负整数的和的数量，即为练习一中第 1 题的逆向求解。结果为 18。

30. 【答案】14 种

• 解析（排除法）： 从 7 人中任意选 2 人的方案数为 $C_7^2 = 21$。两人相邻的方案数（即圆周上的相邻边数）为 7。 $$21 - 7 = 14 \text{ 种}$$

6.7 核心算法题 C++ 代码实现

1. 错排问题计算器（对应第 28 题）

#include <iostream>
#include <vector>

using namespace std;

// 计算 n 个元素的错排数
long long getDerangement(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;

    vector<long long> dp(n + 1, 0);
    dp[1] = 0;
    dp[2] = 1;

    for (int i = 3; i <= n; ++i) {
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
    }
    return dp[n];
}

int main() {
    int n = 4;
    cout << n << "个元素的错排方案数为: " << getDerangement(n) << " 种" << endl;
    return 0;
}

2. 整数划分（球盒问题）动态规划求解（对应第 29 题）

#include <iostream>
#include <vector>

using namespace std;

// 将 m 个相同的球放入 n 个相同的盒子的方案数（允许空）
int countPartitions(int m, int n) {
    // dp[i][j] 表示将整数 i 划分为至多 j 个正整数之和的方案数
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int j = 0; j <= n; ++j) {
        dp[0][j] = 1; // 划分 0 只有 1 种方法（全为0）
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i < j) {
                // 如果球数少于盒子数，多出的盒子没有影响
                dp[i][j] = dp[i][i];
            } else {
                // 两种决策：至少有一个空盒子 (dp[i][j-1]) 或 每个盒子都至少有一个球 (dp[i-j][j])
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        }
    }
    return dp[m][n];
}

int main() {
    int M = 8;
    int N = 5;
    cout << "将 " << M << " 个相同的球放入 " << N << " 个相同的盒子，一共有: " 
         << countPartitions(M, N) << " 种放法。" << endl;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com