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

参考:

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

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

杨辉三角形详解


杨辉三角长这个样子:

\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 的系数。