组合数公式
组合数公式
组合数公式是数学中的一个重要概念，用于计算从若干不同元素中选取固定数量元素的组合个数。它不仅与二项式定理、杨辉三角等数学概念有着密切联系，还能应用于解决实际问题。本文将详细介绍组合数的定义、计算方法及其应用，帮助读者深入理解这一数学工具。
组合数
定义
考虑一个包含(n)个不同元素的集合，从中选取(k)个元素组成一个子集，满足条件的子集数量即为组合数，记作(C_n^k)或(\binom{n}{k})。形式上，可以写作：
[C_n^k = \binom{n}{k}]
其计算公式为：
[\binom{n}{k} = \frac{n!}{k!(n-k)!}]
计算公式推导
首先考虑从(n)个元素中依次选取(k)个元素。根据分步乘法计数原理，选法共有(n(n-1)(n-2)\cdots(n-k+1))种。这种选法考虑了选择的顺序，得到的结果称为“排列数”，记作(A_n^k)或(P(n,k))：
[A_n^k = P(n,k) = n(n-1)(n-2)\cdots(n-k+1)]
然后，由于选出的(k)个元素不应考虑顺序，因此需要排除上述选法中的重复。从这(k)个元素中考虑顺序地依次全部选出（即全排列），得到所有可能的重复共有(k!)种。
在排列数的基础上除以(k)个元素的全排列数，得到：
[\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}]
这就是组合数的计算公式。
性质
设正整数(n)与(k)，通过上述定义，容易得到以下性质：
- (\binom{n}{k} = \binom{n}{n-k})
- (\binom{n}{0} = \binom{n}{n} = 1)
- 组合数的递推式：(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k})
其他相关内容
二项式定理
定理内容：
对于任意的(n)，均有
[(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^k]
推导过程：
((x+y)^n)展开后，每一项都是(x)和(y)的乘积，其中(x)的次数为(n-k)，(y)的次数为(k)。根据多项式的乘法规则，(x^{n-k}y^k)的系数为“从(n)个括号中挑出(k)个，其中的(y)参与相乘；剩余的(n-k)个括号中的(x)参与相乘”的方法数。这恰好是组合数(\binom{n}{k})。
定理应用：
二项式定理的应用十分广泛，例如可以赋值(x=y=1)得到关于组合数的重要恒等式：
[\sum_{k=0}^{n} \binom{n}{k} = 2^n]
还可以赋值(x=1, y=-1)，得到：
[\sum_{k=0}^{n} \binom{n}{k} (-1)^k = 0]
结合以上两个式子即可得到：
[\sum_{k \text{ is even}} \binom{n}{k} = \sum_{k \text{ is odd}} \binom{n}{k} = 2^{n-1}]
再例如，对等式((1+x)^m(1+x)^n = (1+x)^{m+n})（(m)和(n)是正整数）的左右两边分别使用二项式定理，即得：
[\sum_{i=0}^{m} \binom{m}{i} x^i \cdot \sum_{j=0}^{n} \binom{n}{j} x^j = \sum_{k=0}^{m+n} \binom{m+n}{k} x^k]
为使左右两边对应幂次项的系数相等，可以推出范德蒙德(Vandemonde)恒等式：
[\sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}]
杨辉三角
杨辉三角是一种将数字排列成三角形的方式，其特点是“肩上的两个数相加等于该数”，且两侧边缘为1。用这种方法可以构建出如下图所示的阵列：
以第四排的第二个数“3”为例，其“肩上”的两个数是第二排的前两个数“1”和“2”，其和为3，第四排的第二个数由此确定。
杨辉三角与组合数之间有着紧密的联系：它的第(n)行的第(k)个数，恰为(\binom{n}{k})的值。即：
[a_{n,k} = \binom{n}{k}]
为杨辉三角的第(n)行的第(k)个数。
从中可以直接看出组合数的递推公式为：
[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}]
应用举例
例1：从6门科目中选择3门参加考试，共有多少种选科方式？
解：此即组合数(\binom{6}{3})，故有20种选科方式。
例2：由40个单位正方形拼成的长为8，宽为5的长方形组成一个8×5棋盘（如图），那么从一个顶点到最远顶点的最短路的条数有多少？
解：最短路的选择可以看作是由8条单位横线段与5条单位纵线段排列；这等价于从13条线段中选择8条作为横线段，其余5条作为纵线段，此即组合数(\binom{13}{8})。故最短路共有1287条。
例3：设一个凸八边形中的任意三条对角线都不交于一点，求：由多边形的边与对角线围成的三角形的个数。
解：通过分类讨论，所求三角形可以分为以下四类。
① 三角形的三顶点均为原多边形的顶点。显然此类三角形有(\binom{8}{3})个；
② 有两个顶点是原多边形的顶点，此类三角形可以由两条相交于图形内部的对角线确定。一方面，只需从原凸八边形中选出4个顶点即可确定出这两条对角线；另一方面，这样的两条对角线可以确定出4个所需三角形（见下图(a)）。故此类三角形有(4\binom{8}{4})个；
③ 仅一个顶点是原多边形的顶点，此类三角形需要由三条对角线确定，其中两条对角线经过同一顶点。只需从原凸八边形中选出5个顶点，即可确定出这5组满足该情形的对角线：分别令五个顶点引出两条对角线（见下图(b)）。故此类三角形有(5\binom{8}{5})个；
④ 三顶点均不是原多边形的顶点，此类三角形需要由三条对角线确定，且任意两条对角线不经过同一顶点。只需从原凸n边形中选出6个顶点即可确定出这三条对角线：依一个方向给六个顶点编号后，1与4相连，2与5相连，3与6相连，即可围成唯一的一个三角形（见下图(c)）。故此类三角形有(\binom{8}{6})个。
综上所述，可由分类加法计数原理得知所求三角形的个数为(56+280+280+28=644)个。