歡迎來到計數的世界：組合證明！
在 H2 數學的旅程中，你已經學會了如何計算排列與組合。到了 H3 數學，我們要將這些技巧提升到更高層次。我們不再僅僅是計算出一個數值，而是要利用計數作為一種工具，去證明兩個數學表達式相等。這就是所謂的組合論證（Combinatorial Argument）。
你可以這樣想：如果你先按行數點算教室裡的學生人數，然後再按列數點算一次，你得到的總數應該是一樣的。如果按行計數得到一個公式，按列計數得到另一個公式，那麼這兩個公式必然相等！別擔心，如果這聽起來有點抽象——我們會一步步拆解說明。
1. 什麼是組合證明？
組合證明是一種通過展示等式兩邊都在計算同一組對象的不同方式，從而證明恆等式（即左右兩邊相等的方程）的方法。
「故事」法：要寫出一個組合證明，本質上就是講述一個關於選擇一組對象的故事。
1. 左式（LHS）：解釋這個表達式如何計算特定的場景。
2. 右式（RHS）：解釋另一個表達式如何從不同的角度計算完全相同的場景。
3. 結論：既然兩者計算的是同一樣東西，它們一定相等！
你知道嗎？
組合證明通常被認為比代數證明（例如展開括號或使用數學歸納法）更「優雅」，因為它們揭示了恆等式成立的原因，而不僅僅是顯示數學運算上的結果正確。
2. 對稱恆等式
讓我們從你在 H2 已經熟悉的經典公式開始：
\( \binom{n}{r} = \binom{n}{n-r} \)
場景：假設你有一群 \(n\) 位朋友，你想從中挑選 \(r\) 位去參加音樂會。
左式解釋：根據定義，從 \(n\) 個人中挑選 \(r\) 個人的方法數是 \( \binom{n}{r} \)。
右式解釋：與其選擇誰去音樂會，你也可以選擇誰留在家裡。要讓 \(r\) 個人去，你就必須留下 \(n-r\) 個人。選擇這 \(n-r\) 個留在家裡的人的方法數是 \( \binom{n}{n-r} \)。
結論：因為每一次對「參加者」的選擇都對應到唯一一種對「留守者」的選擇，所以這兩個表達式必然相等。
3. 帕斯卡恆等式 (Pascal's Identity)
這是組合學中最基礎的恆等式：
\( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)
場景：你需要從 \(n\) 個人中選出一個 \(k\) 人的委員會。這 \(n\) 個人中有一位學生叫 Sam。
左式解釋：選擇該委員會的總方法數很簡單，就是 \( \binom{n}{k} \)。
右式解釋：讓我們通過觀察 Sam 是否在委員會中來進行分類計數：
• 情況 1：Sam 在委員會中。我們已經選了 Sam，所以只需要從剩下的 \(n-1\) 個候選人中再選出 \(k-1\) 個人。方法數為 \( \binom{n-1}{k-1} \)。
• 情況 2：Sam 不在委員會中。我們必須從剩下的 \(n-1\) 個候選人中選出全部 \(k\) 個人。方法數為 \( \binom{n-1}{k} \)。
由於這兩種情況互斥且涵蓋了所有可能性，我們將它們相加。
結論：兩邊都計算了組成委員會的總方法數，因此 \( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)。
快速複習：「明星隊員」法
每當你看到一個將兩個組合相加得到一個更大組合的恆等式時，試著想像一個「明星隊員」（就像上面的 Sam），並構建兩種情況：一種是他被包含在內，另一種是他被排除在外。
4. 委員會主席恆等式
考慮恆等式：\( k \binom{n}{k} = n \binom{n-1}{k-1} \)
場景：我們想從 \(n\) 個人的群體中組成一個 \(k\) 人的委員會，然後從該委員會中選出一人擔任主席。
左式解釋：首先，從 \(n\) 個人中選出 \(k\) 位委員，方法數為 \( \binom{n}{k} \)。然後，從這 \(k\) 位委員中選出 1 位主席，方法數為 \(k\)。總計：\( k \binom{n}{k} \)。
右式解釋：首先，從 \(n\) 個人的群體中直接選出主席，方法數為 \(n\)。然後，從剩下 \(n-1\) 個人中選出其餘 \(k-1\) 位委員，方法數為 \( \binom{n-1}{k-1} \)。總計：\( n \binom{n-1}{k-1} \)。
結論：兩種方法都計算了同一種「帶主席的委員會」組合，因此表達式相等。
5. 雙射原則 (Bijection Principle)
有時，我們通過展示兩個不同集合之間的一一對應關係（雙射）來證明兩者相等。如果集合 A 中的每個元素都能與集合 B 中的唯一一個元素配對（且沒有剩餘），那麼集合 A 的大小必然等於集合 B 的大小。
例子：星星與棒子 (Stars and Bars)
課程大綱提到將不可區分物品放入可區分盒子。
假設你有 \(n\) 顆相同的糖果要分給 \(k\) 個孩子。這等同於排列 \(n\) 個「星星」（糖果）和 \(k-1\) 個「棒子」（分隔符）。
由於糖果分配與符號排列之間存在雙射，我們可以使用排列公式來證明分配公式：\( \binom{n+k-1}{k-1} \)。
6. 排容原理 (Inclusion-Exclusion Principle, IEP)
在 H2，你學過：\( P(A \cup B) = P(A) + P(B) - P(A \cap B) \)。
在 H3 中，我們將其用於處理更複雜的證明，涉及「至少一個」或「一個都沒有」的場景。
概念：要計算多個集合並集中的元素個數，你需要：
1. 將各個單獨集合的大小相加。
2. 減去所有可能的雙重交集大小（因為它們被多算了一次）。
3. 再加上所有可能的三重交集大小（因為它們被減了太多次）……以此類推。
類比：如果你轉動方向盤時向左修正過度了，你就必須向右轉回來，然後可能再稍微向左調一點以保持居中。排容原理就是一種數學上的「轉向修正」。
7. 常見陷阱與建議
• 避免代數運算：如果題目要求組合論證，僅展開階乘是會被扣分的。專注於你的「故事」。
• 檢查邊界條件：確保你的「故事」在 \(n\) 和 \(k\) 的數值範圍內是有意義的（例如，你不能從 3 個人的群體中挑選 5 個人）。
• 識別「動作」：你在選隊伍嗎？你在分配角色嗎？你在排列符號嗎？識別出具體的動作能幫助你理解公式的含義。
總結重點
• 組合證明通過用兩種方式計算同一個集合來顯示兩個公式相等。
• 雙重計數是核心技巧：找到一個集合，用一種方式計數（左式），再用另一種方式計數（右式）。
• 帕斯卡恆等式依賴於對特定個體的「包含或排除」邏輯。
• 雙射原則通過完美配對元素來證明兩個集合大小相同。
• 排容原理通過增加和扣除交集來幫助計算複雜的重疊情況。
如果起初覺得棘手，別擔心！組合推理就像解謎。一旦你找到了正確的「故事」來講，數學公式就會完美地組合在一起。