这里是学习笔记,注意检索关键词
语法引用 $\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}$
基础阶乘值
n | n! |
---|---|
0 | 1 |
1 | 1 |
2 | 2 |
3 | 6 |
4 | 24 |
5 | 120 |
6 | 720 |
7 | 5040 |
8 | 40320 |
9 | 362880 |
10 | 3628800 |
组合数
从 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个选择