什么是组合公式（nCr）？

• 从 个不同物体中，取出 个，总共有 种不同的组合。公式如下：

• 例：从 这 3 个字母中，取出 2 个，能有多少不同的组合？
• 注意：组合只关心组合的物体而不关心顺序！所以 和 算是同一种。

阶乘函数实现

• 于是，使用我们之前学习过的阶乘函数 factor() 就能按照公式得出一个算法。

1
2int c(int n, int r)
3{
4int t1, t2, t3;
5t1 = factor(n);
6t2 = factor(r);
7t3 = factor(n - r);
8return t1 / (t2 * t3);
9}
10

• 其中， 就是公式的 , 和 。

杨辉三角形递归实现

• 我们还有另一种实现方法，即杨辉三角算法。
• 杨辉三角的每一项就正好对应着 的每种情况（见下图）：

• 于是现在就有 2 种情况需要我们处理：

1. 当 r == 0 或 r == n 时，我们可以直接返回 1。
2. 其余情况，我们以 为例：
   • 所以我们可以推导出 。

• 最后，我们就可以开始写算法了：

1
2int c(int n, int r)
3{
4if (r == 0 || n == r)
5return 1;
6return c(n - 1, r - 1) + c(n - 1, r);
7}
8