阶乘，排列，组合

Last Updated: 2024-05-01 03:47:11 Wednesday

-- TOC --

阶乘（Factorial）
排列（Permutation）
组合（Combination）

阶乘（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)$

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

阶乘有多大？

>>> a = 1
>>> for i in range(1,30):
...   a *= i
...   print(i,len(str(a)),a)
...
1 1 1
2 1 2
3 1 6
4 2 24
5 3 120
6 3 720
7 4 5040
8 5 40320
9 6 362880
10 7 3628800
11 8 39916800
12 9 479001600
13 10 6227020800
14 11 87178291200
15 13 1307674368000
16 14 20922789888000
17 15 355687428096000
18 16 6402373705728000
19 18 121645100408832000
20 19 2432902008176640000
21 20 51090942171709440000
22 22 1124000727777607680000
23 23 25852016738884976640000
24 24 620448401733239439360000
25 26 15511210043330985984000000
26 27 403291461126605635584000000
27 29 10888869450418352160768000000
28 30 304888344611713860501504000000
29 31 8841761993739701954543616000000
>>> len(str(2**32))  # uint32
10
>>> len(str(2**64))  # uint64
20

排列（Permutation）

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

组合（Combination）

从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在下。

$$\sum_{i=0}^nC_n^i=2^n$$

n个元素的所有组合数，就是上面这个计算公式。

本文链接：https://cs.pynote.net/math/202207091/

-- EOF --

-- MORE --