3计数(1).ppt
《3计数(1).ppt》由会员分享,可在线阅读,更多相关《3计数(1).ppt(68页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 H LP-DM离散数学第3章 计数 H LP-DM本章内容本章内容1.基本原理2.鸽巢原理3.排列组合4.二项式系数和组合恒等式5.广义排列组合6.产生排列组合的算法 H LP-DM3.1计数基础计数基础v2种开胃食品种开胃食品v3道主菜道主菜v4种饮料种饮料由一道主菜和一种饮料可以组成多少种不同的正由一道主菜和一种饮料可以组成多少种不同的正餐?餐?由一开胃食品、一道主菜和一种饮料可以组成多由一开胃食品、一道主菜和一种饮料可以组成多少种不同的正餐?少种不同的正餐?H LP-DMv将所有可能的包含一种主食和一种饮料的午餐选择列出:HT,HM,HC,HR,CT,CM,CC,CR,FT,FM,FC
2、,FR 不难发现有12 种不同的选择。v包含一种开胃食品、一种主食和一种饮料的午餐,其可能的组合共有24 种:NHT,NHM,NHC,NHR,NCT,NCM,NCC,NCR,NFT,NFM,NFC,NFR,SHT,SHM,SHC,SHR,SCT,SCM,SCC,SCR,SFT,SFM,SFC,SFR H LP-DM乘法原理乘法原理乘积法则:乘积法则:假定一个过程可以被分解成两个任务,完成第一个任务有n1种方式,在第一个任务完成之后有n2种方式完成第二个任务,那么完成这个过程有n1n2种方式。如果一种活动由连续t步组成,第一步有n1种方法,第二步有n2种方法,.第t步有nt种方法,那么不同的活动
3、数目有 n1*n2*.*nt 当一活动由连续几步组成时,把每一步的方法数乘起来当一活动由连续几步组成时,把每一步的方法数乘起来.H LP-DM例题讲解例题讲解v例1 用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少?v解解:给一个座位编号的过程分两个任务:从26个字母中选取一个字母;从100个正整数中选取一个整数。根据乘法原理,座位的编号方式可以有:26*100=2600种v例2 有多少个不同的7位二进制串?v解:7位二进制串的每一位都可以有两种选择,因此有27 H LP-DMv计数函数 从一个n元集到一个m元集存在多少个函数?v解:一个函数对于定义域中的m个
4、元素中的每个元素都从值域中n个元素中的一个元素对应。因此,由乘法原理nm H LP-DM例例 Melissa病毒病毒 v1990 年,一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统,通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时,宏从用户的地址本中找到前50 个地址,并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后,病毒会自动继续转发,不断往复扩散。v当第一个病毒转发给50 个地址后,每一个接收到病毒的地址又将病毒转发给50 个地址。根据乘法原理,第二次增加了50 50=2500 个接收者;每个接收者又将转发给50 个地址,再根据乘法
5、原理,增加了50 50 50=125 000 个接收者;再经过一次转发,又增加了50 50 50 50=6 250 000 个接收者。则经过4 次转发,共发送了6 250 000+125 000+2500+50+1=6 377 551个附件。H LP-DM例例v如果不允许重复,用ABCDE可以组成多少种长度为4的字符串?v5*4*3*2=120 H LP-DM例例v如果不允许重复,用ABCDE可以组成多少长度为4的字符串?其中有多少是以B开头的?v 1*4*3*2=24 H LP-DM例例v如果不允许重复,用ABCDE可以组成多少长度为4的字符串?其中有多少不是以B开头的?v4*4*3*2=9
6、6v120-24 H LP-DM例例 x1,x2,.,xn的子集的数目一个子集可以由n步构成:选或不选x1,选或不选x2,.,选或不选xn共有2*2*.*2种可能性=子集数 n H LP-DM例例vX是一个含n个元素的集合,满足vA BX的有序对(A,B)有多少个?A BX-BB-AX H LP-DMAnswer集合X中的每个元素x所属有三种可能:在A中(且在B中)在B中(但不在A中,在B-A中)不在B中(不在A中,在X-B中)有序对(A,B)的个数等于将集合X中的元素指定到A、B-A、X-B这三个集合的不同指派数。3*3 .*3 种可能性 n H LP-DM例例v用101或111打头的8位串
7、有多少?v101打头的8位串有 25=32v111打头的8位串有 25 =32用用101或或111打头的打头的8位串有位串有 32+32 H LP-DM加法原理加法原理 假设X1,.,Xt是集合且第i个集合有 ni个元素,如果X1,.,Xt两两不相交,则可以从X1或X2或.Xt选择元素的可能性有n1 +.+nt v当被计数的元素可以被分解到不相交的子集时,可将每个子集的元素数相加得到总的元素数.H LP-DMWhen and Which多练习+对每个问题认真思考 H LP-DM3.1.3 比较复杂的计数问题比较复杂的计数问题v综合应用加法原理与乘法原理v例:5本不同的计算机书3本不同的数学书2
8、本不同的美术书选择2本不同类的书有多少方法?5*3+5*2+3*2 H LP-DMv例:计算机系统的每个用户有一个68个字符构成的密码,其中每个字符是一个大写字母或者数字,且每个密码必须至少包含一个数字。有多少可能的密码?v解:设P是可能的密码总数,用p6,p7,p8分别表示6、7、8位的可能的密码数。则P=p6+p7+p8.vP6=366-266vP7=367-267vP8=368-268 H LP-DM例例由A、B、C、D、E、F 6人委员会要选一个主席,一个秘书,一个书记1.有多少种选法?2.如果A或B必须是主席,有多少种?3.如果E必须任3职之一,有多少种?4.如果D和F必须任职,有多
9、少种?H LP-DMAnswer1.6*5*42.5*4+5*43.3*(5*4)4.3*2*4 H LP-DM3.1.4 容斥原理容斥原理v容斥原理:v|A1A2|=|A1|+|A2|-|A1A2|v例:以1开始或者以00结束的8位二进制符号串有多少?v解:以1开始的8位二进制数的个数:27v以00结束的8位二进制数的个数:26v重复计算的数字:以1开始并且以00结束 25v故:27+26+25 H LP-DMv某计算机公司收到了350份计算机毕业生设计一组新网络游戏服务器工作的申请书。假如这些申请人中有220人主修的是计算机专业,又147人主修的是商务专业,有51人是既主修计算机专业又主修
10、商务专业。那么,有多少申请人既没有主修计算机,又没有主修商务专业?v解:用A1表示主修计算机专业的人数;A2表示主修商务专业的人数v则|A1A2|=|A1|+|A2|-|A1A2|=220+147-51=367-51=316v故:350-314=34 H LP-DM3.1.5 树图树图v所有不含连续两个1的4位二进制串ABCD1 11 11 10 00 00 0 H LP-DM3.2鸽巢原理鸽巢原理 H LP-DM3.2.1 鸽巢原理鸽巢原理v定理定理1:如果:如果k+1个或更多的物体放入个或更多的物体放入k个盒子,个盒子,那么至少有一个盒子包含了那么至少有一个盒子包含了2个或更多的物体个或更
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计数
限制150内