组合数

从n个不同元素中取出k个元素的所有不同组合的个数，叫做组合数。组合数有许多种（相反的）记法：\(C_n^k,\; C_k^n,\; \binom{n}{k}\)。本文采用上大下小的记法。

\(\binom{n}{k}\)的计算方式如下：

若\(n\geqslant k \geqslant 0\)，则\(\binom{n}{k}=\frac{n!}{k!(n-k)!}\)。

否则，\(\binom{n}{k}=0\)。

该计算方式避免了“负数的阶乘”的问题，也直接规定没有办法取出负数个元素。

另外，\(\binom{n}{0}=0\), 这可由阶乘公式计算，但直接记住比较方便。

Related Properties

Vandermonde’s identity

$$
{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}
$$