离散数学教程-王元元-第5章 计数.pptVIP

离散数学 第5章 计数 第5章 计数 5.1.1 加法原理和乘法原理 加法原理： 若对象或事件的有限集合S=S1∪S2 ∪… ∪Sn 且S1,…,Sn两两不 相交，那么|S|=|S1|+|S2| +… + |Sn| 5.1.1 加法原理和乘法原理 乘法原理： 若对象或事件的有限集合S是依次取自有限集合S1, S2,…,Sn 中事件的序列的集合，那么|S|=|S1|?|S2| ?… ?|Sn| 5.1.1 加法原理和乘法原理 例5.1 (1) 从上海直达天津可以乘坐汽车、火车和飞机旅行。已知每天 汽车有3个班次，火车有8个班次，飞机有4个班次，问每天 从上海直达到天津有多少种不同的旅行方式？ (2) 从上海直达天津可以乘坐汽车、火车和飞机旅行，已知汽车 有3个班次，火车有8个班次，飞机有4个班次。从天津直达 大连可以乘坐轮船和飞机旅行，已知轮船有2个班次，飞机 有3个班次。问从上海经天津到大连有多少种旅行方式？ 解 (1) 3 + 8 + 4 = 15种 (加法原理)。 (2) 15·(2 + 3)= 75种 (加法原理和乘法原理) 5.1.1 加法原理和乘法原理 例5.2 一种彩票设计的获奖规则是：当你选择的六个数字与随机产 生的六个数字相同，并且顺序一致，获特等奖；当你选择的 六个数字中恰有5个与随机产生的六个数字中的5个相同，并 且顺序一致，获一等奖。问：你获得特等奖、一等奖的概率 分别是多大，获奖的概率有多大 ？ 解 选取六个数字的方式： 106种（乘法原理） 特等奖概率： 5.1.2 包含排斥原理 定理5.1 考虑集合S1，S2，S= S1∪S2 ，那么 |S|=|S1|+|S2|?|S1∩S2 | 证 由于是元素个数与元素个数之和，其中的公共元素被两次计数， 所以 |S|=|S1|+|S2|?|S1∩S2 | 。 5.1.2 包含排斥原理 定理5.2 考虑集合 S1, …, Sn，S= S1∪… ∪Sn ，那么 |S| = | S1∪… ∪Sn | 5.1.2 包含排斥原理 5.1.2 包含排斥原理 5.1.2 包含排斥原理 定理5.3 考虑集合 ， ，令 为 或 ,那么 定理5.4 考虑集合 ，已知 现将 记为 或 ，那么 5.1.2 包含排斥原理 例5.3 (1) 试计算在集合{1，2，3，…，1000}中有多少元素至少能被 5，6，8这三个数中的一个整除。 (2) 试计算在集合{1，2，3，…，1000}中有多少元素不能被5， 6，8这三个数中的任何一个整除。 5.1.2 包含排斥原理 5.1.2 包含排斥原理 解 S：密钥各位位置的集合，A、B：被4或6整除的各位位置的集合。 一次未改动的密钥位集合可表示为Aˉ∩Bˉ ； 改动两次，最终与原奇偶性相同的密钥位集合可表示为A∩B 。 5.2.1 排列的计数 定义5.1 用 或 表示“从n个元素的集合中每次取出r个元素 进行有序排列时可得到的排列的总数”。 或 简称为 r- 排列数， 简称为n- 全排列数。 定理5.5 对任意正整数n , r , r≤n , 从n个元素的集合中每次取出r个 元素进行有序排列时可得到的排列的总数是： （约定 ） 特别地， ， 5.2.1 排列的计数 例5.5 问有多少个大于6400，又同时满足各位数字都不相同，且数中 不出现数字2与7。 解 满足条件的数只能是四、五、六、七和八位数。 五、六、七和八位数的数目可以如下分别计算： 而五、六、七和八位数的数的总