當「直接數」變得不可能：容斥、生成函數與符號的力量

當「直接數」變得不可能：容斥、生成函數與符號的力量

你已經會用排列（permutation）與組合（combination）算出「有多少種」了。但請先想一個問題：在 $1$ 到 $100$ 之間，有多少個整數不是 $2$、$3$ 或 $5$ 的倍數？

你可能會想：先扣掉 $2$ 的倍數、再扣掉 $3$ 的倍數、再扣掉 $5$ 的倍數。但 $6$ 同時是 $2$ 和 $3$ 的倍數，被扣了兩次；$30$ 更是被反覆計算。如果硬要逐一列舉，這還勉強可行；可是把 $100$ 換成 $10^{18}$，把「$2,3,5$」換成「前 $20$ 個質數」，列舉就徹底崩潰了。

進階組合學的核心精神，正是在「無法直接數」的時候，找到一套系統化的代數機制去數。這篇文章帶你看三件入門篇通常不會細談的利器：容斥原理（Inclusion-Exclusion Principle）、生成函數（Generating Function），以及把組合恆等式變成「形式符號運算」的視角。

容斥原理：把「重複扣掉的」加回來

容斥原理處理的是「聯集的大小」。對兩個集合，你早就知道：

$$ |A \cup B| = |A| + |B| - |A \cap B|. $$

減去 $|A \cap B|$ 是因為交集被算了兩次。推廣到三個集合：

$$ |A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|. $$

注意符號的規律：單個集合是 $+$，兩兩交集是 $-$，三個交集又變回 $+$。一般地，對 $n$ 個集合 $A_1, \dots, A_n$：

$$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq \{1,\dots,n\}} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right|. $$

這個 $(-1)^{|S|+1}$ 就是「奇數個集合相交時加、偶數個集合相交時減」的代數寫法。它為什麼正確？關鍵在於：對任何一個落在聯集裡的元素，假設它恰好屬於其中 $k$ 個集合，我們要驗證它在右式中總共被計入的次數恰好是 $1$。它被計入的次數是

$$ \sum_{j=1}^{k} (-1)^{j+1} \binom{k}{j}. $$

由二項式定理（Binomial Theorem），$\sum_{j=0}^{k} (-1)^{j}\binom{k}{j} = (1-1)^k = 0$，移項後立刻得到 $\sum_{j=1}^{k}(-1)^{j+1}\binom{k}{j} = 1$。每個元素剛好被算一次——這就是容斥成立的證明，而且它本質上就是二項式定理。

看一個例子

回到開頭的問題：$1$ 到 $100$ 中，有多少個數不被 $2$、$3$、$5$ 整除？

令 $A$、$B$、$C$ 分別是 $2$、$3$、$5$ 的倍數所成的集合。用地板函數（floor function）計數：

$$ |A| = \left\lfloor \tfrac{100}{2} \right\rfloor = 50,\quad |B| = \left\lfloor \tfrac{100}{3} \right\rfloor = 33,\quad |C| = \left\lfloor \tfrac{100}{5} \right\rfloor = 20. $$

兩兩交集（倍數的最小公倍數）：

$$ |A\cap B| = \left\lfloor \tfrac{100}{6}\right\rfloor = 16,\quad |A\cap C| = \left\lfloor \tfrac{100}{10}\right\rfloor = 10,\quad |B\cap C| = \left\lfloor \tfrac{100}{15}\right\rfloor = 6. $$

三個交集：$|A\cap B\cap C| = \left\lfloor \tfrac{100}{30}\right\rfloor = 3$。

於是被 $2,3,5$ 任一整除的數有：

$$ 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74. $$

不被任何一個整除的：$100 - 74 = 26$ 個。你可以驗證，這恰好對應到歐拉函數（Euler's totient）的精神：在 $30$ 為週期的範圍內，與 $30$ 互質的比例是 $\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5}$。把這個方法推到「前 $20$ 個質數」「上界 $10^{18}$」，公式形式完全不變，只是 $S$ 的子集多到要靠電腦遍歷——但機制不變，這正是容斥的威力。

錯位排列：容斥的經典戰場

容斥最漂亮的應用之一是錯位排列（derangement）：$n$ 個人各寫一張卡片，洗牌後重新分發，問「沒有任何人拿到自己卡片」的排列有幾種？記作 $D_n$。

設 $A_i$ 為「第 $i$ 個人拿到自己卡片」的排列集合。我們要的是所有 $A_i$ 都不發生，也就是 $n! - |A_1 \cup \cdots \cup A_n|$。固定其中 $j$ 個人各自拿到自己卡片，其餘隨意，方法數是 $(n-j)!$，而選哪 $j$ 個人有 $\binom{n}{j}$ 種。套用容斥：

$$ D_n = \sum_{j=0}^{n} (-1)^{j} \binom{n}{j}(n-j)! = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!}. $$

這裡藏著一個迷人的事實：當 $n \to \infty$，$\sum_{j=0}^{n}\frac{(-1)^j}{j!} \to e^{-1}$。所以

$$ \frac{D_n}{n!} \to \frac{1}{e} \approx 0.3679. $$

換句話說，無論多少人玩這個交換禮物遊戲，「完全沒有人拿到自己禮物」的機率穩定趨近於 $1/e$，約 $37\%$。一個離散的計數問題，極限竟然冒出自然常數 $e$——這是組合學與分析學交會的第一個驚喜。

生成函數：把序列「打包」成一個函數

現在介紹進階組合學最強大的工具：生成函數。核心想法是，把一個數列 $a_0, a_1, a_2, \dots$ 編碼成一個形式冪級數（formal power series）：

$$ A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots $$

這裡的 $x$ 不是要代入求值的變數，而是一個「記帳的標籤」——$x^n$ 的係數就是 $a_n$。生成函數的魔力在於：數列之間的組合操作，對應到函數之間的代數操作。數列的卷積（convolution）對應函數的乘積，遞迴關係對應函數方程。

最基本的例子是幾何級數。考慮「每種物品要不要選」這類問題，一個物品的生成函數是 $(1 + x)$（不選貢獻 $x^0$，選貢獻 $x^1$）。$n$ 個物品就是 $(1+x)^n$，展開後 $x^k$ 的係數正是 $\binom{n}{k}$——這就是二項式定理的生成函數版本。

如果允許「同一種物品可以重複拿任意多個」，單一物品的生成函數變成

$$ 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}. $$

看一個例子：用生成函數解硬幣問題

問：用 $1$ 元、$2$ 元、$5$ 元硬幣（各種數量不限）湊出 $n$ 元，有幾種方法？

每種面額對應一個「子生成函數」。$1$ 元硬幣可以用 $0,1,2,\dots$ 個，貢獻 $1 + x + x^2 + \cdots = \frac{1}{1-x}$；$2$ 元硬幣每個帶來 $x^2$，貢獻 $1 + x^2 + x^4 + \cdots = \frac{1}{1-x^2}$；$5$ 元硬幣貢獻 $\frac{1}{1-x^5}$。湊錢方法數的生成函數就是三者相乘：

$$ G(x) = \frac{1}{(1-x)(1-x^2)(1-x^5)}. $$

要算「湊 $n$ 元有幾種方法」，就是求 $G(x)$ 中 $x^n$ 的係數。例如湊 $6$ 元，把 $G(x)$ 展開到 $x^6$，係數是 $5$（你可以手動驗證：$6$ 個 $1$；$4$ 個 $1$ 加 $1$ 個 $2$；$2$ 個 $1$ 加 $2$ 個 $2$；$3$ 個 $2$；$1$ 個 $1$ 加 $1$ 個 $5$——共 $5$ 種）。

重點在於：原本需要動腦窮舉的「分拆問題」，被轉化成一個純機械的「乘冪級數、取係數」運算。當面額很多、目標金額很大時，這個代數框架可以直接交給電腦或用部分分式（partial fractions）求閉式解。

用生成函數解遞迴：費氏數列的閉式解

生成函數還能把遞迴關係「一鍵」解出閉式。以費氏數列（Fibonacci）為例：$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$。

設 $F(x) = \sum_{n\ge 0} F_n x^n$。把遞迴關係乘上 $x^n$ 並對 $n \ge 2$ 求和：

$$ \sum_{n\ge 2} F_n x^n = \sum_{n\ge 2} F_{n-1}x^n + \sum_{n\ge 2} F_{n-2}x^n. $$

左式是 $F(x) - F_0 - F_1 x = F(x) - x$。右式兩項分別是 $x\big(F(x) - F_0\big) = xF(x)$ 與 $x^2 F(x)$。整理得

$$ F(x) - x = xF(x) + x^2 F(x) \;\;\Longrightarrow\;\; F(x) = \frac{x}{1 - x - x^2}. $$

分母 $1 - x - x^2$ 的根與黃金比例（golden ratio）$\varphi = \frac{1+\sqrt 5}{2}$ 有關。用部分分式拆解後提取係數，就得到著名的 Binet 公式：

$$ F_n = \frac{1}{\sqrt 5}\left( \varphi^n - \psi^n \right),\quad \varphi = \frac{1+\sqrt 5}{2},\ \psi = \frac{1-\sqrt 5}{2}. $$

一個只有加法的整數遞迴，閉式解裡卻出現無理數 $\sqrt 5$，而且每一步算出來都精準回到整數——這再次展示了生成函數如何在離散與連續之間搭橋。

動手試試

試著用生成函數重新推導「卡塔蘭數（Catalan number）」。卡塔蘭數 $C_n$ 計數許多對象：$n$ 對括號的合法配對方式、$n+1$ 個葉子的二元樹形狀、不越過對角線的格點路徑等。它滿足遞迴

$$ C_0 = 1,\quad C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}. $$

請注意右邊是一個卷積，這正是生成函數的拿手好戲。設 $C(x) = \sum_{n\ge 0} C_n x^n$，卷積對應乘積，於是 $C(x)$ 滿足

$$ C(x) = 1 + x\, C(x)^2. $$

把它當成關於 $C(x)$ 的二次方程解出（取在 $x=0$ 處有界的那一支根），你會得到

$$ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}, $$

再用廣義二項式定理展開 $\sqrt{1-4x}$，提取係數，就能證明閉式

$$ C_n = \frac{1}{n+1}\binom{2n}{n}. $$

如果你能獨立走完這條路，代表你已經掌握了生成函數的整套語言。

重點回顧

• 容斥原理用 $(-1)^{|S|+1}$ 的交錯符號，把「重複算到的」精準扣回；它的正確性根植於二項式定理 $\sum_j (-1)^j \binom{k}{j} = 0$。
• 錯位排列 $D_n = n!\sum_{j=0}^n \frac{(-1)^j}{j!}$，且 $D_n/n! \to 1/e$——離散計數的極限冒出自然常數 $e$。
• 生成函數把數列編碼成形式冪級數，讓「數列的組合操作」轉化為「函數的代數操作」：選取對應乘積、卷積對應相乘、遞迴對應函數方程。
• 硬幣湊錢、費氏遞迴、卡塔蘭數，這些看似不同的問題，在生成函數框架下都化為「取 $x^n$ 係數」的機械運算。
• 進階組合學的精神是：當「直接數」不可行時，用代數結構把計數系統化、可推廣、可交給機器。

深入探討（研究所視角）

上述工具其實是一座更宏大理論的入口。

符號方法（Symbolic Method）與解析組合學。 Flajolet 與 Sedgewick 的《Analytic Combinatorics》把「組合結構的構造」與「生成函數的運算」建立成一個嚴格的字典：不交聯集（disjoint union）對應 $A(x) + B(x)$，笛卡兒積（product）對應 $A(x)\cdot B(x)$，序列（sequence）構造 $\mathrm{SEQ}(\mathcal{A})$ 對應 $\frac{1}{1 - A(x)}$，多重集（multiset）與循環（cycle）也各有對應公式。這意味著你可以「不解遞迴」，直接從組合物件的遞迴定義「翻譯」出生成函數。更進一步，對指數生成函數（exponential generating function, EGF） $\hat{A}(x) = \sum a_n \frac{x^n}{n!}$，標記結構（labelled structure）的組合操作又有另一套字典，這對排列、圖、樹等帶標記物件特別自然。

奇異點分析（singularity analysis）。 解析組合學最深刻之處在於：生成函數作為複變函數，其離原點最近的奇異點（dominant singularity）位置與類型，直接決定了係數 $a_n$ 的漸近增長率。例如卡塔蘭數的生成函數在 $x = 1/4$ 有平方根型分支點，由此可推出 $C_n \sim \frac{4^n}{n^{3/2}\sqrt\pi}$。這把組合計數與複分析（complex analysis）的留數、Hankel 圍道、轉移定理（transfer theorem）緊密結合，是現代演算法平均複雜度分析的理論基礎。

容斥的代數化：Möbius 反演。 容斥原理其實是偏序集（poset）上 Möbius 反演（Möbius inversion） 的特例。在布林格（Boolean lattice，即所有子集構成的偏序集）上，Möbius 函數 $\mu(S, T) = (-1)^{|T \setminus S|}$，這正是容斥裡的交錯符號。把這個觀點推廣到一般偏序集（Rota 的開創性工作），就能統一處理數論中的 Möbius 反演、區間計數、以及染色多項式（chromatic polynomial）等看似無關的問題。容斥不再是一個「技巧」，而是某個格結構上的反演定理。

q-類比與更深的對稱。 把二項式係數 $\binom{n}{k}$ 換成 q-二項式係數（Gaussian binomial coefficient） $\binom{n}{k}_q$，許多恆等式都有「帶 $q$」的精緻版本，計數的不再是子集，而是有限體上的子空間、或帶權重的格點路徑。這條線通向 $q$-級數、分拆理論（partition theory，Hardy–Ramanujan 漸近公式）、乃至表示論與數學物理。當你下一次寫下一個簡單的 $\binom{n}{k}$ 時，不妨記得：它背後牽連的，是一張橫跨代數、分析與幾何的廣闊版圖。