(信息学奥赛辅导)排列与组合基础知识(7页).doc
《(信息学奥赛辅导)排列与组合基础知识(7页).doc》由会员分享,可在线阅读,更多相关《(信息学奥赛辅导)排列与组合基础知识(7页).doc(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、-(信息学奥赛辅导)排列与组合基础知识-第 6 页排列与组合基础知识有关排列与组合的基本理论和公式:加法原理:做一件事,完成它可以有n类办法,在第一类办法中有m1种不同的方法,在第二类中办法中有m2种不同的方法,在第n类办法中有mn种不同方法。那么完成这件事共有Nm1m2mn种不同的方法,这一原理叫做加法原理。乘法原理:做一件事,完成它需要分成n个步骤,做第一步有m1种不同的方法,做第二步有m2种不同的方法,做第n步有mn种不同的方法,那么完成这件事共有Nm1m2mn种不同的方法,这一原理叫做乘法原理。公式:阶乘公式,规定0!1;全排列公式选排列公式、圆排列:n个不同元素不分首位围成一个圆圈达
2、到圆排列,则排列数为:组合数公式、规定提示:(1)全排列问题和选排列问题,都可根据乘法原理推导出来。(2)书写方式:记为P(n,r);记为C(n,r)。加法原理例题:图1中从A点走到B点共有多少种方法?(答案:4239)乘法原理例题:图2中从A点走到B点共有多少种方法?(答案:4624)加法原理与乘法原理综合:图3、图4中从A走到B共有多少种方法?(答案:28、42)注意:在信息学奥赛中,有许多只需计数而不需具体方案的问题,都可以通过思维转换或方法转换,最后变为两类问题:一类是转变为排列组合问题,另一类是转变为递推公式问题。因此对于加法原理、乘法原理、排列、组合等知识,需要非常熟练,以达到简化
3、问题的目的。加法原理、乘法原理、排列、组合例题:1. (1)用数字0、1、2、3能组成多少个三位数?(2)要求数字不能重复,又能组成多少个三位数?(提示:(1)先确定百位数,只能是1、2、3之间的数字;再确定十位数,可以为0、1、2、3任何一个;最后确定个位数,可以为0、1、2、3任何一个。根据乘法原理,共有34448个。(2)同理,先确定百位数、再确定十位数、最后确定个位数,根据乘法原理,共有332个)2. 国际会议洽谈贸易,有5家英国公司,6家日本公司,8家中国公司,彼此都希望与异国的每个公司单独洽谈一次,问需要安排多少个会谈场次?(提示:共分为中英、中日、英日会谈三类,对于中英会谈,先选
4、定中方公司有8种选法,在选定英方公司有5种选法,故根据乘法原理有58:同理中日86;英日56;总的会谈:118)3. 有编号为1、2、3、4、5的五本书需要摆放在书架上,问有多少种不同的摆放方案数。(提示:此题为全排列,故摆放方案总数为P(5,5)=5!=120种。也可以按乘法原理思考,即摆放第一本书有5种选择,摆放第二本数有4种选择,最后结果为54321即5!)4. 有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上,问有多少种不同方案。(提示:可根据选排列公式计算,总数为P(5,3)。也可以根据乘法原理计算,答案为54360)5. 有编号为1、2、3、4、5的五本书需要任选3本书
5、,问有多少种方法。(提示:此题为组合问题,答案为10)6. 五种不同颜色的珠子串成一圈项链,问有多少种不同的方法。(提示:此题属于圆排列问题,答案为(51)!24)7. 把两个红色球、两个蓝色球、三个黄色球摆放在球架上,问有多少种方案。(提示:此题为排列问题。摆放方案总数为(223)!种,但是两个红球一样,所以要除以2!,同理两个蓝球,除以2!,三个黄球,除以3!,即摆放方案总数为)8. 有男女各5人,其中3对是夫妻,他们坐成一排,若每对夫妻必须相邻而坐,问有多少种方法?(提示:因为3对夫妻必须相邻而坐,因此可以将每对夫妻看为一个整体进行排列,这样排列总数为(7!)种方法,又因为每对夫妻可以可
6、以左右调换位置,因此总的方案为(7!222)9. (1)把3个相同的球放到4个不同颜色的盒子中去,问有多少种方法?(2)把4个相同的球放到3个不同颜色的盒子中去,问有多少种方法?(3)推广开来,把R个相同的球放到N个不同颜色的盒子中去,问有多少种方法?(提示:这是允许重复组合的典型模型。)(解答(1):3个球放入4个不同颜色盒子的分法共有3、0、0、0;1、2、0、0;1、1、1、0三类;对于第一类3、0、0、0的方法,共有种方法,但是有3个0是一样的,所以应该除以,即第一类分法的方法数为种,同理,第二种分法的方法数为,第三种分法的方法数为,所以总共的方法数为()种。 解答(2)自行求解。 解
7、答(3):这一类问题,我们称为重复组合问题,其求解公式为C(n+r-1,r)。请记住该公式即可。)排列组合练习习题:1. 有5本日文书、7本英文书、10本中文书。问(1)从中任取2本书有多少种方案?(2)从中取2本相同文字的书有多少种方案?(3)从中取2本不同文字的书有多少种方案? (提示:此题为组合问题。答案分别为:、)2. 把八个“车”放在88的国际象棋棋盘上,如果它们两两均不能互吃(即在任何一行、任何一列都只有一个“车”),那么称八个“车”处于一个安全状态。问共有多少种不同的安全状态?(提示:乘法原理。先在第一行放置一个“车”,有8种选法,再在第二行放置一个“车”,还有7种选法,同理,总
8、共有8721,即8!种不同的安全状态。)3. 从1300之间任取3个不同的数,使得这3个数的和正好被3除尽,问有多少种方案?(提示:1300之间的数被3除的余数共有三类,分别是余数为0、余数为1、余数为2,每类各100个数。任取3个数且这3个数相加的和正好被3除尽的情况只能是以下四种情况之一:余数为012;000;111;222。再根据乘法原理和加法原理即可求解。答案为:100100100100999810099981009998)4. 5对夫妇围绕圆桌坐下吃饭,共有多少种方案?如果要求夫妇必须坐在一起,又有多少种方案?(提示:此题为圆排列问题。第一问的答案为(101)!。对于第二问,因为夫妇
9、必须坐在一起,因此可以将每对夫妇看为一个整体先行进行圆排列,排列方案为(51)!,又因为每对夫妇可以左右交换位置,因此总的排列方案为(51)!22222。)5. N个男同学和N个女同学围绕圆桌坐下,要求男女必须交替就座,问共有多少种就座方法?(提示:先经这N个男同学进行圆排列,方案为(N1)!,然后每个女同学依次坐入到两个男同学中间,第一个女同学有N个位置可以选,第二个女同学有N1个位置可以选,依此类推。根据乘法原理,所有的就座方案为(N1)!N!)6. 8人站成一排排队,如果其中的甲和乙两人要求一定站在一起,问有多少种排队方法?如果甲和乙两人要求一定不站在一起,又有多少种方法?(提示:第一问
10、中,甲和乙一定站在一起,因此可以先将此二人看为一个整体,则排队方法为7!,又因为甲和乙可以交换位置,因此总的方案为7!2。对于第二问,则用8个人的总排队方案数减去甲和乙站在一起的方案数即可,答案为8!7!2。)7. 有N个男同学和M个女同学站成一排,其中这M个女同学要求站在一起,问共有多少种排队方法?(提示:排列问题乘法原理。分两步:第一,先将这M个女同学看成一个整体排列;第二,再将这M个女同学再排列。然后根据乘法原理即可求得。答案为:(N1)!M!)8. 一个长度为NM个字符的01字符串,问其中有N个1的字符串有多少个?(提示:组合问题。现有NM个字符,如果把1看作取字符,把0看作不取字符,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息学 辅导 排列 组合 基础知识
限制150内