从 n 个不同元素 中,不考虑顺序 选出 m 个,所有不同的选法个数记作组合数 C(n, m)。
当 1 ≤ m ≤ n 时,有公式:
C(n, m) = n! ÷ (m! × (n - m)!)
当 m = 0 或 m = n 时,只有一种选法,所以 C(n, 0) = C(n, n) = 1。
在信息学竞赛中,经常需要根据题意把「只关心选哪些,不关心顺序」的问题,抽象成组合数 C(n, m),再结合取模运算或预处理阶乘来高效计算。
计算过程:
以下是从 1 到 n 中选出 m 个元素得到的所有不同组合(只关心选哪些,不关心顺序;当 n、m 较小时才全部列出)。左侧为序号,右侧为过程。
| 序号 | 过程 |
|---|