定义

排列

从 n 个不同的元素中，任取 m 个元素按照一定的顺序构成一个序列的方案数，叫做从 n 个元素中取出 m 个元素的排列数。

排列数记为 A(n, m) 或 Anm。

组合

从 n 个不同的元素中，任取 m 个元素无序构成一个集合的方案数，叫做从 n 个元素中取出 m 个元素的组合数。

组合数记为 C(n, m) 或 Cnm，最常用的是 。

计算公式

常见公式

数学证明

组合意义证明

从 n 个人中选取 m 个人留下，等同于 n 个人中选取 n − m 个人让他们离开。

数学证明

组合意义证明

从 n 个人中选取 m 个人留下，可以分两类讨论：

  • 第 n 个人被选中了：此时还要从剩下的 n − 1 人中选取 m − 1 个人，故方案数为 。
  • 第 n 个人没被选中：此时还要从剩下的 n − 1 人中选取 m 个人，故方案数为 。

综上，总方案数 。

证明

考虑从 n 个人中选出任意个留下（可以不选），询问有多少种方案。

  • 对于每个人考虑，每个人有留下或者不留下两种情况，所以总方案数为 2n。
  • 对于选的人考虑，枚举选出的人数 i ∈ [0, n]，总情况数就是 。

综上， 可得 。

二项式定理：

证明

式子的含义是对于 ∀ i ∈ [0, n]，求 xiyn − i 的系数。

这相当于从 n 个物品中选 i 个给 x，选 n − i 个给 y 的方案数，所以其系数为 。

由于该式子的存在，组合数也常被成为二项式系数。

应用

用二项式定理求证 。

证明：

证明

应用

该公式提醒我们，在杨辉三角内，对于同一行的组合数，奇数位置的和与偶数位置的和相等。

即

公式集合