组合数学与计数

组合数学是算法竞赛和面试中计数类问题的理论基础。排列、组合、容斥原理、卡特兰数等工具能优雅地解决"有多少种方案"类问题。

一、排列与组合

Mermaid · 渲染中（下方为源码）

graph LR
  A[计数] --> B[排列 P]
  A --> C[组合 C]
  A --> D[容斥]
  A --> E[卡特兰数]

公式

P(n, k) = n! / (n-k)!     （排列：有序）
C(n, k) = n! / (k!(n-k)!) （组合：无序）

计算（取模）

long MOD = 1_000_000_007;
long[] fact = new long[MAX];
long[] invFact = new long[MAX];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[MAX-1] = fastPow(fact[MAX-1], MOD-2, MOD);
    for (int i = MAX-2; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

二、容斥原理

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

组合数学是算法竞赛和面试中计数类问题的理论基础。排列、组合、容斥原理、卡特兰数等工具能优雅地解决"有多少种方案"类问题。

一、排列与组合

Mermaid · 渲染中（下方为源码）

graph LR
  A[计数] --> B[排列 P]
  A --> C[组合 C]
  A --> D[容斥]
  A --> E[卡特兰数]

公式

P(n, k) = n! / (n-k)!     （排列：有序）
C(n, k) = n! / (k!(n-k)!) （组合：无序）

计算（取模）

long MOD = 1_000_000_007;
long[] fact = new long[MAX];
long[] invFact = new long[MAX];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[MAX-1] = fastPow(fact[MAX-1], MOD-2, MOD);
    for (int i = MAX-2; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

二、容斥原理

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

D(n) = n! × Σ(-1)^k / k!  (k=0..n)
D(n) = (n-1) × (D(n-1) + D(n-2))

C_n = C(2n, n) / (n+1) = C(2n, n) - C(2n, n+1)

问题	答案
n 对括号的合法序列数	C_n
n 个节点的不同 BST 数	C_n
n 步不越过对角线的路径数	C_n
凸 n+2 边形的三角剖分数	C_n
栈的出栈序列数	C_n

(a + b)^n = Σ C(n,k) × a^(n-k) × b^k

// LeetCode 118
List<List<Integer>> generate(int numRows) {
    List<List<Integer>> tri = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) row.add(1);
            else row.add(tri.get(i-1).get(j-1) + tri.get(i-1).get(j));
        }
        tri.add(row);
    }
    return tri;
}

C(n, m) mod p = C(n/p, m/p) × C(n%p, m%p) mod p

方式1：公式法 C(n,k) = n! / (k!(n-k)!)
  C(5,2) = 5! / (2!·3!) = 120 / (2·6) = 120/12 = 10 ✓
  问题：除法在取模下不成立，需要逆元

方式2：递推（杨辉三角）C(n,k) = C(n-1,k-1) + C(n-1,k)
  C(5,2) = C(4,1) + C(4,2)
         = [C(3,0)+C(3,1)] + [C(3,1)+C(3,2)]
  逐层展开，适合批量预处理 O(n²)

方式3：阶乘 + 逆元（取模场景）
  C(n,k) = n! · inv(k!) · inv((n-k)!) mod p
  预处理 fact[i] 和 inv_fact[i]，单次查询 O(1)

Catalan(n) = C(2n, n) / (n+1)
前几项：1, 1, 2, 5, 14, 42, 132…

经典模型（本质相同）：
  - n 对括号的合法组合数（LC 22）
  - n 个节点的不同 BST 数（LC 96）
  - 不越过对角线的网格路径数
  - n+1 个叶子的满二叉树数
识别信号：“合法序列/不越过某条线/进出栈” → 卡特兰

组合数学与计数

一、排列与组合

公式

计算（取模）

二、容斥原理

组合数学 Combinatorics

一、排列与组合

公式

计算（取模）

二、容斥原理

组合数学 Combinatorics

应用：错排（全错位排列）

三、卡特兰数

卡特兰数的应用

四、鸽巢原理

五、二项式定理

杨辉三角（Pascal's Triangle）

六、Lucas 定理（大组合数 mod 小质数）

七、面试要点

八、组合数计算过程模拟

九、思考题

相关教程

交互式可视化