组合数

定义

从 个不同元素中取出 个组成一个集合（不考虑顺序），产生的不同集合数量就是组合数，记作

性质：

1通式：

我们从 个元素中取 个，那么第 个有 种选法，第 个有 种选法，以此类推，第 个有 种选法，故应

但是由于不考虑顺序，而最后选出的每一种方案都对应着 种顺序（因为有 个），所以还要除以 ，即最后的表达式为.

2.

我们每次从 个元素中取出 个，那么剩下的 个元素也组成一个集合，这两个集合一一对应，所以从 个中取 个和取

3.

考虑是否取第 个元素。若取第 个元素，那我们就要从剩下的 个元素中选出 个来，即 。同理，若不取第 个元素，那我们就要从剩下的 个元素中选出 个来，即 。加起来就是 。
这个公式可以让我们在

4.（即：)

每个元素都有 种取法（要么取，要么不取），所以总方案数是 。

代表的就是总方案数，那就是

5.（即：）

由于

那么前两项就可以化成：

通过性质3可知，与第三项合并合并得到,依次类推到最后一项就是：

这个公式的推论：

运用前缀和的思想：

。

所以：

那么运用这个公式可以求出“““一段”””组合数之和。

6.

使用数学归纳法证明：

当时，成立。

现在假设当时假设成立，那么当时：

把乘进去

得证。