加法、乘法原理和鸽巢原理。
定义 ： 一个集合是一个无序的不同元素的集合。通常用大括号表示。集合的基数是指集合元素的个数。
定义： 序列是元素的有序集合，允许元素重复。通常用小括号表示。
定义： 集合的排列是一个序列，使得每个该集合的元素出现恰好一次。$n$个元素的集合的排列个数是$n!$，第一个位置有$n$个选择，第二个只剩下$n-1$ ，……依次下去。
定义： 一个函数 $f:X\to Y$是一个$X,Y$上的关系，使得每个$X$中的元素只与$Y$中的一个元素有关。称$X$ 为定义域，$Y$ 为值域。
定义：
满射是指每个 $Y$ 中的元素都被映射到至少一次。
单射是指每个 $Y$ 中的元素都被映射到至多一次。
双射是指每个 $Y$ 中的元素都被映射到恰好一次。也就是既单又满。
映射法则
$f:X\to Y$是满射$\implies |X|\ge |Y|$
$f:X\to Y$是单射$\implies |X|\leq |Y|$
$f:X\to Y$是双射$\implies |X|=|Y|$ (双射法则)
广义鸽巢原理
如果 $|X|=k|Y|$，那么$\forall f:X\to Y, \exists k+1$个不同的$X$中的元素被映射到同一个$Y$中的元素。$k=1$ 时就是通常的鸽巢原理。可以利用反证法证明。
Ex.随便取十个二位数，子集有 $2^{10}$ 个，那么一定有至少两个子集的和相等。当然按照广义的定理可以得到更高的下界。
一个 $k-to-1$的函数$f:X\to Y$是指，每个$Y$中的元素都被$k$个$X$中的元素映射到，此时$|X|=k|Y|$ 。也被称为除法原理。
广义乘法原理
设 $S$是一个长度为$k$的序列，如果有$n_1$个可能的第一个元素，对每个第一个元素有$n_2$个可能的第二个元素……那么$|S|=n_1\cdot n_2 \dots \cdot n_k$ 。
Ex. $n$个人，选出来三个人分别在接下来的三天工作。$n\cdot (n-1)\cdot (n-2)$ 种情况。这件事在高中是常见的（
集合的笛卡尔积：
$$ A_1\times ... \times A_n=\{(a_1,...,a_n),a_i\in A_i\} $$
乘法原理给出：
$$ |A_1\times ... \times A_n|=|A_1|...|A_n| $$
加法原理
不交集合 $A_1,…,A_n$ 的并的基数是各集合基数的和：
$$ |A_1\cup ...\cup A_n|=|A_1|+...+|A_n| $$
这同样是高中熟悉的。按下不表。