组合数学阅读笔记-第2章:排列与组合

2.1 基本计数原理

2.1.1 加法原理

集合$S$被分成两两不相交的集合$S_1,S_2,S_3,……,S_k$，有

$$|S|=|S_1|+|S_2|+|S_3|+......+|S_k|$$

2.1.2 乘法原理

集合$S$是有序对$(a,b)$的集合，其中a来自$S_a$，b来自$S_b$

$$|S|=|S_a|*|S_b|$$

2.1.3 减法原理

令集合$A\in U$，$A’={x|x\in U,x\notin A}$

$$|A|=|U|-|A'|$$

2.1 4 除法原理

把有限集合$S$分成k个部分是的每一部分包含的对象数目相同

$$k=\frac{|S|}{在一个部分中的对象数目}$$

2.2 集合的排列

$$P(n,m)=\frac{n!}{(n-m)!}$$ $$\frac{P(n,m)}{m}=\frac{n!}{m(n-m)!}(循环排列公式)$$

2.3 集合的组合

$$C(n,m)=\frac{n!}{m!(n-m)!}$$ $$C(n,m)=C(n-1,m)+C(n-1,m-1)$$ $$C(n,0)+C(n,1)+C(n,2)+......+C(n,n)=2^n$$

2.4 多重集合的排列

$$\frac{n!}{n_1!n_2!...n_k!}=C(n,n_1)*C(n-n_1,n_2)*...*C(n-n_1-n_2-...-n_{k-1},n_k)$$

2.5 多重集合的组合

$$C(r+k-1,r)=C(r+k-1,k-1)(k种元素类型的无限集的r组合个数)$$

2.6 有限概率

在样本空间为$S$的实验中，事件$E$的概率定义为$S$中属于$E$的结果的比率

$$Prob(E)=\frac{|E|}{|S|}$$