P13练习题9解析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《P13练习题9解析课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- P13 练习题 解析 课件
- 资源描述:
-
1、1 P13练习题练习题9 一间屋子内有一间屋子内有10个人,他们中没有人年龄超个人,他们中没有人年龄超过过60岁,但又至少不低于岁,但又至少不低于1岁。证明,总能找到岁。证明,总能找到两组人(两组不含相同的人),各组人的年龄两组人(两组不含相同的人),各组人的年龄和是相同。题中的数和是相同。题中的数10能换成更小的吗?能换成更小的吗?解:从解:从10个人中任意选个人中任意选0到到10人为一组,则共有:人为一组,则共有:1021010.2101100102种选择方法,由于必须分成两组,去掉其中的:种选择方法,由于必须分成两组,去掉其中的:共有:共有:1022种,又因为每个人种,又因为每个人的年龄
2、可以是的年龄可以是1到到60中的任意一个,中的任意一个,年龄和年龄和可可能的分布共:能的分布共:6010=600种,因此,相当于种,因此,相当于1022个物体放在个物体放在600个盒子,由个盒子,由鸽巢原理,至鸽巢原理,至少有两组分配在同一盒子中,在同一个盒子中少有两组分配在同一盒子中,在同一个盒子中的两组的年龄和必然相等;的两组的年龄和必然相等;若将人数降为若将人数降为9人,共有人,共有29-2=510种,分配种,分配给给609=540个盒子,不能得到题意的要求。个盒子,不能得到题意的要求。210100103第三章第三章 排列与组合排列与组合 3.2 集合的排列集合的排列定义定义:设设n元集
3、元集S=a1,a2,an,从,从S中取出中取出r个不个不同元素按次序排列,称为同元素按次序排列,称为S的一个的一个r-排列排列,其个,其个数称为数称为r-排列数排列数,记作,记作P(n,r)或或 。当。当n=r时,时,S的的r-排列又称排列又称S的的全排列全排列,其个数,其个数P(n,n)又称又称全全排列数排列数。r-排列就是将排列就是将r个元素有序摆放。个元素有序摆放。rnp4例:如果集合例:如果集合 S=a,b,c,则,则S的的3个个1-排列是排列是 a,b,c P(3,1)=3 S的的6个个2-排列是排列是:ab,ac,ba,bc,ca,cb P(3,2)=6 S的的6个个3-排列是排列
4、是:abc,acb,bac,bca,cab,cba P(3,3)=6 S没有没有4-排列及其以上的排列排列及其以上的排列,因为因为S中最多中最多只有只有3个元素。个元素。排列的特征在于排出的排列的特征在于排出的字符串一定有顺序之分字符串一定有顺序之分。5 定理定理3.2.1 对于正整数对于正整数n和和r,若,若 r n,则,则 P(n,r)n(n1)(nr1)即即:我们定义我们定义n!(读作(读作n的的阶乘阶乘)为:)为:n!=n(n1)2 1 并约定并约定0!=1)!(!),(rnnrnp)1()(110knknrkrk6 例例1字母字母ABCDEFABCDEF的排列中有多少个包含子串的排列
5、中有多少个包含子串 DEF?DEF?解:为了保证解:为了保证DEFDEF出现在子串中,这三个字母必须出现在子串中,这三个字母必须连在一起且保持这个顺序连在一起且保持这个顺序,可以将可以将DEF DEF 看成一个字看成一个字符。剩余的字母符。剩余的字母A,BA,B和和C C可以放置在任意的位置。可以放置在任意的位置。可以把构造包含子串可以把构造包含子串DEFDEF的的ABCDEFABCDEF的排列看作四个的排列看作四个标号标号DEF,A,B,CDEF,A,B,C的排列的排列.由全排列定义,由全排列定义,7四个对象有四个对象有4 4!个排列。于是包含子串!个排列。于是包含子串DEFDEF的的ABC
6、DEFABCDEF的排列数为的排列数为4 4!=24=24。DEF A B C例例2:ABCDEF的包含字母的包含字母DEF不间隔不间隔任意顺序任意顺序 的排列有多少个?的排列有多少个?8 我们可以通过两步来解决这个问题:选择字我们可以通过两步来解决这个问题:选择字母母DEF为一个子字符串,构造为一个子字符串,构造DEF的一个任意的一个任意顺序的排列。由全排列定义,第一步有顺序的排列。由全排列定义,第一步有3!=6种方法,根据例种方法,根据例1,第二步可以有,第二步可以有24种方法。根种方法。根据乘法原理,据乘法原理,ABCDEF的包含字母的包含字母DEF的任意的任意顺序的排列数为:顺序的排列
7、数为:624=1449 例例3:七个男人和五个女人坐一排开会,如果不七个男人和五个女人坐一排开会,如果不允许两个女人坐在一起允许两个女人坐在一起(可能是因为她们开会喜可能是因为她们开会喜欢说话欢说话),有多少种方法?,有多少种方法?解解:我们可以用两步将男人和女人排列起来:先我们可以用两步将男人和女人排列起来:先排列男人,再排列女人。男人有排列男人,再排列女人。男人有7!=5040种排法,种排法,一旦我们已经排好男人,因为不能有两个女人站一旦我们已经排好男人,因为不能有两个女人站在一起,女人有八个可能的位置可以站:在一起,女人有八个可能的位置可以站:10 _M1_M2_M3_M4_M5_M6_
8、M7_ (这样就保证了女人不相邻)(这样就保证了女人不相邻)因此女人有因此女人有P(8,5)=87654=6720种种排列方法。根据乘法原理,七个男人和五个女排列方法。根据乘法原理,七个男人和五个女人坐一排开会,如果不能有两个女人站在一起,人坐一排开会,如果不能有两个女人站在一起,共有:共有:50406270=33868800种方法。种方法。11例例4 有多少取自有多少取自1,2,9的各位互异的的各位互异的7位数位数 使得使得5和和6不以任何顺序不以任何顺序相继相继出现?出现?解法一解法一 1,2,9的的7-排列中满足要求的可被排列中满足要求的可被分成分成4类:类:1)5,6均不出现。均不出现
9、。即即1,2,3,4,7,8,9的的7-排序排序P(7,7)12 2)5出现出现6不出现。不出现。即即5有有7个位置,其余是个位置,其余是1,2,3,4,7,8,9的的6-排列排列 7P(7,6)3)5不出现不出现6出现。出现。即即5有有7个位置,其余是个位置,其余是1,2,3,4,7,8,9的的6-排列排列 7P(7,6)134)5与与6同时出现,但是同时出现,但是 a)第)第1位等于位等于5。此时此时6有有5个位置,其余是个位置,其余是1,2,3,4,7,8,9的的5-排列排列:5P(7,5)b)第)第7位等于位等于5。此时此时6有有5个位置,其余是个位置,其余是1,2,3,4,7,8,9
10、的的5-排列排列:5P(7,5)c)5出现在首尾之外的位置上。出现在首尾之外的位置上。14此时,此时,5有有5个位置可选。对于每种个位置可选。对于每种5的选择,的选择,6仅仅 有有4个位置可选。其余个位置可选。其余5位是位是1,2,3,4,7,8,9的的5-排列。于是排列。于是 54P(7,5)综上所述,结论为综上所述,结论为 P(7,7)7P(7,6)25P(7,5)2 54P(7,5)15120015解法二解法二 令令T是是1,2,.,9的所有的所有7-排序的集合。排序的集合。现对现对T构造划分构造划分S和和 ,其中其中S是满足要求的是满足要求的7位位数的集合数的集合,而,而 T=S T
11、=S +所以所以 S=T 而而 T P(9,7);26P(7,5)故故 S P(9,7)26P(7,5)151200 5,6作为相连子串有作为相连子串有:56或或65之分之分,共有共有6个位置放。个位置放。SSSSS16 以上我们讨论的是以上我们讨论的是线性排列线性排列。例如例如1,2,3,4,5,6 的两个的两个6-排列:排列:5 6 1 2 3 4 与与 2 3 4 5 6 1 是两个不同的排列。但是,如果我们把每是两个不同的排列。但是,如果我们把每个排列各自的首尾相接起来,所形成的两个个排列各自的首尾相接起来,所形成的两个“环环”就没有什么不同。此时,就没有什么不同。此时,1我们称它们属
12、于同我们称它们属于同 2 6一个一个循环排列循环排列。3 5他们是右图:他们是右图:417 上述循环排列可以从下列线性排列得到:上述循环排列可以从下列线性排列得到:123456 234561 345612 456123 561234 612345 其中的每一个通过将第一元素看成接在最后一其中的每一个通过将第一元素看成接在最后一个元素后面的元素产生。这样,要想求得循环个元素后面的元素产生。这样,要想求得循环排列的数目,我们只要用排列的数目,我们只要用6 6去除线性排列去除线性排列的数目的数目即可。故上述元素的循环排列数为:即可。故上述元素的循环排列数为:6!/6=5!=12018定理定理3.3.
13、2 n个元素的集合的循环个元素的集合的循环r-排列的个数是排列的个数是 特别地,特别地,n个元素的循环排列的个数是个元素的循环排列的个数是(n-1)!例例5:10个人要围坐一圆桌,其中有两人不愿意个人要围坐一圆桌,其中有两人不愿意彼此挨着座。共有多少种循环座位按排方法?彼此挨着座。共有多少种循环座位按排方法?解法一解法一 将这两个人挨着座,看成一个元素,共将这两个人挨着座,看成一个元素,共9个元素的循环排列有:个元素的循环排列有:9!/9=8!种;这两个种;这两个人挨着座又有左右之分,总共应该有人挨着座又有左右之分,总共应该有:28!种种;题意的安排为:题意的安排为:10!/10 28!=78
展开阅读全文