【📄笔记📄】上半区问题路线数计算（卡特兰数列）公式推导（? - 校内/校外

组合‌$C_{n}^{m}$：从n个元素中取出m个元素，不考虑顺序，只关注元素的组合方式。例如，从A、B、C中取出两个元素，AB和BA被视为同一个组合。

‌排列‌$A_{n}^{m}$：从n个元素中取出m个元素，考虑顺序。例如，AB和BA被视为不同的排列。

$C_{1}^{1} = 1$

$C_{n}^{1} = n$

$C_{n}^{n} = 1$

$C_{m}^{n} = \frac{A_{m}^{n}}{A_{n}^{n}} = \frac{m!}{n!*(m - n)!} = C_{m}^{m - n}$

$C_{m}^{n} = C_{m - 1}^{n - 1} * C_{m - 1}^{n}$

$C_{m}^{n} = C_{m}^{n - 1} * \frac{m - n + 1}{n}$

↑

这个公式为什么一定能整除？

提示：因式分解

$A_{1}^{1} = 1$

$A_{n}^{1} = n$

$A_{n}^{n} = n! = n * (n - 1) * …… * 1$

$A_{m}^{n}= \frac{A_{m}^{m}}{A_{n}^{n}} = \frac{m!}{(m - n)!}=m * (m - 1) * …… * (m - n + 1)$