二项式系数

组合数

组合数 $C_m^n$（有时记作$C_n^k$,或者${}_n{C}_k$）, 表示从 $m$ 个不同的元素中选择 $n$ 个元素的方式的数量，而不考虑选择的顺序。计算组合数 $C_m^n$ 的公式如下：
$C_m^n=\frac{n!(m-n)!}{m!}$

例如，要计算$C_5^2$，即从5个不同的元素中选择2个元素的方式的数量，可以这样计算：
$C_5^2=\frac{2!\cdot (5-2)!}{5!}=\frac{2!\cdot 3!}{5!}=\frac{(2\cdot 1)\cdot (3\cdot 2\cdot 1)}{5\cdot 4\cdot 3\cdot 2\cdot 1}=10$
所以，$C_5^2$ 等于10，表示从5个不同的元素中选择2个元素的方式有10种。

也可以写成以下更对称的形式:
$C_{m+n}^n=\frac{m!\cdot n!}{(m+n)!}=C_{m+n}^m$
表示从 $m+n$ 个元素中选出m个元素或n个元素, 这两种情况的组合数相等

---

Wikipedia

定义及概念

对于非负整数$n$,$k$, 二项式系数定义为$(1+x{)}^n$的多项式展开中, $x^k$的系数
$(1+x{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k=(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})x+\cdots +(\genfrac{}{}{0ex}{}{n}{n})x^n$
事实上，若$x$, $y$为交换环上的元素，则满足二项式定理
$(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$

阶乘公式

二项式系数最简洁的表达式是阶乘:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}\text{for }0\le k\le n.$$

递归公式

以下递归公式可计算二项式系数：

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)\forall n,k\in \mathbb{N}$$

其中特别指定：

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1\forall n\in \mathbb{N}\cup \{0\},$$ $$\left(\genfrac{}{}{0ex}{}{0}{k}\right)=0\forall k\in \mathbb{N}.$$

此公式可由计算 $(1+x{)}^{n-1}(1+x)$ 中的 $x^k$ 项，或点算集合 $\{1,2,\cdots ,n\}$ 的 $k$ 个元素组合中包含 $n$ 与不包含 $n$ 的数量得出。

显然，如果 $k>n$，则 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$。而且对所有 $n$，$\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。

乘数公式

个别二项式系数可用以下公式计算：

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n^{\underline{k}}}{k!}=\frac{n(n-1)(n-2)\cdots [n-(k-1)]}{k(k-1)(k-2)\cdots 1}=\prod _{i=1}^k\frac{n-(k-i)}{i},$$

上式中第一个分数的分子是一阶乘幂。此公式可以二项式系数在计算组合数量的意义理解：分子为从 $n$ 个元素中取出 $k$ 个元素的序列之数量，当中包含同样的元素但不同排列次序的序列。分母则计算同样的 $k$ 个元素可有多少种排序方式。