第 8 章 組合數學演算法#

組合數學研究「有多少種」與「怎麼列出來」：n 個人有幾種排法、從 52 張牌抽 5 張有幾種組合、合法括號序列有多少條。對電腦來說，它呈現兩個面貌：枚舉（把所有情況走一遍——搜尋、測試、產生測資的基礎）與計數（不列舉就直指總數——動態規劃與封閉公式的戰場）。

8.1 節排列與組合的枚舉：字典序法不靠遞迴就能逐一生成下一個排列，這是 C++ next_permutation 的原理；組合枚舉則有精巧的位元技巧。8.2 節鴿籠原理與生成函數：鴿籠原理是「存在性證明」的最短捷徑，生成函數則是把數列裝進多項式、把組合問題變成乘法問題的瑞士刀。8.3 節卡特蘭數與遞迴計數：許多看似無關的問題（括號配對、二元樹計數、凸多邊形三角剖分）共享同一個遞迴式，其封閉形式就是卡特蘭數——這是「遞迴 → 動態規劃 → 封閉公式」三段升級的完整示範。

本章與第 1 章呼應得特別密切：組合數爆炸成長（n! 比 2ⁿ 還兇）正是「枚舉不可行、計數必須聰明」的原因；而大整數能力（Python 原生支援）讓我們能算出 C(1000, 500) 這種 300 位的天文數字。學完本章，你應能判斷一個組合問題該「枚舉、遞迴計數、還是套公式」，以及每條路徑的成本。