排列与组合

2.1 基本计数原理

2.1.1 加法原理

定义一个集合 \(S\) 的划分 \(S_1,S_2,...,S_n\)，满足 \(\bigcup\limits_{i=1}^n S_i=S\) 并且 \(\forall i,j(1\leq i,j \leq n,i\neq j) S_i \bigcap S_j=\phi\)，我们有 \(|S|=\sum\limits_{i=1}^{n}|S_i|\)

证明很显然，但是加法原理只适用于所有的子集互不相交的情况，而要处理有相交的状况，在后面的章节会提到容斥原理来计算