组合数

Owen大约 2 分钟

概念

从 n 个不同元素中，任取 m $（ m \leq n ）$ 个元素并成一组，叫做从 n 个元素中取出 m 个元素的一个组合；从 n 个不同元素中取出 m $（ m \leq n ）$ 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数。

定义

组合是数学的重要概念之一。从 n 个不同元素中每次取出 m 个不同元素 $（ 0 \leq m \leq n ）$ ，不管其顺序合成一组，称为从 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组合的种数称为组合数。

计算公式

在线性写法中： $C (n, m)$
组合数的计算公式：

C_{n}^{m} = \frac{P_{n}^{m}}{P_{m}} = \frac{n!}{m! * (n - m)!}, C_{1}^{0} = 1

n 元集合 A 中不重复地抽取 m 个元素作成的一个组合实质上是 A 的一个 m 元子集合。如果给集 A 编序$ A = {a_1,a_2, a_3, ... , a_n } $成为一个序集，那么 A 中抽取 m 个元素的一个组合对应于数段 $N_{m} = {1, 2, 3, . . ., m}$ 到序集 A 的一个确定的严格保序映射。组合数的常用符号还有 $(_{n}^{m}), C (n, m), . . . .$

性质

互补性质即从 n 个不同元素中取出 m 个元素的组合数 = 从 n 个不同元素中取出（n-m）个元素的组合；即：

C (n, m) = C (n, n - m)

C_{n}^{m} = C_{n}^{(n - m)}

规定：

C (n, 0) = 1

C (n, n) = 1

C (0, 0) = 1

组合恒等式若表示在 n 个物品中选取 m 个物品，则如存在下述公式：

C (n, m) = C (n, n - m) = C (n - 1, m - 1) + C (n - 1, m)