阶乘，排列，组合

Last Updated: 2024-03-01 12:21:10 Friday

-- TOC --

阶乘（Factorial）

$n!=n\cdot(n-1)\cdot(n-2)\cdots3\cdot2\cdot1$

显然，n是一个自然数。

零也属于自然数，规定：$0!=1$

6=2*3，2和3就是6的factor。factor这个单词可以翻译成（乘法）因子或因式。-ial后缀表示connecting with或relate to。

Stirling's Approximation

$$n!=\sqrt{2\pi n}\left(\cfrac{n}{e}\right)^n\left(1+\Theta\left(\cfrac{1}{n}\right)\right)$$

$n!=o(n^n)$

$n!=\omega(2^n)$

$\log{n!}=\Theta(n\log n)$

以上几个公式，在做算法分析的时候，会很有用。

从n个不同的元素中，拿出m个，$m \le n$，有多少种不同的拿取方法？

就算是拿m个相同的元素，也会因为拿取的顺序不同，造成拿取方法的不同，因此这是个排列问题。

$A_n^m$被称为排列数：

$$A_n^m = n\cdot(n-1)\cdot(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}$$

当$m=n$时，$A_n^m=A_n^n=n!$

当$m=0$时，$A_n^m=1$

从n个不同的元素中，拿出m个，$m \le n$，不考虑m个元素的拿取顺序，有多少种不同的拿取方法？

当不考虑拿取顺序的时候，完全相同的m个元素，不管用什么顺序拿取，都是一样的，算一种方法。由于m个元素排列数为$A_m^m=m!$，我们可以得到组合数：

$$C_n^m = \frac{A_n^m}{A_m^m} = \frac{n!}{(n-m)!\cdot m!}$$

另外，拿出m个元素，与保留n-m的元素的组合一样：

$$C_n^m = C_n^{n-m}$$

还可以分场景计算：

$$C_{n+1}^m = C_n^m + C_n^{m-1}$$

当$m=0 \text{ or } m=n$时，$C_n^m = 1$

在很多地方，组合数还有一种表示方法：$\binom{n}{m}$，这种表达方式，n在上m在下。

-- EOF --

-- MORE --