欢迎来到数学预备知识！
欢迎来到离散数学 (Discrete Mathematics) 的世界！与你在微积分中接触过处理“平滑”对象（如曲线）的数学不同，离散数学专注于“离散”或“可数”的对象。你可以把它想象成斜坡（连续）与楼梯（离散）之间的差别。
在本章中，我们要建立你的“工具箱”。这些预备知识是计算和组织对象的基本规则。它们乍看之下可能很简单，但它们却是计算机科学、日程安排，甚至是玩桌上游戏获胜背后的秘密引擎！
1. 四类问题
在离散数学中，你面临的几乎所有挑战都属于这四类（或多类）之一。厘清你处理的是哪一类问题，就已经成功了一半！
A. 存在性 (Existence)：这能做到吗？这是在询问是否真的存在解决方案。例子：我们可以用四种颜色为地图着色，使得没有两个相邻的国家颜色相同吗？
B. 构造性 (Construction)：我们该如何做？如果存在解决方案，这就是构建它的步骤说明。例子：画出上述提到的地图颜色。
C. 枚举 (Enumeration)：有多少种方法？这是“计数”的核心。例子：你可以用多少种不同的方式为该地图着色？
D. 最优化 (Optimisation)：什么是“最好”的方法？通常这意味着找到最短、最快或最便宜的解决方案。例子：快递员访问十个地点的最快路线是什么？
关键要点：
在你开始解题前，问问自己：“我是要找出这‘是否’可能（存在性）、‘如何’去做（构造性）、‘有多少’方法（枚举），还是‘最好’的方法（最优化）？”
2. 集合与划分的语言
集合 (Set) 只是对象的集合（例如一组数字或一组学生）。要掌握这一章，你需要理解划分 (Partitions)。
一个集合的划分意味着将它拆分成更小的“堆”（子集），使得：
1. 原始集合中的每一项都在某个堆中。
2. 没有任何项目位于多于一个堆中（没有重叠）。
3. 没有一个堆是空的。
类比：如果你有一副扑克牌并按花色（红心、方块、黑桃、梅花）分组，你就创建了这副牌的一个划分。每一张牌都有归宿，且没有一张牌既是红心又是黑桃。
计算划分：有时你需要计算划分一个集合的方法数。例如，如果你有 3 本不同的书，想把它们放入 2 个非空的堆中，你可以有（书 A）和（书 B, C），或（书 B）和（书 A, C），或（书 C）和（书 A, B）。这就是 3 种方法！
3. 鸽笼原理 (Pigeonhole Principle)
这是数学中最著名（也最有趣！）的规则之一。如果它听起来太简单也不要担心——它的强大之处在于你如何应用它。
规则：如果你有 \(n+1\) 只鸽子和只有 \(n\) 个鸽笼，那么至少有一个鸽笼必然包含多于一只鸽子。
现实例子：如果房间里有 13 个人，那么至少有两个个人必然在同一个月份出生。为什么？因为只有 12 个月份（“笼子”）而有 13 个人（“鸽子”）。
快速回顾：要在问题中使用此原理，请找出你的“鸽子”（你要分配的对象）以及你的“笼子”（它们进入的类别）。
4. 乘法原理 (Multiplicative Principle)
这是计数的“黄金法则”。
如果你有 'a' 种方法做一件事，以及 'b' 种方法做另一件事，那么同时做这两件事就有 \(a \times b\) 种方法。
例子：如果一家咖啡厅提供 3 种三明治和 4 种饮料，你能组成多少种午餐搭配？
答案：\(3 \times 4 = 12\) 种搭配。
对象排列：如果你有 \(n\) 个不同 (distinct) 的对象，你想把它们全部排成一行，方法数就是 \(n!\) (n 的阶乘)。
\(n! = n \times (n-1) \times (n-2) \times ... \times 1\)。
例子：将 5 本不同的书排列在书架上？\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\) 种方法。
5. 排列 (Permutations) 与组合 (Combinations)
这是许多学生卡关的地方，但这里有一个区分它们的简单技巧：
排列 (\(_nP_r\))：顺序很重要 (MATTERS)。记住“P”代表“Position”（位置）。
当你为特定职位选人（如金、银、铜牌）时使用此法。
公式：\(_nP_r = \frac{n!}{(n-r)!}\)
组合 (\(_nC_r\))：顺序不重要 (DOES NOT matter)。记住“C”代表“Committee”（委员会）。
当你只是挑选一个大家地位平等的小组（如选 3 个朋友去看电影）时使用此法。
公式：\(_nC_r = \frac{n!}{r!(n-r)!}\)
你知道吗？
“密码锁 (combination lock)”实际上应该被称为“排列锁 (permutation lock)”，因为数字的顺序是有影响的！
6. 带限制的排列
有时情况并不简单，我们会有限制条件。以下是两种常见情境：
A. 重复（相同对象）
如果你要排列单词中的字母，而其中一些字母相同，你必须除以重复部分的阶乘。
例子：排列“EGG”中的字母有多少种方法？
字母总数 = 3。重复的 'G' 有 2 个。
答案：\(\frac{3!}{2!} = \frac{6}{2} = 3\) 种方法 (EGG, GEG, GGE)。
B. 限制（“不在一起”）
如果有两个人，Alice 和 Bob，他们拒绝在 5 个人的队伍中站在一起，请使用空隙法 (Gap Method)：
1. 先排列其余 3 个人 (\(3!\))。
2. 观察他们周围的空隙：_ P1 _ P2 _ P3 _（共有 4 个空隙）。
3. 为 Alice 和 Bob 选择 2 个空隙坐下 (\(_4P_2\))。
4. 将它们相乘：\(3! \times \text{}_4P_2\)。
7. 容斥原理 (Inclusion-Exclusion Principle)
在计算小组内的事物时，如果有些人属于两个小组，我们经常会不小心重复计算。我们使用此原理来修正这个问题。
对于两个集合 (A 和 B)：
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
翻译：（A 或 B 的总数）=（A 的数量）+（B 的数量）-（两者皆有的数量）。
对于三个集合：
规律是加、减、加：
1. 加上单个集合。
2. 减去重叠的两两组合。
3. 加回三重重叠（韦恩图的中心）。
常见错误：
忘记减去交集！如果 10 个人喜欢苹果，10 个人喜欢橙子，而 2 个人两者都喜欢，总共只有 18 个人 (\(10+10-2\))，而不是 20 人。
8. 错排 (Derangements)
错排 (Derangement)（记作 \(D_n\)）是一种特殊的排列，其中没有任何东西在原本的位置上。
例子：“秘密圣诞老人”问题。如果 3 个人 (A, B 和 C) 互相购买礼物，错排是指没有人拿到自己的礼物的情况。
可能的错排：（B 拿到 A 的，C 拿到 B 的，A 拿到 C 的）或（C 拿到 A 的，A 拿到 B 的，B 拿到 C 的）。
所以，\(D_3 = 2\)。
对于考试，你通常使用特定方法 (ad hoc methods) 来求这些值——这是一种高级的说法，意指对于小数量的项目“仔细列举出来”。
快速回顾区
• 挑选一个团队？使用 \(_nC_r\)。
• 挑选主席和副主席？使用 \(_nP_r\)。
• 对象必须分开？使用空隙法。
• 重叠的小组？使用容斥原理。
• 没有东西在正确的位置？那是错排 (\(D_n\))。