离散数学考前复习：（三）计数
3.1排列与组合
加法法则：第一项任务为n1种方式，第二项任务为n2种方式，两项任务不能同时完成，则为（n1+n2）种方式乘法法则：一个过程可以分为独立的两个相互独立的任务，第一个任务有n1种完成方式，第二个任务有n2种完成方式，那么完成这个任务有n1*n2种方式排列：在有n个元素的集合A中任取r（0<r<n）个元素，按顺序排成一列，称为从A中取r的一个排列 具有n个不同元素的集合r-排列数是：组合：从n个元素中取出r个而不考虑它们的顺序时，称为从n中取r个的组合 n元素集合的r的组合数是： 圆周排列：从n个不同元素中不重复地取出m（1≤m≤n）个元素在一个圆周上，叫做这n个不同元素的圆排列。（n!/[m*(n-m)!]）有重复的排列： 具有n个物体的集合允许重复的r排列数为n^r 类型1相同的物体有n1个，类型2的相同的物体有n2个，…，类型k的相同的物体有nk个，那么n=n1+n2+…+nk个物体的不同排列数是：n! / n1! n2! … nk! 从n个元素的集合中允许重复的r组合有Cr （n+r-1）个
3.2 生成排列和组合
字典序排列按字典序生成下一个r-的组合
3.3 生成函数
定义：对于任意数列a0,a1,a2…an 即用如下方法与一个函数联系起来:G(x)=a0+a1x+a2x^2 +…+ ak*x^k常用的生成函数表 图被我吃了2333用生成函数解决递推关系
3.4 鸽巢原理
把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件把多于m*n+1(n不为0)个的物体放到n个抽屉里，则至少有一个抽屉里有不少于(m+1)的物体。
3.5 容斥原理
如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。（A∪B = A+B - A∩B)如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）
（感觉这一块更多还是要根据实际来理解诶。看看后面的内容，嗷嗷啊还有好多……༼༎ຶᴗ༎ຶ༽菜鸡萌妹在线自闭）
