欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    《组合学初步》PPT课件.ppt

    • 资源ID:5567163       资源大小:315.99KB        全文页数:23页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    《组合学初步》PPT课件.ppt

    1,第 2 节 组合学初步,广义的组合数学就是离散数学,离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之,组合数学是一门研究离散对象的科学。狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。,2,第 2 节 组合学初步,主要内容:,基本计数法则容斥原理抽屉原理,3,1 基本计数法则,如果具有性质A的事件有m个,性质B的事件有n个,则具有性质A或B的事件有m+n个。,加法法则:,设A,B为两个不相交的有限集,则 AB=A+B。,集合描述:,(A和B是性质无关的两个事件),4,基本计数法则,通俗的语言描述:,如果有p种方法能够从一堆物品中选择一个物品,而有q种方法也能够从另一堆物品中选择一个物品,那么从这两堆物品中选择一个物品的方法共有p+q种。,5,基本计数法则,若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A及B的事件有mn个。,乘法法则:,设A,B为有限集,则AB=AB。,集合描述:,6,基本计数法则,通俗的语言描述:,一项任务有p个结果,而不论第一项任务的结果如何,第二项任务都有q个结果,那么,这两项任务连续执行就有pq个结果。,一项任务要经过两个步骤,如果第一个步骤有p个结果,而不论第一步的结果如何,第二个步骤都有q个结果,那么,这项任务就有pq个结果。,或者,7,基本计数法则,例1:求小于10000的正整数中含有数字1的数的个数?,例3:确定数3452 117138的正整数因子的个数?,例2:两位数字有多少两个位互异且非零的两位数?,(答案:3439),(答案:72),(答案:1080),8,问题:设A,B,C,D为有限集,则 AB=?ABC=?ABBC=?,2 容斥原理,9,定理1 容斥原理(或逐步淘汰原理)形式之一设A1,A2,.,An为n个有限集,则,容斥原理,10,例1:在1000名大学毕业生的调查中,有804人掌握了英语,205人掌握了日语,190人撑握了俄语,125人既掌握了英语又掌握了日语,57人既掌握了日语又掌握俄语,85人既掌握英语又掌握俄语。试求这1000名大学生中,英语、日语、俄语全掌握的有多少?,容斥原理,11,ABC=A+B+C-AB-AC-BC+ABC,1000=804+205+190-125-85-57+ABC,ABC=68,英语、日语、俄语全掌握的有68人。,则A=804,B=205,C=190,,AB=125,AC=85,BC=57,容斥原理,解:,设A为掌握了英语的人数,B为掌握了日语的人数,C为掌握了俄语的人数。,12,定理2 容斥原理(或逐步淘汰原理)形式之二设A1,A2,.,An都是有限集S的子集,则,容斥原理,13,例2:1,2,3,4,5,6六个数的全排列中不出现135和46的排列有多少个?,容斥原理,例3:一个人写了十封集和十个信封,然后随机地将信装入信封,试求每封信都装错了的概率。,14,容斥原理解决的问题:,广义容斥原理解决的问题:,容斥原理,15,抽屉原理:简单形式 如果n+1个物体被放进n个盒子中,那么至少有一个盒子包含两只或更多的物体。其它表述形式:如果n+1只鸽子被放进n个鸽巢中,那么至少有一个鸽巢包含两只或更多的鸽子。如果n+1个物体用n种颜色涂色,那么必然有两个物体被涂成相同的颜色。,3 抽屉原理,16,4个物体,3个盒子,存放,1,2,3,4,5,抽屉原理,17,例1:在13个人中存在两个人,他们的生日在同一个月 份里。,抽屉原理,考虑12个盒子,每个盒子对应一个月份,将13个人放到12个盒子中,则至少有一个盒子包含两个或两个以上的人,即,这在13个人中存在两个人,他们的生日在同一个月份里。,18,应至少选择n+1个人。考虑n个盒子,每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去,那么就有同一个盒子含有两个人,也就是说,我们选择了一对已婚夫妇。如果选择n个人,可以只选择所有丈夫或只选择所有的妻子。,抽屉原理,例2:设有n对已婚夫妇。为保证能够有一对夫妇被选出,至少要从这2n个人中选出多少人?,19,例3:给定m个整数a1,a2,am,存在整数k和l,0klm,使得ak+1+ak+2+al能够被m整除。,抽屉原理,例4:一位国际象棋大师有11周的时间备战一场锦标赛,他决定每天至少下一盘棋,但是为了使自己不过分疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天,期间这位大师恰好下了21盘棋。,例5:从整数1,2,3,200中我们选择101个整数。证明,在所选择的这些整数之间存在两个这样的整数,其中一个可以被另一个整除。整数分解知识:任何一个整数都可以写成2ka的形式,其中,k0,a为奇数。,20,抽屉原理:加强形式令q1,q2,qn为n个正整数。如果将q1+q2+qn-n+1个物体放入n个盒子内,那么,或者第一个盒子至少含有q1个物体,或者第二个盒子至少含有q2个物体,或者第n个盒子至少含有qn个物体。,抽屉原理,抽屉原理的简单形式是其加强形式通过q1=q2=qn=2来实现的。这时,q1+q2+qn-n+1=2n-n+1=n+1。,21,证明:采用反证法,设将q1+q2+qn-n+1个物体放入到n个盒子中,如果对于每个i=1,2,n,第i个盒子含有少于qi个物体,那么所有盒子中的物体总数不超过(q1-1)+(q2-1)+(qn-1)=q1+q2+qn-n这与物体的总数为q1+q2+qn-n+1相矛盾,所以或者第一个盒子至少含有q1个物体,或者第二个盒子至少含有q2个物体,或者第n个盒子至少含有qn个物体。,抽屉原理,22,推论1.m个物体,n个盒子,则至少有一个盒子里有不少于(m-1)/n+1个物体。证明:采用反证法,设所有盒子了最多有(m-1)/n个物体,则n个盒子中的物体数最多为n(m-1)/n m-1,与假设矛盾。推论2:若取n(m-1)+1个物体放入n个盒子中,则至少有1个盒子有m个物体。这个推论相当于q1=q2=qn=m时的特殊情况。,抽屉原理,23,则m1,m2,mn中至少有1个数不小于r。,推论3:若m1,m2,mn是n个正整数,而且,抽屉原理,例6:证明每个由n2+1个实数构成的序列a1,a2,an2+1或者含有长度为n+1的递增子序列,或者含有长度为n+1的递减子序列。,

    注意事项

    本文(《组合学初步》PPT课件.ppt)为本站会员(小飞机)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开