歡迎來到數學預備知識！
歡迎踏上離散數學 (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!\)) 用於將所有對象按順序排列。
• 鴿巢原理證明了當「鴿子」數量多於「巢」的數量時，重疊必然發生。
• 劃分將一個集合拆分為互不重疊且包含所有成員的部分。