【编程数论】排列与组合

组合数是组合数学里的概念，用于计算 “从 $n$ 个元素中选 $k$ 个元素，有多少种不考虑顺序的选法”。比如从 $10$ 个不同的小球里选 $3$ 个，不管先选哪个后选哪个，只要最终选出的是这 $3$ 个小球，就算同一种选法，这时候就用 ${\mathrm{C}}_{10}^3$ 计算选法总数 ，通用写法就是：Cnk，也可以用(kn)，$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ （规范写法是 $n$ 在上、$k$ 在下 ）就是组合数。

组合数有专门的计算公式：
(kn)=Cnk=k!(n−k)!n!

对于 ${\mathrm{C}}_{10}^3$ ，把 $n=10$，$k=3$ 代入公式：$$\begin{array}{rl}{\mathrm{C}}_{10}^3& =\frac{10!}{3!(10-3)!}\\ & =\frac{10!}{3!\times 7!}\\ & =\frac{10\times 9\times 8\times 7!}{3\times 2\times 1\times 7!}\\ & =\frac{10\times 9\times 8}{3\times 2\times 1}\\ & =120\end{array}$$

计算时，$7!$ 可以约掉，简化后得到结果是 $120$ ，意思就是从 $10$ 个元素里选 $3$ 个元素，不考虑顺序的话，一共有 $120$ 种不同的选法 。

和组合数容易混淆的是排列数（比如 ${\mathrm{A}}_{10}^3$ ），排列数计算的是 “从 $n$ 个元素中选 $k$ 个元素并考虑顺序的排列方式总数” 。排列数公式是 ${\mathrm{A}}_n^k=\frac{n!}{(n-k)!}$ ，对比组合数，会发现组合数因为不考虑顺序，要把排列数里重复计算的顺序 “除掉”（除以 $k!$ ），所以组合数结果一般比对应排列数小 。

比如 ${\mathrm{A}}_{10}^3=\frac{10!}{(10-3)!}=10\times 9\times 8=720$ ，明显比 ${\mathrm{C}}_{10}^3=120$ 大，就是因为排列数考虑了选出 $3$ 个元素内部不同的排列顺序，而组合数不考虑 。

简单说，${\mathrm{C}}_{10}^3$ 就是算从 $10$ 个里选 $3$ 个 “不排顺序” 的选法总数，结果是 $120$ ，常用来解决组合数学里的计数、概率等问题，像计算抽奖中奖概率、选代表的方案数等场景都会用到它 。