Combinatorics組合計數

01為什麼需要它

看到這些關鍵字就想到它：從 n 個裡選 k 個、不管順序、網格路徑數、相同物品分到不同箱子（隔板法）、機率等於有利情況除以全部情況、答案取模 10⁹+7 的計數題、大量查詢 C(n, k)。

02核心概念

計數的兩個基本式子：排列 P(n, k) = n! / (n − k)!，從 n 個不同的東西依序挑 k 個，順序不同算不同；組合 C(n, k) = n! / (k! · (n − k)!)，不管順序，所以把每組 k 個東西的 k! 種排法除掉。很多題目換個角度就是組合數：在方格上往右 a 步、往下 b 步的路徑數是 C(a + b, a)，因為只要決定 a + b 步裡哪幾步往右；把 n 個相同的東西分進 k 個箱子（可以空）是 C(n + k − 1, k − 1)，相當於在 n 個東西之間插 k − 1 根隔板，這叫隔板法。

怎麼算取決於規模和模數。第一種是 Pascal 三角形：C(n, k) = C(n − 1, k − 1) + C(n − 1, k)，理由是單看第 n 個東西選或不選，把所有選法分成不重疊的兩類。整張表 O(n²) 時間和空間，只用加法，所以任何模數都能用，適合 n 在幾千以內。第二種是精確值的乘法公式 C(n, k) = ∏ (n − k + i) / i，i 從 1 到 k，每一步的中間結果都是 C(n − k + i, i)，一定是整數，O(min(k, n − k))；但 C++ 的 64 位元整數在 n 超過 60 左右就會溢位，精確值要靠大數或 Python。

第三種是模數為質數 p 時最常用的做法：預先算階乘表 fact[i] = i! mod p 和階乘反元素表 inv_fact[i] = (i!)⁻¹ mod p，之後 C(n, k) = fact[n] · inv_fact[k] · inv_fact[n − k]，每次查詢 O(1)。反元素表不必對每一格做快速冪，只對 n! 做一次，再由右往左 inv_fact[i − 1] = inv_fact[i] · i，因為 (i − 1)! = i! / i。建表總共 O(n + log p) 時間、O(n) 空間。前提是 n < p，否則 p! 以後的階乘都含因數 p，取模變成 0，沒有反元素；n 比 p 大時要改用 Lucas 定理。

常見的坑：k < 0 或 k > n 時答案是 0，沒先擋掉會索引越界；直接算 n! 再除，21! 就超過 64 位元；乘法公式寫成 res * ((n − k + i) / i)，整數除法先截斷就錯了；階乘表只開到 n，查詢時 n 超出範圍；模數不是質數卻用了費馬小定理；算機率時用浮點數直接乘組合數，很快就溢位或失去精度，應該改用 ln(n!) 的對數相加減。和鄰近課程的關係：上一篇 Modular Arithmetic 提供反元素；Pascal 三角形本身就是 Memoization & Tabulation 的填表；Backtracking 的 Combinations 是把 C(n, k) 種組合實際列出來，組合數告訴你那個搜尋會有多大。

03演算法步驟

1. 1先判斷要數的是排列還是組合、東西是否相同，把問題換成 C(n, k) 或 P(n, k) 的式子，例如路徑數 C(a + b, a)、隔板法 C(n + k − 1, k − 1)。
2. 2n 在幾千以內，或模數不是質數：用 Pascal 三角形 C[n][k] = C[n − 1][k − 1] + C[n − 1][k] 填表。
3. 3模數是質數 p 而且 n < p：建 fact[0..n]，fact[i] = fact[i − 1] · i mod p。
4. 4inv_fact[n] = fact[n]^(p − 2) mod p，再由右往左 inv_fact[i − 1] = inv_fact[i] · i mod p。
5. 5查詢時 k < 0 或 k > n 回傳 0，否則回傳 fact[n] · inv_fact[k] · inv_fact[n − k] mod p。

04互動示範

上方可以切換兩種算法。「Pascal 三角形」從兩端的 1 開始，逐格填第 0 到 6 列：藍色是正在算的格子，黃色是它上一列的兩個來源，第一格的說明會拆解為什麼是「包含第 n 個」加上「不包含第 n 個」。填完第 6 列 1、6、15、20、15、6、1，總和 64 = 2⁶，綠色的 C(6, 2) = 15 同時也是往右 4 步、往下 2 步的路徑數。「階乘表 mod 13」要算 C(8, 3) mod 13：先由左往右填 0! 到 8!，再只對 8! = 7 做一次費馬小定理得到反元素 2，接著由右往左每格乘上 i 填完反元素表，每一步都附驗算。查詢時綠色的三格相乘 7 × 11 × 9 ≡ 4，和 56 mod 13 相同。最後一步說明為什麼 n 必須小於模數。

05程式碼

Python 放階乘表加階乘反元素表的 Binomial 類別，以及計算精確值的乘法公式，並用它算樂透、網格路徑和隔板法的例子。C++ 放同樣的 Binomial 結構、模數不是質數時用的 Pascal 三角形，以及算機率時改用 lgamma 對數的寫法。

MOD = 1_000_000_007


class Binomial:
    """預先算好階乘與階乘的反元素，之後每次 C(n, k) mod p 都是 O(1)。需要 n_max < p"""

    def __init__(self, n_max, p=MOD):
        self.p = p
        self.fact = [1] * (n_max + 1)
        for i in range(1, n_max + 1):
            self.fact[i] = self.fact[i - 1] * i % p
        self.inv_fact = [1] * (n_max + 1)
        self.inv_fact[n_max] = pow(self.fact[n_max], p - 2, p)   # 整個流程只做這一次快速冪
        for i in range(n_max, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % p     # (i-1)! 的反元素 = i! 的反元素 × i

    def C(self, n, k):
        if k < 0 or k > n:                      # 選不出來就是 0 種，先擋掉免得索引越界
            return 0
        return self.fact[n] * self.inv_fact[k] % self.p * self.inv_fact[n - k] % self.p


def comb_exact(n, k):
    """精確值，O(min(k, n-k))。第 i 步的結果是 C(n-k+i, i)，一定是整數，所以先乘再除不會有餘數。
    Python 3.8 起也可以直接用 math.comb"""
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    res = 1
    for i in range(1, k + 1):
        res = res * (n - k + i) // i
    return res


if __name__ == "__main__":
    print(Binomial(8, 13).C(8, 3), comb_exact(8, 3))   # 4 56：示範裡的 C(8, 3) mod 13
    print(comb_exact(49, 6))                    # 13983816：大樂透 49 選 6 的組合數
    print(comb_exact(4 + 2, 2))                 # 15：往右 4 步、往下 2 步的路徑數
    print(comb_exact(10 + 4 - 1, 4 - 1))        # 286：10 台相同的機器分到 4 個機房（隔板法）
    print(Binomial(200000).C(200000, 100000))   # 879467333

06練習題

• LeetCode 118Pascal's TriangleEasy
• LeetCode 1641Count Sorted Vowel Strings（隔板法）Medium
• LeetCode 2400Number of Ways to Reach a Position After Exactly k Steps（決定幾步往右）Medium
• LeetCode 1735Count Ways to Make Array With Product（質因數分解後每個質數各用隔板法）Hard
• LeetCode 1569Number of Ways to Reorder Array to Get Same BST（左右子樹交錯排列 C(n − 1, 左子樹大小)）Hard
• LeetCode 1916Count Ways to Build Rooms in an Ant Colony（階乘表加反元素）Hard