第1章：组合数学基础——排列、组合与核心计数工具

组合数学，说白了就是「数数」的学问。但别小看这个数数，我在项目中吃过不少亏——有一次写一个调度算法，因为少算了一个排列组合的情况，导致系统在高并发下频繁死锁。嗯，从那以后我再也不敢轻视这些基础了。

这一章我们聊聊几个核心概念：排列与组合、二项式定理、容斥原理、卡特兰数、斯特林数。它们就像工具箱里的螺丝刀，每个都有特定的用途。

1.1 排列与组合

先问个问题：从5个人里选3个排队，有多少种排法？

这就是排列问题。排列讲究顺序，选出来还要排好队。公式很简单：

P(n, k) = n! / (n - k)!

那如果只是选人，不排队呢？那就是组合：

C(n, k) = n! / (k! * (n - k)!)

我个人习惯用组合数公式时，会先约分再计算，避免大数溢出。比如 C(10, 3)，我会写成 (10*9*8)/(3*2*1)，而不是先算阶乘。

1.2 二项式定理

二项式定理其实就是 (a + b)^n 的展开公式：

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

这个公式在算法分析里经常用到。我记得有一次做动态规划的状态压缩，就是靠二项式定理来推导状态转移的复杂度。

举个例子，展开 (x + 1)^4：

(x + 1)^4 = C(4,0)x^4 + C(4,1)x^3 + C(4,2)x^2 + C(4,3)x + C(4,4)
           = x^4 + 4x^3 + 6x^2 + 4x + 1

系数 1, 4, 6, 4, 1 就是杨辉三角的第4行。你想想看，这多好记。

1.3 容斥原理

容斥原理解决的是「重叠计数」的问题。比如统计一个班里既喜欢数学又喜欢物理的人数，直接加会重复计算。

公式长这样：

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

我曾经在写一个日志分析工具时，需要统计同时满足多个条件的记录数。一开始直接累加，结果数据对不上。后来用容斥原理一算，问题就解决了。

1.4 卡特兰数

卡特兰数是个神奇的东西，它出现在很多看似不相关的问题里：

• n对括号的合法匹配数
• n个节点的二叉搜索树形态数
• n×n网格中不穿越对角线的路径数

递推公式：

C₀ = 1
Cₙ = Σ Cᵢ * Cₙ₋₁₋ᵢ  (i从0到n-1)

通项公式：

Cₙ = C(2n, n) / (n + 1)

前几个卡特兰数：1, 1, 2, 5, 14, 42, 132, 429...

我记得有一次面试，面试官让我写一个函数计算卡特兰数。我直接用通项公式，一行代码搞定。但要注意，C(2n, n) 可能很大，需要用 long long 或者大数库。

1.5 斯特林数

斯特林数分两类，我分别说说。

第一类斯特林数 s(n, k)

表示将n个元素排成k个圆排列的方案数。圆排列就是首尾相连的排列，旋转后相同算一种。

递推公式：

s(n, k) = s(n-1, k-1) - (n-1) * s(n-1, k)

第二类斯特林数 S(n, k)

表示将n个元素划分成k个非空子集的方案数。这个在集合划分问题里很常见。

递推公式：

S(n, k) = S(n-1, k-1) + k * S(n-1, k)

举个例子，S(4, 2) = 7，表示4个元素分成2个非空子集有7种分法。

知识体系总览

下面这张图帮你理清这五个概念的关系：

代码示例：组合数计算

下面是一个用C语言实现的组合数计算函数，支持大数：

#include <stdio.h>

// 计算组合数 C(n, k)
long long combination(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    // 利用对称性，取较小的k
    if (k > n - k) k = n - k;
    
    long long result = 1;
    for (int i = 1; i <= k; i++) {
        result = result * (n - k + i) / i;
    }
    return result;
}

int main() {
    printf("C(10, 3) = %lld\n", combination(10, 3));
    printf("C(20, 10) = %lld\n", combination(20, 10));
    return 0;
}

这段代码我用了边乘边除的技巧，避免中间结果溢出。你想想看，如果先算分子再算分母，20! 早就爆 long long 了。

避坑指南

我曾经在实现卡特兰数时，直接用递归公式，结果n=20就跑不动了。后来改成动态规划，瞬间搞定。

还有一次，我在容斥原理的实现中忘了处理符号交替，导致结果全错。调试了一下午才发现。嗯，从那以后我写容斥原理的代码，都会先画个韦恩图确认一下。

---

公众号:蓝海资料掘金营，微信deep3321