当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)11/30

资源类别:文库,文档格式:PPT,文档页数:46,文件大小:479KB,团购合买
点击下载完整版文档(PPT)

第十一章排列与组合 计数的基本原理是加法原理和乘法原理 容斥原理是加法原理的推广

第十一章 排列与组合 计数的基本原理是加法原理和乘法原理, 容斥原理是加法原理的推广

111基本计数原理 定理11(加法原理)设A和B是有限集合S 的两个互不相交的子集,且A∪B=S, 则|S|=|AH+|B| 证明:因为S=AUB,先求A中元素个数 为A|,再求S中其余元素个数。 因为A和B是有限集合S的两个互不相交 的子集, 所以S中的元素不在A中必在B中,且B 中元素不在A中 所以S中不在A中的元素有B个,即 SA+B

11.1 基本计数原理 • 定理11.1(加法原理)设A和B是有限集合S 的两个互不相交的子集,且A∪B=S, 则|S|=|A|+|B|。 • 证明:因为S=A∪B,先求A中元素个数 为|A|,再求S中其余元素个数。 • 因为A和B是有限集合S的两个互不相交 的子集, • 所以S中的元素不在A中必在B中,且B 中元素不在A中, • 所以S中不在A中的元素有|B|个,即 |S|=|A|+|B|

定理1,乘法原理):设集合A和B都是 有限集,A|=p,|B|=q,则:|A×B=pq 证明从略。 例:某学生从2门数学课和4门计算机 课中任意选修一门, 有2+4=6种选修方法。 若他要选修数学课和计算机课各一门, 则有2×4-8种选修方法

• 定理11.2(乘法原理):设集合A和B都是 有限集,|A|=p,|B|=q,则:|A×B|=pq • 证明从略。 • 例:某学生从 2 门数学课和 4 门计算机 课中任意选修一门, • 有2+4=6种选修方法。 • 若他要选修数学课和计算机课各一门, • 则有2×4=8种选修方法

112集合的排列 集合的排列 将讨论集合的排列,包括环排列问题 1排列 (1)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 如果要求每位数字都不相同,问有多少种选 法? (2)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 问有多少种选法? 这两个问题不同点在于前者不允许重复选取, 而后者则允许重复。 首先考虑不重复问题

11.2 集合的排列 • 一、集合的排列 • 将讨论集合的排列,包括环排列问题。 • 1.排列 • (1)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 如果要求每位数字都不相同,问有多少种选 法? • (2)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 问有多少种选法? • 这两个问题不同点在于前者不允许重复选取, 而后者则允许重复。 • 首先考虑不重复问题

定义111从n个元素的集合S中有序选取 的r个元素称为S的一个r排列,不同的 排列总数记为p(m,r)。若r=n,则称此排 列为全排列。当r>n,规定p(n,r)=0 定理11.3:对r≤n的正整数n,r,有 p(n,r)=n(n-1)(n-r+1) 令n!=n(n-1)21,且规定0!=1,则 p(n,r)=n!/(n-r)!

• 定义11.1:从n个元素的集合S中有序选取 的r个元素称为S的一个r-排列,不同的 排列总数记为p(n,r)。若r=n,则称此排 列为全排列。当r>n,规定p(n,r)=0。 • 定 理 1 1 . 3 : 对 rn 的正整数 n,r, 有 p(n,r)=n(n-1)…(n-r+1) • 令 n!=n(n-1)…2•1, 且 规 定 0 ! = 1 , 则 p(n,r)=n!/(n-r)!

例:某产品加工需要一、二 五共5道工序, 则安排这些加工工序共有p(5,5)=120种 方法 若工序一必须先加工,则有p(4,4)=24种 方法。 若工序三不能放在最后加工,此时的安 排加工工序的方法数可这样来求 由于工序三的加工安排有p(4,1)=4种, 而其余的工序安排共有p(4,4)=24种, 由乘法原理知共有4×24=96种方法

• 例:某产品加工需要一、二、三、四、 五共 5 道工序, • 则安排这些加工工序共有 p(5,5)=120种 方法。 • 若工序一必须先加工,则有p(4,4)=24种 方法。 • 若工序三不能放在最后加工,此时的安 排加工工序的方法数可这样来求: • 由于工序三的加工安排有p(4,1)=4种, • 而其余的工序安排共有p(4,4)=24种, • 由乘法原理知共有4×24=96种方法

例:在上例中,(1)若规定工序四必须紧跟在工序 三的后面,有多少种安排方法? ·(2)若规定工序二必须在工序五的前面,有多少种 安排方法? 解:(1)把工序三、四看成一个工序,这样就相当于 四道工序,因此有p(4,4)=24种方法。 (2)把工序二放在工序五的前面,有四种情况: 1)工序二、五在一起,相当于四道工序, 因此有24种; 2)工序二、五中间间隔一道工序,中间一道工序从一、 三、四中选,有p(3,1)=3种, 把工序二、五连同中间间隔一道工序看成一个工序, 这样就相当于三道工序, 因此有p(3,3)=6种方法, 由乘法原理得p(3,3)×p(3,1)=18种;

• 例:在上例中,(1)若规定工序四必须紧跟在工序 三的后面,有多少种安排方法? • (2)若规定工序二必须在工序五的前面,有多少种 安排方法? • 解:(1)把工序三、四看成一个工序,这样就相当于 四道工序,因此有p(4,4)=24种方法。 • (2)把工序二放在工序五的前面,有四种情况: • 1)工序二、五在一起,相当于四道工序, • 因此有 24 种; • 2)工序二、五中间间隔一道工序,中间一道工序从一、 三、四中选,有p(3,1)=3种, • 把工序二、五连同中间间隔一道工序看成一个工序, • 这样就相当于三道工序, • 因此有p(3,3)=6种方法, • 由乘法原理得p(3,3)×p(3,1)=18种;

3)工序二、五中间间隔两道工序, 中间两道工序从 、四中选,有p(3,2)种, 把工序二、五连同中间间隔两道工序看成一个 工序 这样就相当于两道工序,因此有p(2,2)种方法, 由乘法原理得p(2,2)Xp(3,2)=12种; 4)工序二、五中间间隔三道工序,则有 p(3,3)=6种。 由加法原理知,要使工序二在工序五的前面, 安排加工工序的方法共有24+18+12+6=60种

• 3)工序二、五中间间隔两道工序, • 中间两道工序从一、三、四中选,有p(3,2)种, • 把工序二、五连同中间间隔两道工序看成一个 工序, • 这样就相当于两道工序,因此有p(2,2)种方法, • 由乘法原理得p(2,2)×p(3,2)=12种; • 4 ) 工 序 二 、 五 中 间 间 隔 三 道 工 序 , 则 有 p(3,3)=6种。 • 由加法原理知,要使工序二在工序五的前面, 安排加工工序的方法共有24+18+12+6=60种

例:十进制数字中,没有重复的4位数 有多少个? 解:这是从10个数字0,1,2,3,4,5,6,78,9中取4个 的排列问题, 所以P(104)=5040。 又因为4位数首位不能为0,必须去掉这种情 况 而首位是0的4位十进制字符串个数就是考虑 另三位从1,2,3,4,5,6,7,8,9中选取的问题, 即为P(9,3)=504。 所以十进制数字中,没有重复的4位数有 5040-504=4536

• 例:十进制数字中,没有重复的4位数 有多少个? • 解:这是从10个数字0,1,2,3,4,5,6,7,8,9中取4个 的排列问题, • 所以P(10,4)=5040。 • 又因为4位数首位不能为0,必须去掉这种情 况。 • 而首位是0的4位十进制字符串个数就是考虑 另三位从1,2,3,4,5,6,7,8,9中选取的问题, • 即为P(9,3)=504。 • 所以十进制数字中,没有重复的4位数有 5040-504=4536

例:排列26个字母,使得在a和b之间正好有7 个字母,问有多少种排法? 解:(1)a首b尾,中间恰含7个字母的排列有 P(24,7) b首a尾,中间恰含7个字母的排列有P(24,7) 因此以a,b为端点的9个字母排列有2P(24,7) (2把上述9个字母看成整体,与剩下的17个字 母共18个进行全排列,有P(18,18)=18 因此由乘法原理得“排列26个字母,使得在a 和b之间正好有7个字母”的排法有2P(24,7)18!

• 例:排列26个字母,使得在a和b之间正好有7 个字母,问有多少种排法? • 解:(1)a首b尾,中间恰含7个字母的排列有 P(24,7); • b首a尾,中间恰含7个字母的排列有P(24,7)。 • 因此以a,b为端点的9个字母排列有2P(24,7)。 • (2)把上述9个字母看成整体,与剩下的17个字 母共18个进行全排列,有P(18,18)=18! • 因此由乘法原理得“排列26个字母,使得在a 和b之间正好有7个字母”的排法有2P(24,7)18!

点击下载完整版文档(PPT)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共46页,可试读16页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有