组合数学
鸽巢原理
-
定理：若有 n 个鸽巢，n+1 只鸽子，则至少有一个鸽巢里至少有两只鸽子。
例 1-1：
一年 365 天，今有 366 个人，则其中至少有两个人生日相同。
例 1-2：
抽屉里有 10 双手套，从中取 11 只出来，其中至少有两只是完 整配对的。
例 1-3. 取数问题：
求证： 从 1,2,...,2n 中最多能取n个数，使取出的这些数两两不整除。
证明：分成n个集合，第i个集合包含数 (2i−1)×2^k,k≥ 0，那么任取 n+1 个数，则有一个集合里有两个数，它们是整除关系，同时，如果 取 n+ 1,n+ 2,...,2n 这 n 个数，则不存在整除关系。
加强形式：若有 n 个鸽巢，m1 +m2 +···+mn−n+1只鸽子，则存在i使得鸽巢i中至少有 mi只鸽子。
推论： 若有 n 个鸽巢，kn+ 1只鸽子，则存在一个至少有 k+1只鸽子的鸽巢。
排列组合
-
基本计数原理：乘法原理和加法原理
-
排列组合：
1.排列数:从n元素集合S中取出r个元素有序地排成一列，称为S的一个r排列。这样的排列共有P(r n)=n(n-1)(n-2)···(n−r+1)!=n!/(n-r)!个。注：全排列共有n!个。
2.组合数：从n元素集合S中取出一个含有r个元素的集合，称为S的一个r组合（子集）。这样的组合（子集）共有（n r)=n!/(r!(n-r)!)个。若 r<0或r>n，则(n r)=0
3.组合数的性质:
1.(n i)=(n n-i):取i个等同于不取n-i个 2.(n i)=(n-1 i)+(n-1 i-1):按照取不取第 n 个分情况讨论 3.(n 0)+(n 1)+···+(n n)=2^n:n元集合的全部子集数为2^n。 -
定理:
1.二项式定理:设n为非负整数，则(x+y)^n=(n 0)x^0×y^n+(n 1)x^1×y^(n-1)+···+(n n)x^n×y^0.
2.其他:从 n 元集中选取奇数个元素 和偶数个元素的方案数相等
3.Lucas定理:对于非负整数 n, i 和 p，(n i)≡(n/p i/p)(n%p i%p) (mod p)
容斥原理
设全集为U，则|A^c|=|U|-|A|。
|A∪B|=|A|+|B|−|A∩B|。
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A ∩B∩C|。
特殊的数列
-
1.Catalan 数
第n个Catalan 数Cn是满足如下要求的数列的个数：
长度为2n的数列a1,a2,...,a2n，其每一项ai的取值都是 ±1，且对于任意i,a1+a2+···+ai≥0。
如果在二维平面上画出前缀和的折线，不难发现是某例题的特殊情况，即 Cn=（2n n)−(2n n+1)=1/(n+1)(2n n)。
递推式1：Cn =∑(n,i=1)Ci−1×Cn−i，初值 C0 = 1。通过枚举前缀和恰好为0的位置得到。 递推式 2：Cn=(4n−2)/(n+1)Cn-1。 -
2.第二类Stirling 数
定义:第二类 Stirling 数{n k}表示：将n个元素的集合划分成k个非空子集的方案数。
递推：第n个元素要么单独占据一个集合，要么在前n−1个元素已经构成的k个非空子集中任选一个加入。
{n k}={n-1 k-1}+k{n-1 k}.性质:
定义下降幂 x^_i:= x(x − 1)(x − 2)· · ·(x − i + 1) ∑(n,i=0){n i}x^_i=x^n -
3.第一类Stirling 数
定义:第一类 Stirling 数[n k]表示：将n个两两不同的元素，划分为k个互不区分的非空轮换的方案数。
递推：第n个元素要么单独占据一个轮换，要么可以插入之前任意一个元素之前。
[n k]=[n-1 k-1]+(n-1)[n-1 k]. 定义上升幂x^i_:=x(x+1)(x+2)···(x+i−1)， 有∑(n,i=0)[n i]x^i=x^n_ -
4.Stirling 反演
对任意取值的{p i},{q i},
qn=∑(n,i=0){n i}pi <=> pn=∑(n,i=0) (-1)^(n-i)[n i]qi.
即矩阵 Fi,j={i j} 和 Gi,j=(−1)^(i-j)[i j] 互为逆矩阵。交换两Stirling 数 也成立