离散数学第七章计数.ppt

第七章计数 7 1基本计数原理 1 加法原理2 乘法原理 加法原理 加法原理又称为和计数原理 也称和规则 存在三种表述形式 其本质是说 整体等于其部分之和 若集合X是不相交非空子集S1 S2 Sm的并 则 X 若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是非空集合 则笛卡尔积S1 S2 Sm的元素个数是 若事件E1 E2 Em发生分别有e1 e2 em种方式 并且诸事件是独立的 则事件E1或E2或 或Em依次发生有e1 e2 em种方式 乘法原理 如果选取事物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 DCA类的网络标识有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 mn 1 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 一般情形 设S为全集 又因为则有 2个集合的情形 S A B A B 3个集合的情形 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 17由 S 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圆排列总数记为K n r 或 由于在圆排列中重要的是元素彼此间相对位置 因此一个圆排列经过旋转后得到的仍是同一个圆排列 而线排列则不然了 只要有一个元素的位置发生变化便得到不同的排列 考虑到对每一个固定的n个元素取r个的圆排列均恰有r种不同方式展成r个不同线排列 不同的圆排列展成的线排列彼此也必不同 全部圆排列展出的恰好就是全部线排列 因此线排列数是圆排列数的r倍 于是K n r P n r r特别当r n时 K n n P n n n n 1 例7 4 26颗颜色不同的钻石 可穿成几种钻石圈 圆排列 就是在P 6 6 的基础上 本来在这里面ABCDEFG和BCDEFGA是不同的 但是 圆排列 这里因为形成了一个圆圈 所以 ABCDEFG和BCDEFGA是相同的 同样 CDEFGAB 等和他们也是相同的 可见 一个相同的圆排列在原有的P 6 6 中是被重复计算了6次 于是圆排列的结果是 P 6 6 6 1 2 3 4 5 120又因为钻石圈是可以翻转的 也就是在这里 ABCDEF 和 FEDCBA 是一样的 想象一下手镯 你平放着 你再翻转一下 还是原来的手镯 但是你同样是顺时针编号 得出的号码是正好调转的 于是在圆排列的基础上你要除以2 得到P 6 6 6 2 60种 例7 4 36个人坐成一个圆形 可以有多少种坐法 你只要考虑 圆排列 了 因为你不能把人底朝天的翻转 于是答案是P 6 6 6 120种 下面我们主要讲解重集的排列与组合所谓重集是指其元素可以多次出现的集合 某元素ai出现的次数ni ni 1 2 称为该元素的重复数或重复度 如重集S中有k个元素a1 a2 ak 其重复数分别为n1 n2 nk 则S n1 a1 n2 an nk ak 重集的排列定义 从重集S n1 a1 n2 an nk ak 中有序选择r个元素称为S的一个r排列 当r n1 n2 nk时也称S的全排列或S的排列 定理7 4 5设重集S a1 a2 ak 则S的r排列数是kr 推论设重集S n1 a1 n2 a2 nk ak 且ni r 1 i k 则S的r排列数是kr 下面我们来看重集的全排列 先看下面这个例子 例 1个m 4个i 5个s 2个p全部使用 共能组成多少个单词 解 有12个空格 把1 4 5 2 12个字母全部放进这12个格子中即算完成这件事 先从12个格子中选1个放m 再从剩下的12 1 11个格子中选4个放i 再从剩下的12 1 4 7个格子中选5个格式放s 再从最后12 1 4 5 2个格子中选2个放p 由乘法原理知 共有种方法 定理7 4 6设重集S n1 a1 n2 an nk ak 且n1 n2 nk n 则S的全排列数是 重集的组合定义 设重集S n1 a1 n2 an nk ak S中r个元素的子重集称为S的r组合 由定义知 若S有n个元素 即n1 n2 nk n 则S的n组合只有一个 即S自身 若S含有k个不同元素 则存在k个S的1组合 例如 S 3 a 1 b 2 c 则 a a a b a c b c c c 都是S的2组合 定理7 4 7设重集S a1 a2 ak 则S的r组合数是C k r 1 r 证 S的每个r组合可以用k 1条竖线和r颗星的形式来表示 其中k 1条竖线表示k个不同的单元 当集合的第i个元素出现在组合中 第i个单元就包含一颗星 如 4元素集合的一个6组合用3条竖线和6颗星来表示 例如 表示包含2个第一元素a1 1个第二元素a2 0个第三元素a3和3个第四元素a4的组合 所以包含k 1条竖线和r颗星的每一个不同的情况就对应于k元素集合的允许重复的一个r组合 所有这些情况的个数是C k r 1 r 因为每种情况对应于从包含r颗星和k 1条竖线共k 1 r个位置中取r个位置来放r颗星的一个选择 推论1设重集S n1 a1 n2 a2 nk ak 且ni r 1 i k 则S的r组合数是C k r 1 r 推论2设重集S a1 a2 ak 且r k 则S中每个元素至少选择一个的r组合数是C r 1 k 1 例7 4 6面包店供应8种面点 如果一盒装12个面点 并且面包店有大量 每种至少12个 各种面点 问能供应多少不同面点盒 解设8种面点分别记为a1 a2 a8 所求不同面点盒个数是重集 a1 a2 a8 或 12 a1 12 a2 12 a8 的12组合数 即C 8 12 1 12 C 19 12 C 19 7 7 5递推关系 定义7 5 1将数列H 0 H 1 H n 中任一项H n 与其前某些项H i 用相等 小于等于或大于等于联结起来的式子 称为递推关系 其中n0 i n 这里n0是一个非负整数 称H 0 H 1 H n0 为初始条件 由初始条件和递推关系而导出通项的显示表达式 称为递推公式 也称递推公式是递推关系的解 例7 5 1汉诺塔游戏 它是由安装在三根固定的柱子上和不同尺寸的n个圆盘组成 开始时 这些圆盘按大小的次序放在第一根柱子上 使大圆盘在底下 游戏的规则是 每次把1个圆盘从一根柱子移到另一根柱子 但不允许这个圆盘放在比它小的圆盘上面 游戏的目标是把所有圆盘按照大小的次序都放到第二根柱子上 并且将最大的圆盘放在底部 令Hn表示把n个圆盘从一根柱子移到另一根柱子所需要的移动次数 建立关于序列 Hn 的递推关系 这一步实际有Hn 1步 这只需1步 这一步又需要Hn 1步 故移动n个圆盘的总步数Hn Hn 1 1 Hn 1 2Hn 1 1 以 Hn 2Hn 1 1 且H1 1 为例 求通项 递推公式 的常用方法有 逐差求和 等差数列通项的求法 逐商求积 等比数列通项的求法 转化为等差或等比数列后利用等差或等比数列的通项公式求得归纳法迭代方法母函数法 生成函数法 定义 对于序列 an a1 a2 an 构造一函数G x 称函数G x 是序列 an 的生成函数 或母函数 或形式幂级数 例如 1 x n是序列 的生成函数 如若已知序列 an 则对应的生成函数G x 便可根据定义确定 反之 如若已求得序列的生成函数G x 则该序列也随之确定 使用母函数法 要用到高数中有关级数的知识 这里我们就不详细举例求解了 下面我们介绍一类特殊的递推关系 分而治之递推关系 例7 5 2分而治之递推关系 在算法分析中 会分析一个规模为n的问题分成a个子问题的处理过程 其中每子问题的规模是n b 此外 假设由于分解而需要额外运算为g n 若f n 为求解该问题所需要的运算次数 于是得到f n 满足的递推关系f n af n b g n 称上式为分而治之递推关系 定理7 5 1设f n 满足递推关系f n af n b c的增函数 其中b n a 1 b 1 c为正实数 则下面举一例说明定理7 5 1的应用 例如 分析二分检索算法 若n为偶数时 二分检索算法把对某个元素在长度为n的搜索序列中的搜索转化为对一元素在长度