这里是学习笔记,注意检索关键词

语法引用 $\LaTeX$ ,未显示准确需转码


阶乘

阶乘的定义

正整数的阶乘(Factorial)是所有小于及等于该数的正整数的积,计为 ${n!}$ ,例如5的阶乘计为 ${5!}$ ,其值为120:

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

并定义,

$$1! = 0! = 1$$

其中0的阶乘$0!$表示一个空积(零个因子相乘的结果)

$$n! = \prod \limits_{k=1}^n \times k , \forall n \geqslant 1$$

亦即 $$n! = 1 \times 2 \times 3 \times \cdots \times n$$

阶乘亦可以递归方式定义:

$$0! = 1$$

$$n!={n-1}! \times n$$

当n很大时,可用斯特林公式估计,对于足够大的整数n,这两个数互为近似值:

$${n!} \approx \sqrt{{2}\pi{n}} (\frac{n}{e})^n$$

$${\lim_{x \to +\infty}\frac{{e}^{n}{n!}}{n^n \sqrt{n}} = \sqrt {2 \pi}}$$

其中 $\sqrt{{2}\pi} \approx {2.506628274631}$

基础阶乘值

nn!
01
11
22
36
424
5120
6720
75040
840320
9362880
103628800

组合数

从 n 个不同元素中每次取出 m 个不同元素 $(0 \leqslant m \leqslant n)$ ,

不管其顺序合成一组,称为从 n 个元素中不重复地选取 m 个元素的一个组合

所有这样的组合的种数称为组合数

在线性写法中被写作C(n,m),在二项式系数中被写作 $\tbinom{n}{m}$

即 $C_n^m$

组合数的计算公式为

$$C_n^m = \frac{P_n^m}{P_m} = \frac{n!}{(n-m)!},C_n^0 = 1$$

n 元集合 A 中不重复地抽取 m 个元素作成的一个组合实质上是 A 的一个 m 元子集合

互补性质

$$C_n^m = \frac{P_n^m}{P_m} = \frac{n!}{(n-m)!} = C_n^{n-m}$$

规定:$C_n^0 = 1, C_n^n=1, C_0^0 = 1$

例如 $C_9^2=C_9^7$

从9个元素里选择2个元素的方法从9个元素里选择7个元素的方法是相等的

组合恒等式

若表示在 n 个物品中选取 m 个物品,则如存在下述公式:

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

组合数公式

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

其中排列数为: $$A_n^m = n(n-1)(n-2) \cdots (n-m+1)$$

从n个不相同元素中取出m个排成一列(有序)

第一个位置可以有n个选择,第二个位置可以有n-1个选择(已经有1个放在前一个位置)

则同理可知第三个位置可以有n-2个选择,以此类推第m个位置可以有n-m+1个选择