Probability (including counting) concepts

歡迎來到 H3 概率與計數！

你好！如果你正在閱讀這份筆記，說明你已經掌握了 H2 數學的基礎。在 H3 中，我們將在這些基礎上加入一些強大的「邏輯工具」，幫助你解決那些曾經看似無法破解的計數難題。把這一章想像成是為你的數學工具箱升級精密儀器。我們將探討雙射原理 (Bijection Principle) 和容斥原理 (Inclusion-Exclusion Principle)。別被這些聽起來很高級的名稱嚇到了，它們其實都是基於我們日常生活中非常簡單的邏輯！

1. 雙射原理：透過映射進行計數

有時候，直接計算集合中的對象非常困難。雙射原理指出，如果你能找到一種方法，將集合 A 中的每一個項目與集合 B 中的每一個項目進行完美的一對一匹配（兩邊都沒有剩餘），那麼集合 A 和集合 B 的項目數量必然相等。

類比：想像一個擠滿人的電影院。與其四處走動數人頭，你可以直接數已佔用的座位數。如果每個人都剛好有一個座位，且沒有人共用座位，那麼人數就等於已佔用的座位數。這就是一個雙射 (bijection)！

將不可區分的對象分配到可區分的盒子中

這是一個經典的 H3 問題。假設你有 10 個相同的蘋果（不可區分），想把它們分給 3 個朋友（可區分：Alice、Bob 和 Charlie）。有多少種分法？

我們使用一種稱為「隔板法」(Stars and Bars) 的方法。

步驟說明：
1. 將 10 個蘋果表示為星星：★ ★ ★ ★ ★ ★ ★ ★ ★ ★
2. 為了將這些星星分給 3 個人，我們需要 2 個「隔板」( | )。例如：★ ★ | ★ ★ ★ ★ ★ | ★ ★ ★
3. 在這個例子中，Alice 得到 2 個，Bob 得到 5 個，Charlie 得到 3 個。
4. 「分配蘋果」的問題現在就完全等同於（這就是雙射！）「排列 10 顆星星和 2 個隔板」的問題。

公式：
如果你有 \(n\) 個相同的項目和 \(r\) 個不同的盒子，分配它們的方法數為：
\( \binom{n + r - 1}{r - 1} \) 或 \( \binom{n + r - 1}{n} \)

例子： 對於 10 個蘋果和 3 位朋友，\(n = 10\)，\(r = 3\)。
方法數 = \( \binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66 \)。

重點複習：當你分配的物品是完全相同的（例如相同的硬幣或糖果），但接收物品的人是不同的，請使用隔板法。

核心概念：雙射原理讓我們能用一個更簡單的計數問題來替換困難的問題，同時保持計數結果不變。

2. 容斥原理 (PIE)

在 H2 中，你學過 \( P(A \cup B) = P(A) + P(B) - P(A \cap B) \)。容斥原理只是這個規則針對超過兩個集合時的「進階版」。

核心思想是：加上各個獨立組別的數量，減去兩個組別重疊的部分（因為你重複計算了兩次），補回三個組別重疊的部分（因為你減去的次數太多了），依此類推。

三個集合的可視化

假設你正在計算修讀生物 (B)、化學 (C) 和物理 (P) 的學生人數。要找出修讀至少其中一科的學生總數，我們遵循以下模式：
1. 包含：加上各集合的大小： \( |B| + |C| + |P| \)
2. 排除：減去兩兩重疊的部分： \( - |B \cap C| - |B \cap P| - |C \cap P| \)
3. 包含：補回三者重疊的部分： \( + |B \cap C \cap P| \)

公式：
\( |A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C| \)

冷知識：這個原理對於計算錯排 (derangements) 非常有用。錯排是一種排列方式，其中沒有任何元素留在原來的位置（就像 5 個人離開派對時，每個人都意外拿錯了別人的帽子！）。

記憶法：把它想像成心跳：加、減、加、減... 你先加上單個項目，接著減去成對的項目，然後加上三元組合，以此類推。

核心概念：容斥原理是你的「清理小組」。當集合重疊時使用它，確保你沒有多算或少算任何特定成員。

3. 常見陷阱與建議

陷阱 1：忘記物件是相同還是不同。
永遠問自己：「如果我交換這兩個物件，排列看起來會不一樣嗎？」如果是，它們就是不同的；如果不是，它們就是相同的。隔板法只適用於相同的物件。

陷阱 2：在隔板法中遺漏了「至少一個」的條件。
基本公式 \( \binom{n+r-1}{r-1} \) 允許某些人得到 0 個項目。如果題目要求「每個人必須至少收到一個蘋果」，請先分給每個人一個，然後再對剩餘的蘋果使用公式。

陷阱 3：在容斥原理中太早停止。
如果你有四個集合，你必須繼續「加、減、加、減」的模式，直到算到所有四個集合的交集。千萬不要在三個集合時就停下來！

鼓勵：組合數學和概率就像拼圖遊戲。如果你卡住了，試著畫出問題的簡化版本。如果你能解決 3 個項目的情況，通常你就能看出解決 100 個項目的規律了！

章節總結

1. 雙射原理：將困難的集合映射到簡單的集合。使用隔板法來將相同的物件分配到不同的盒子： \( \binom{n+r-1}{r-1} \)。
2. 容斥原理：透過交替加減來校正重疊集合的計數。這是處理「至少一個」或「沒有一個」問題的終極工具。
3. 邏輯優先：在挑選公式之前，務必先確認順序是否重要，以及物件是否相同！