歡迎來到數學預備知識！
歡迎來到離散數學 (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\))。