离散数学第七章 计数
更新时间:2023-08-15 15:30:01 阅读量: 人文社科 文档下载
- 离散数学第七章课后答案推荐度:
- 相关推荐
离散数学
第七章 计数
离散数学
7.1 基本计数原理1.加法原理 2.乘法原理
离散数学
加法原理加法原理又称为和计数原理,也称和规则,存在三种表 述形式,其本质是说,整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并,则 |X|= m
| Si 1
i
|
② 若E1,E2,…,Em是彼此互斥事件,并且E1发生有e1 种方式,E2发生有e2种方式,…,Em发生有em种方式, 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是,事件E1和E2互斥是说,E1和E2发生但两 者不能同时发生。
离散数学
③ 如果选择事物O1有n1种方法,选择事物O2 有n2种方法,…,选择事物Om有nm种方法, 并且选择诸事物方法不重叠,则选取O1或O2 或…或Om有n1+n2+…+nm种方法。
离散数学
加法原理
例7.1.1 一个学生想选修一门数学课或一门生 物学课,但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件,试问 该生有多少方式来选修课程?
离散数学
乘法原理
乘法原理又称有序计数原理,也称积规则,类 似加法原理,也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合,则笛卡尔 m 积S1 S2 … Sm的元素个数是 | Si | i 1 ② 若事件E1,E2,…,Em发生分别有e1, e2,…,em种方式,并且诸事件是独立的,则 事件E1或E2或·· m依次发生有e1 e2 … em ·或E 种方式。
离散数学
乘法原理
③ 如果选取事物O1,O2,…,Om分别有n1, n2,…,nm种方法,并且选取诸事物方法不重 叠,则事物O1与O2与…与Om依次选取有 n1 n2 … nm种方法。
离散数学
乘法原理
例7.1.2 一个学生要选修两门课,第一门课在 上午4小时内任选1小时,第二门课在下午3小 时内也可任选1小时,试问该生有多少种可能 的时间安排?
离散数学
乘法原理
例7.1.3 计数因特网地址。在由计算机的物理网络 互连而构成的因特网中,每台计算机的网络连接 被分配一个因特网地址。在网际协议版本IPV4中, 一个地址是32位的位串,它以网络标识netid开始, 后跟随主机标识hostid,该标识把一个计算机认定 为某个指定网络成员。
离散数学
乘法原理
根据网络标识和主机标识位数的不同目前使用3类地 址形式: 用于最大规模网络的A类地址,由0后跟7位网络标识 和24位的主机标识构成。 用于中等规模网络的B类地址,由位串10后跟14位的 网络标识和16位的主机标识构成。 用于最小规模网络的C类地址,由位串110后跟21位的 网络标识和8位的主机标识构成。 此外,又规定位串1111111在A类的网络标识中是无 效的,全0和全1组成的主机标识对任何网络都是无效 的。试计数因特网上的计算机有多少不同的有效IPV4 地址?
离散数学
乘法原理
令D是因特网上计算
机的有效地址数, DA,DB,DC分别表示A类B类和C类的有效地址, 根据加法原理D= DA+DB+DC A类的网络标识有27-1=127个( 1111111无 效),主机标识224-2=16777214(全0和全1 组成的主机标识无效),根据乘法原理, DA=127*16777214
离散数学
乘法原理
B类的网络标识有214个,主机标识216-2个, 根据乘法原理,DB= 214 * (216-2) C类的网络标识有221个,主机标识28-2个,根 据乘法原理,DB= 221 * (28-2) D= DA+DB+DC=3737091842
离散数学
7.2 鸽洞原理
若n+1只鸽子入住n个鸽洞,则至少有1个鸽洞 里至少有2只鸽子。 例7.2.1 在任意一群366人中,至少有2人生日 相同。 例7.2.2 抽屉里有3副手套,随意抽出4只手套, 则其中至少有一副手套。
离散数学
鸽洞原理
例7.2.3 一个学生用37天准备考试。根据以往 的经验他知道需要复习的时间不超过60个小时, 他打算每天至少复习1小时,证明不管他如何 安排学习时间表(假定每天学习时数为整数), 必存在相继的若干天,他恰好共学习13小时。
离散数学
鸽洞原理
设t1是第一天学习的时数,t2是前2天学习时 数,t3是前3天学习时数…… 因为每天至少学习1小时,所以t1≥1,数列 t1,t2,……,t37是严格单调递增的: t1<t2<……<t37 复习的时间不超过60个小时,所以t37≤60 数列t1+13,……t37+13也是严格递增的,并且 t37+13 ≤73
离散数学
鸽洞原理
因此74个数t1,t2,……,t37,t1+13,……t37+13 都位于1和73之间,根据鸽洞原理,它们之中 必有两个数相等 由于前37个数和后37个数都是彼此不相等的, 故存在两个数i和j,使得ti=tj+13 于是j+1,j+2,……,i这些天中,该生恰好学 习13小时
离散数学
鸽洞原理的推广设m1,m2,…,mn是正整数,并有m1+m2+…+mn-n+1只 鸽子住进n个鸽洞,则或者 第1个鸽洞至少有m1只鸽 子,或者第2个鸽洞至少有m2只鸽子,…,或者第n个 鸽洞至少有mn只鸽子。 证明:反证法。假设第一个鸽洞住进的鸽子数少于m1 只,第2个鸽洞住进鸽子数少于m2只……于是,鸽子 总数不超过(m1-1)+(m2-1)+……+(mn1)=m1+m2+……+mn-n 与m1+m2+…+mn-n+1只鸽子矛盾
离散数学
7.3 容斥原理有限集合中的容斥定理,在无限集合中不一定成立.
2个集合的情形:|A∪B| = |A| + |B| – |A∩B|
3个集合的情形:|A∪B∪C| = |A| + |B|+|C| – |A∩B| – |A∩C| – |B∩C|+ |A∩B∩C|一般情形:1 i n
| A1 A2 An |
| A | | A Ai 1 i j n i
j
|
1 i j k n
| A Ai
j
Ak |
( 1) n 1 | A1 A2 An |
离散数学
设S为全集,又因为 | A | | S | | A | 则有 | A1 A2 An | | S | | A1 A2 An | | S | | Ai | 1 i n 1 i j n
| A Ai
j
|
1 i j k n
| A Ai
j
Ak |
( 1) n | A1 A2 An |
2个集合的情形: | A B | = |S| – (|A| + |B|) + |A∩B| 3个集合的情形: | A B C | = |S| – (|A| + |B|+|C|) + (|A∩B| + |A∩C| + |B∩C|) – |A∩B∩C|
离散数学
例 一个班里有50个学生,在第一次考试中有26 人得5分,在第二次考试有21人得5分.如果两次 考试中都没得5分的有17人,那么两次考试都得5 分的有多少人? 解 设A,B分别表示在第一次和第二次考试中得5 分的学生的集合,那么有 |S|=50, |A|=26, |B|=21, | A B | =17 由 | A B | = |S| – (|A| + |B|) + |A∩B|,得 |A∩B| = | A B | – |S| + (|A| + |B|) = 17 – 50 + 26 + 21=14
有14人两次考试都得5分.
离散数学
7.4 排列与组合我们以前讨论的排列称为线排列更为确 切,因为它隐含着将所选择的r元素排成在一 直线上,若使线排列的首末元素相邻就得了 “圆排列”。 定义7.4.2 从n元集S中有序选择r个元素并 排成一个圆周称为S的一个r圆排列,不同的r r 圆排列总数记为K(n,r)或 K n 。
正在阅读:
离散数学第七章 计数08-15
Intel 5、6、7、8系列芯片组详尽资料汇总 - 图文10-06
悄悄地提醒作文600字07-03
菜篮子工程数学建模06-05
微软练习题 - 图文10-31
2017沪教版小学数学六年级下册全册练习题(42份)09-16
普惠性民办幼儿园认定自评表10-04
- 粮油储藏基础知识
- 论文范文(包括统一封面和内容的格式)
- 经典解题方法
- 综合部后勤办公用品管理办法+领用表
- 学生宿舍突发事件应急预案
- 16秋浙大《生理学及病理生理学》在线作业
- 四分比丘尼戒本(诵戒专用)
- 浙江财经大学高财题库第一章习题
- 九大员岗位职责(项目经理、技术负责人、施工员、安全员、质检员、资料员、材料员、造价员、机管员)
- 旅游财务管理习题(学生版)
- 德阳外国语高二秋期入学考试题
- 投资学 精要版 第九版 第11章 期权市场
- 控制性详细规划城市设计认识
- bl03海运提单3国际贸易答案
- 2010-2011学年湖北省武汉市武珞路中学七年级(上)期中数学试卷
- VB程序填空改错设计题库全
- 教师心理健康案例分析 - 年轻班主任的心理困惑
- 民间借贷司法解释溯及力是否适用?
- 三联书店推荐的100本好书
- 《化工原理》(第三版)复习思考题及解答
- 第七章
- 离散
- 计数
- 数学
- 北京邮电大学第六届“研究生学术论坛”参赛手册
- 历史中心与历史联系_对全球史观的冷思考
- iPad使用说明
- 实验三 IIR数字滤波器设计及软件实现
- 建莲产业品牌建设探析
- 电子科技大学大学物理II期末考试要求
- 国外职业教育与职业资格证书制度衔接
- 工程建设项目经理培训费用估算和控制
- 电信3G无线上网卡各种错误代码描述
- 趣味逻辑推理100题第81-90题及答案
- 钢结构工地进程预算表
- 椎动脉开口狭窄的血管内支架成形术治疗
- 地方政府公信力缺失的现状及原因分析
- 星火高频词汇
- 如何编制发改委立项用热镀焊管项目可行性研究报告(甲级-发改委-经信委-商务局-备案-核准)
- 5.印广法师专访系列之五:了义法与不了义法、法华道场宗旨
- 优秀大学生采访稿
- 图像灰度化的方法及编程实现
- 大学英语语法 unit 1 Sentence Structure
- 交通费、通讯费、招待费标准及相关管理规定