欢迎来到数学预备知识！
欢迎踏上离散数学 (Discrete Mathematics) 的旅程！如果你已经习惯了微积分或函数那种「平滑」的数学，离散数学可能会让你感到一点点不同。我们不再研究连续的曲线，而是关注一个个独立、分开的对象——例如，计算书架上排列图书的方法，或是为送货司机寻找最短路线。
如果这些概念起初让你觉得有些抽象，别担心。这一章就是你的「工具箱」。我们将学习基础的术语和计数技巧，让这门课程的余下部分变得轻松许多。让我们开始吧！
1. 四大类问题
在离散数学中，你遇到的几乎所有问题都会归类为以下四种之一。你可以把这些看作是你的数学任务目标。
存在性 (Existence)
解是否存在？在你花费数小时尝试安排完美的日程或规划路线之前，你首先要问：「这真的可能实现吗？」
构造性 (Construction)
如果解存在，我们该如何构建它？这涉及创建一个逐步解决问题的方法（即算法 (Algorithm)）来得出结果。
计数 (Enumeration)
有多少种解法？这纯粹是关于「计数」。我们不需要列出所有解法，只需要知道可能性的总数。（例如：「我可以创建多少种不同的 4 位数 PIN 码？」）
优化 (Optimisation)
如果存在多个解，哪一个才是「最好」的？通常这意味着找到成本最低、速度最快或距离最短的方案。
快速回顾：
• 存在性： 是否可能？
• 构造性： 我该如何做到？
• 计数： 有多少种方法？
• 优化： 哪种方法最好？
2. 集合与划分
集合 (Set) 只是一组对象（称为元素）的集合。在本章中，我们重点关注划分 (Partition)。
什么是划分？
想象你有 10 颗不同的弹珠，想把它们放入三个小盒子里。要成为真正的划分，必须遵循两条规则：
1. 每颗弹珠都必须放入盒子里（不能有弹珠被遗漏）。
2. 同一时间内，没有弹珠可以同时位于多于一个盒子内。
类比： 想象一所学校。每个学生都会被分配到一个「学院」（如格兰芬多或拉文克劳）。由于每个学生都有所属学院，且没有学生同时身处两个学院，这些学院就构成了学校人口的划分。
常见错误： 忘记了划分必须包含所有内容。如果你将数字集合 {1, 2, 3, 4, 5} 分为 {1, 2} 和 {4, 5}，这不是一个划分，因为你遗漏了数字 3！
3. 鸽巢原理 (Pigeonhole Principle)
这是一个非常强大且易于理解的法则。
规则： 如果你有 \(n\) 个物品要放入 \(m\) 个容器中，且 \(n > m\)，那么至少有一个容器必定包含超过一个物品。
例子： 如果有 8 只鸽子但只有 7 个鸽巢，那么至少有一个巢内会有 2 只或以上的鸽子。
你知道吗？ 在像伦敦这样的城市里，绝对至少有两个人头上的头发数量是完全相同的！为什么？因为人类头上最多约有 15 万根头发，但伦敦却有数百万人口。鸽子 = 人；巢 = 头发数量。
重点提示： 当你需要证明「碰撞」或「重叠」必然会发生时，请使用鸽巢原理。
4. 计数：排列与选择
这是课程中关于「计数」的部分。它能帮助我们计算大量的可能性，而无需逐一列出。
乘法原理 (Multiplicative Principle)
如果你必须进行一系列的选择，只需将每个选择的可行选项数量相乘。
例子： 如果你有 3 件衬衫和 4 条裤子，你就有 \(3 \times 4 = 12\) 种可能的搭配。
排列 (Permutations) (顺序很重要！)
排列是有序的组合。当序列很重要时使用此方法，例如比赛结果或密码。
排列 \(n\) 个不同对象的方法数为 \(n!\)（n 的阶乘）。
\(n! = n \times (n-1) \times (n-2) \times ... \times 1\)。
如果你从 \(n\) 个对象中选取 \(r\) 个，且顺序很重要，我们使用以下符号：
\(nPr = \frac{n!}{(n-r)!}\)
组合 (Combinations) (顺序不重要！)
组合是一种选取方式，其中顺序不重要。想象选拔一支队伍或选择披萨配料。
如果你从 \(n\) 个对象中选取 \(r\) 个，且顺序不重要，我们使用以下符号：
\(nCr = \frac{n!}{r!(n-r)!}\)
记忆小撇步：
• Permutation (排列) = Place (位置/顺序) 很重要。
• Combination (组合) = Choice (纯粹的选择，顺序不重要)。
处理限制条件
有时候题目会增加「规则」，例如「两个 2 不能相邻」。
1. 重复： 如果有相同的物品（例如 "APPLE" 中的字母），你需要用总排列数除以重复物品数量的阶乘。以 APPLE 为例：\(\frac{5!}{2!}\)，因为当中有两个 'P'。
2. 限制： 如果两个物品不能在一起，最简单的方法通常是算出总排列数，然后减去它们在一起的排列数。
5. 排容原理 (Inclusion-Exclusion Principle)
计算两个不同群组的总数时，我们有时会不小心把「重叠」部分的人重复计算了。这个原理能解决这个问题。
对于两个集合 \(A\) 和 \(B\)，属于 \(A\) 或 \(B\) 的元素总数（并集）为：
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
类比： 如果 10 个学生参加足球队 (\(A\))，12 个参加篮球队 (\(B\))，其中 3 个两者都参加，请问有多少个学生参与运动？
答案不是 \(10 + 12 = 22\)，因为那 3 个学生在两个群组中都被计算了一次！
正确答案：\(10 + 12 - 3 = 19\)。
快速回顾： 务必减去交集 (\(A \cap B\))，这样才不会重复计算重叠的部分！
总结：章节重点
• 离散 (Discrete) 指的是分开的对象，而非平滑的线条。
• 使用 nPr 进行排列（顺序重要），使用 nCr 进行选择（顺序不重要）。
• 阶乘 (\(n!\)) 用于将所有对象按顺序排列。
• 鸽巢原理证明了当「鸽子」数量多于「巢」的数量时，重叠必然发生。
• 划分将一个集合拆分为互不重叠且包含所有成员的部分。