组合数学幻灯片12.ppt

  1. 1、本文档共19页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
组合数学幻灯片12

研究排列问题的主要目的是求出根据已知的条件所能作出的不同排列的种数。 分类 线排列 圆排列 重排列 线排列是把一些元素排成一条直线, A={ } r是正整数,从这n个不同的元素中取r个按照一定的次序排列起来(r≤n),称为集合A的r-排列。 集合A的所有r-排列的个数记为P(n,r)。(定义1-1) 注意:A的r-排列为A的r有序子集。 例:集合A={a,b,c} 集合A有6个2-排列:ab,ac,ba,ca,bc,cb 即P(3,2)=6 A有6个3-排列:abc,acb,bac,bca,cab,cba, 即P(3,3)=6 线排列 线排列 定理1.1 对于正整数n, r, r≤n,有 P(n,r)=n(n-1)…(n-r+1)= n! ÷(n-r)! (1.3) 证明:集合第一项,有a1,a2,…,an n种选法 第二项,有除第一项外的n-1种选法. 第r项,有n-r+1种选法 由乘法规则,这r个项可以有n·(n-1)…(n-r+1)种选法。 所以 P(n,r)=n·(n-1)…(n-r+1)= n!÷ (n-r)! 推论1 当n≥r≥2时,有  P(n,r)=nP(n-1,r-1) (1.4) 推论2 当n≥r≥2时,有  P(n,r)=rP(n-1,r-1)+P(n-1,r) (1.5) 线排列 例一:由数字1,2,3,4,5,6可以构成多少个数字互不相同的四位数。 解:很显然 这是一个排列P(6,4)= 360 。 例二:将具有9个字母的单词FRAGMENTS进行排列,要求字母A总是紧跟在字母R的右边,问有多少种这样的排法? 解:A和R可以算一个元素,所以这是一个P(8,8), P(8,8)=8!=40320。 例 一些元素排成一个圆圈的排列 定义1.2 从集合A={a1,a2,…,an}的n个不同元素中取出r个元素按照某种顺序(如逆时针)排成一个圆圈,称这样的排列为圆排列(或称循环排列)。 圆排列 注意:把一个圆排列旋转所得到的另一个圆排列视为相同的圆排列。即排列 a1a2…ar, a2a3…ara1, a3…ara1a2, …, ara1a2…ar-1 在圆排列中是同一个. 所以圆排列的个数为 P(n,r)/r=n!/(r(n-r)!) (1.6) 圆排列 有8人围圆桌就餐,问有多少种就座方式?如果有两人不愿坐在一起,又有多少种就座方式? 解: 由公式(1.6)知,8人围圆桌就座一共有8!/8=7!种就座方式。 又由于两人不愿坐在一起,设这两个人为甲和乙,当甲和乙坐在一起时,相当于7个人围圆桌而坐,其就座方式为7!/7=6! 而甲和乙坐在一起时,又有两种情况,或者甲坐在乙的右面,或者甲坐在乙的左面,这样一来,甲和乙坐在一起时共有2×6!种就座方式 . 例三 甲和乙不坐在一起时共有就座方式的种数为 7!-2×6!=5×6!=3600 例三 4男4女围圆桌交替就座有多少种方式? 解: 首先这是一个圆排列 先让四个男(女)的围圆桌而坐,有4!/4种就座方式。 加入一个女(男)的进去就座就有4种方式 加入第二个女(男)的又有3种方式 …… 由乘法规则知,4男4女围圆桌交替就座的方式数为(4!/4)·4·3·2·1=144 例四 重排列 上面我们讨论了从集合A(A中的元素是互不相同的)中选r个元素进行排列,在每种排列中每个元素至多只出现一次的情况 现在考虑元素允许重复出现的情况,即考虑在重集B={k1·a1,k2·a2,…,kn·an}中选r个元素进行的排列。 从重集B={k1·b1,k2·b2,…,kn·bn}中选取r个元素按照一定的顺序排列起来,称这种r-排列为重排列。 定义1-3 重集B={∞·b1,∞·b2,…,∞·bn}的r排列的个数为 证明:选择r-排列的第一项,可以从n个元素中任选一个 有n种选法 第二项,由于可以重复选取,仍有n种选法。 …… 由乘法规则可求得r排列的数目为 定理1-3 由1,2,3,4,5,6这六个数字能组成多少个五位数? 又可组成多少大于34500的五位数? 一

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档