锐客网

  1. 首页 > it技术 > >

离散数学考前复习（（三）计数）

离散数学考前复习：（三）计数 3.1排列与组合

  • 加法法则：第一项任务为n1种方式，第二项任务为n2种方式，两项任务不能同时完成，则为（n1+n2）种方式
  • 乘法法则：一个过程可以分为独立的两个相互独立的任务，第一个任务有n1种完成方式，第二个任务有n2种完成方式，那么完成这个任务有n1*n2种方式
  • 排列：在有n个元素的集合A中任取r（0 具有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）
【离散数学考前复习（（三）计数）】（感觉这一块更多还是要根据实际来理解诶。看看后面的内容，嗷嗷啊还有好多……???????菜鸡萌妹在线自闭）

    推荐阅读


    上一篇：Accurate|Accurate Structured-Text Spotting for Arithmetical Exercise Correction 论文翻译

    下一篇：g++升级到7.3版本