从若干不同元素中，任取固定数量的元素合成一组，能够形成的组合的个数，称为组合数。关于组合数的其它恒等式有很多种，其与二项式定理、杨辉三角等也有密不可分的关系。

考虑一个元素集合的子集，的元素个数为。满足条件的的个数即为组合数 。有时也记为。

此即组合数的定义，形式上，可以写为

其计算公式为

首先考虑从个元素中依次选出个元素。由分步乘法计数原理，选法有 种。此选法考虑了选择的顺序，得到的结果又称为“排列数”，记为或：

然后，由于选出的个元素应当不计顺序，故需排除上述选法中的重复。从这个元素中考虑顺序地依次全部选出（又称“全排列”），即得到所有可能的重复有共种。

在排列数的基础上除以个元素的全排列数，得到

此即组合数的计算公式。

设正整数与，通过上述定义，易得：

1. ；；

2.；

3. 组合数的递推式。

定理内容：

对于任意的，均有

推导过程：

，由多项式的乘法规则，所得多项式中，的系数为“从中挑出个，其中的参与相乘；剩余的中的参与相乘”的方法数。此恰为组合数。

定理应用

二项式定理的应用十分广泛，例如可以赋值得到关于组合数的重要恒等式：

还可以赋值，得到：

结合以上两个式子即可得到：

再例如，对等式（和是正整数）的左右两边分别使用二项式定理，即得：

为使左右两边对应幂次项的系数相等，可以推出范德蒙德(Vandemonde)恒等式：

杨辉三角是一种将数字排列成三角形的方式，其特点是“肩上的两个数相加等于该数”，且两侧边缘为1；用这种方法可以构建出如下图所示的阵列：

以第四排的第二个数“3”为例，其“肩上”的两个数是第二排的前两个数“1”和“2”，其和为3，第四排的第二个数由此确定。

杨辉三角与组合数之间有着紧密的联系：它的第行的第个数，恰为的项系数。即：为杨辉三角的第行的第个数。

从中可以直接看出组合数的递推公式为

例1 从6门科目中选择3门参加考试，共有多少种选科方式？

解：此即组合数，故有20种选科方式。

例2 由40个单位正方形拼成的长为8，宽为5的长方形组成一个8×5棋盘（如图），那么从一个顶点到最远顶点的最短路的条数有多少？

解：最短路的选择可以看作是由8条单位横线段与5条单位纵线段排列；这等价于从13条线段中选择8条作为横线段，其余5条作为纵线段，此即组合数。故最短路共有1287条。

例3 设一个凸八边形中的任意三条对角线都不交于一点，求：由多边形的边与对角线围成的三角形的个数。

解：通过分类讨论，所求三角形可以分为以下四类。

① 三角形的三顶点均为原多边形的顶点。显然此类三角形有个；

② 有两个顶点是原多边形的顶点，此类三角形可以由两条相交于图形内部的对角线确定。一方面，只需从原凸八边形中选出4个顶点即可确定出这两条对角线；另一方面，这样的两条对角线可以确定出4个所需三角形（见下图(a)）。故此类三角形有个；

③ 仅一个顶点是原多边形的顶点，此类三角形需要由三条对角线确定，其中两条对角线经过同一顶点。只需从原凸八边形中选出5个顶点，即可确定出这5组满足该情形的对角线：分别令五个顶点引出两条对角线（见下图(b)）。故此类三角形有个；

④ 三顶点均不是原多边形的顶点，此类三角形需要由三条对角线确定，且任意两条对角线不经过同一顶点。只需从原凸n边形中选出6个顶点即可确定出这三条对角线：依一个方向给六个顶点编号后，1与4相连，2与5相连，3与6相连，即可围成唯一的一个三角形（见下图(c)）。故此类三角形有个。

综上所述，可由分类加法计数原理得知所求三角形的个数为56+280+280+28=644个。