组合数学里面的杨辉三角公式

杨辉三角，也叫帕斯卡三角，是一个由数字组成的三角形，其中第n行有n个数字。每一行的两个端点都是1，其它数字是上一行相邻两个数字之和。杨辉三角有许多有趣的性质，如其中的每个数字都是组合数，且满足对称性等。

杨辉三角公式是用来计算组合数的一种方法，可以通过它快速计算任意n和k的组合数C(n, k)。它基于杨辉三角中的性质，即每个数字都是上一行相邻两个数字之和。假设我们已经计算出杨辉三角中的前n行，可以使用以下公式来计算C(n, k)：

C(n, k) = C(n-1, k-1) + C(n-1, k)

这个公式的意思是，要计算C(n, k)，我们需要知道C(n-1, k-1)和C(n-1, k)的值，这两个值可以在杨辉三角的前n-1行中找到。

使用杨辉三角公式来计算组合数的好处是，它不需要计算阶乘，因此在计算较大的组合数时效率更高。此外，由于杨辉三角具有对称性，可以使用该对称性来优化计算，从而使计算效率更高。

下面是一个使用C++实现的示例代码，该代码使用杨辉三角公式来计算组合数：

#include <iostream>
using namespace std;

// 定义计算组合数的函数
int combination(int n, int k) {
  int C[n+1];
  memset(C, 0, sizeof(C)); // 初始化C数组为0
  C[0] = 1; // 边界条件
  for (int i = 1; i <= n; i++) {
    for (int j = min(i, k); j > 0; j--) {
      C[j] = C[j] + C[j-1]; // 递推公式
    }
  }
  return C[k];
}

int main() {
  int n = 5, k = 2;
  cout << "C(" << n << ", " << k << ") = " << combination(n, k) << endl;
  return 0;
}

在这个代码中，combination函数使用杨辉三角公式来计算组合数。它定义了一个一维数组C，其中C[j]表示C(i, j)的值。首先，它将C[0]初始化为1，这是递推的边界条件。然后，使用两个嵌套的循环来计算C[i][j]的值。内循环从min(i, k)开始，以递减的顺序遍历C数组。在每次迭代中，使用递推公式C[j] = C[j] + C[j -1]; 来更新C[j]的值。最后，函数返回C[k]作为C(n, k)的值。

在主函数中，我们使用n=5和k=2来计算C(5, 2)的值，并将结果输出到控制台。运行该程序，输出结果为：

C(5, 2) = 10

这个结果表明，C(5, 2)的值为10，与手工计算的结果一致。这表明该程序成功地使用杨辉三角公式计算了组合数。

当然，我们也可以将计算杨辉三角和计算组合数的过程分开来。下面是一个计算杨辉三角的示例代码：

#include <iostream>
using namespace std;

// 定义函数来打印杨辉三角
void print_pascal_triangle(int n) {
  int C[n+1][n+1];
  memset(C, 0, sizeof(C)); // 初始化C数组为0
  for (int i = 0; i <= n; i++) {
    C[i][0] = 1; // 第一列全是1
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      C[i][j] = C[i-1][j-1] + C[i-1][j]; // 递推公式
    }
  }
  // 打印杨辉三角
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      cout << C[i][j] << " ";
    }
    cout << endl;
  }
}

int main() {
  int n = 5;
  print_pascal_triangle(n);
  return 0;
}

这个程序中，我们定义了一个函数print_pascal_triangle，该函数使用杨辉三角公式计算并打印前n行杨辉三角。它使用一个二维数组C来保存杨辉三角中的数字。首先，我们将C数组初始化为0，并将第一列设置为1。然后，使用两个嵌套的循环来计算杨辉三角中的数字。在每次迭代中，使用递推公式C[i][j] = C[i-1][j-1] + C[i-1][j]来计算C[i][j]的值。最后，打印整个杨辉三角。

在主函数中，我们使用n=5来计算前5行杨辉三角，并将其打印到控制台。运行该程序，输出结果为：

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1

这个结果表明，该程序成功地计算并打印了前5行杨辉三角。

当然，在实际编程中，我们通常不会使用递归来计算组合数或杨辉三角，因为递归算法通常效率较低。相反，我们可以使用迭代算法来计算组合数和杨辉三角。下面是一个使用迭代算法计算组合数的示例代码：

#include <iostream>
using namespace std;

// 定义函数来计算组合数
int calculate_combination(int n, int k) {
  int C[n+1][k+1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= min(i, k); j++) {
      if (j == 0 || j == i) {
        C[i][j] = 1;
      } else {
        C[i][j] = C[i-1][j-1] + C[i-1][j];
      }
    }
  }
  return C[n][k];
}

int main() {
  int n = 5, k = 2;
  int Cnk = calculate_combination(n, k);
  cout << "C(" << n << ", " << k << ") = " << Cnk << endl;
  return 0;
}

这个程序中，我们定义了一个函数calculate_combination来使用迭代算法计算组合数。该函数使用一个二维数组C来保存杨辉三角中的数字。使用两个嵌套的循环来计算杨辉三角中的数字。在每次迭代中，使用递推公式C[i][j] = C[i-1][j-1] + C[i-1][j]来计算C[i][j]的值。最后，函数返回C[n][k]作为C(n, k)的值。

在主函数中，我们使用n=5和k=2来计算C(5, 2)的值，并将结果输出到控制台。运行该程序，输出结果为：

C(5, 2) = 10

这个结果表明，C(5, 2)的值为10，与手工计算的结果一致。这表明该程序成功地使用迭代算法计算了组合数。