笔记 – 杨辉三角

在探究组合数的时候，有一种杨辉三角求组合数的方法。为什么可以用杨辉三角求组合数呢？因为它们的递推关系是类似的。

参考：

【算法零基础学习】组合数与杨辉三角

组合数学之杨辉三角与组合数

杨辉三角形详解

杨辉三角长这个样子：

\begin{aligned}
&1\cr
1&\texttt{ }1\cr
1\texttt{ }&2\texttt{ }1\cr
1\texttt{ }3&\texttt{ }3\texttt{ }1\cr
1\texttt{ }4\texttt{ }&6\texttt{ }4\texttt{ }1
\end{aligned}

• 每一个数等于其右上的数加其左上的数
• 每行数字左右对称
• 第 n 行的数字有 n 个
• 第 n 行的第 m 个数可以表示为 C_{n – 1}^{m – 1}，即为从 n-1个数中取 m-1 个元素的组合数。
  • 推导：C_{n}^{m} = C_{n – 1}^{m} + C_{n – 1}^{m – 1}，与杨辉三角递推公式一致。
• 第 n + 1 行的数字对应着 (a + b) ^ n 的系数。