两个基本原理#

• 加法原理： 做一件事有若干类互不重叠的办法，每类分别有 a₁, a₂, … 种方式，则总方案数为 a₁ + a₂ + …。
• 乘法原理： 做一件事分成若干连续的步骤，每步分别有 b₁, b₂, … 种选择，则总方案数为 b₁ × b₂ × …。

几乎所有计数问题都是这两个原理的组合：先”分类”（加法）再”分步”（乘法）。

排列与组合#

• 排列数： 从 n 个不同元素中选出 m 个排成一列，方案数 A(n, m) = n! / (n - m)!。
• 组合数： 从 n 个不同元素中选出 m 个（不考虑顺序），方案数 C(n, m) = n! / (m!(n - m)!)。 组合与排列差一个 m! 倍：排列 = 组合 × 选出的 m 个元素内部的排列数。

常用性质：

• 对称性： C(n, m) = C(n, n - m)（选 m 个等价于排除 n - m 个）；
• 递推式： C(n, m) = C(n-1, m) + C(n-1, m-1)（按”第 n 个元素选或不选”分类，加法原理）；
• 二项式定理： (x + y)^n = Σ C(n, k)·x^k·y^{n-k}，这也是组合数名称的由来。

组合数的四种求法（按数据范围选择）#

递推求组合数模板#

1
import java.util.*;
2

3
public class Main {
4
    static final int N = 2010;
5
    static final int MOD = (int) 1e9 + 7;
6
    static int[][] c = new int[N][N];
7

8
    // 递推预处理所有组合数 C[i][j]（i, j < N）
9
    static void init() {
10
        for (int i = 0; i < N; i++)
11
            for (int j = 0; j <= i; j++)
12
                if (j == 0) c[i][j] = 1;
13
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
14
    }
15

16
    public static void main(String[] args) {
17
        Scanner sc = new Scanner(System.in);
18
        init();
19
        int n = sc.nextInt();
20
        while (n-- > 0) {
21
            int a = sc.nextInt(), b = sc.nextInt();
22
            System.out.println(c[a][b]);
23
        }
24
    }
25
}

卡特兰数#

问题原型： 求”n 个 +1 和 n 个 -1 组成的序列中，任意前缀和 ≥ 0 的合法序列个数”，等价于很多经典计数问题：n 对括号的合法匹配方案数、n 个元素依次入栈的不同出栈序列数、n+1 个叶子的满二叉树个数、凸 n+2 边形三角剖分方案数等。

公式： 卡特兰数

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

递推式： C₀ = 1，Cₙ₊₁ = Σ Cᵢ·Cₙ₋ᵢ（按”第一对括号匹配的位置”分类，乘法原理 + 加法原理）。

理解”合法括号”计数： 2n 个位置任选 n 个放左括号共 C(2n, n) 种；其中非法的部分（存在前缀右括号多于左括号）可以通过”第一次越界处整体翻转”一一对应到”n+1 个左括号、n-1 个右括号”的序列，共 C(2n, n+1) 种。两者相减即得合法方案数。