阶乘，排列，组合

-- TOC --

阶乘

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

显然，n是一个自然数。

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

从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 --