简单组合数学

概念讲解

排列数

从 n 个不同元素中取 m 个进行排列：

Anm=n!(n−m)!A_n^m = \frac{n!}{(n-m)!}

组合数

从 n 个不同元素中取 m 个进行组合：

Cnm=(nm)=n!m!(n−m)!C_n^m = \binom{n}{m} = \frac{n!}{m!(n-m)!}

杨辉三角

性质

Cnm=Cn−1m−1+Cn−1mC_n^m = C_{n-1}^{m-1} + C_{n-1}^m

实现

1234567891011const int N = 1005;
long long C[N][N];

void init() {
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

组合数取模

123456789101112const int MOD = 1e9 + 7;
const int N = 1005;
long long C[N][N];

void init() {
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

考点分析

初赛考查方式

  1. 选择题： 组合数计算
  2. 程序阅读： 杨辉三角
  3. 编程题： 计数问题

常见考点

  • 排列组合公式
  • 杨辉三角性质
  • 组合数取模

例题精讲

例题 1：组合数

题目： C52C_5^2 是多少？

解答：

C52=5!2!3!=10C_5^2 = \frac{5!}{2!3!} = 10

例题 2：杨辉三角

题目： 杨辉三角第 5 行是什么？

解答：

1 4 6 4 1

练习题

  1. CnmC_n^m 和 Cnn−mC_n^{n-m} 的关系是什么？
查看答案

相等，即 Cnm=Cnn−mC_n^m = C_n^{n-m}

证明：Cnm=n!m!(n−m)!=n!(n−m)!m!=Cnn−mC_n^m = \frac{n!}{m!(n-m)!} = \frac{n!}{(n-m)!m!} = C_n^{n-m}

例如：C52=C53=10C_5^2 = C_5^3 = 10

  1. 杨辉三角的递推公式是什么？
查看答案

Cnm=Cn−1m−1+Cn−1mC_n^m = C_{n-1}^{m-1} + C_{n-1}^m

含义：从 n 个元素中选 m 个 = 包含某个特定元素的方案 + 不包含该元素的方案

  1. 组合数取模的方法是什么？
查看答案

使用杨辉三角递推：

1234567891011const int MOD = 1e9 + 7;
long long C[N][N];

void init() {
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

注意：在计算过程中取模，防止溢出。

易错点

⚠️ 注意：

  1. 排列有序，组合无序
  2. Cn0=1C_n^0 = 1
  3. 杨辉三角可以用递推预处理
  4. 取模要在计算过程中进行