------------------------------------------作者xxxx------------------------------------------日期xxxx(信息学奥赛辅导)排列与组合基础知识【精品文档】【精品文档】【精品文档】【精品文档】【精品文档】【精品文档】排列与组合基础知识有关排列与组合的基本理论和公式:加法原理:做一件事,完成它可以有n类办法,在第一类办法中有m1种不同的方法,在第二类中办法中有m2种不同的方法,……,在第n类办法中有mn种不同方法。那么完成这件事共有N=m1+m2+…+mn种不同的方法,这一原理叫做加法原理。乘法原理:做一件事,完成它需要分成n个步骤,做第一步有m1种不同的方法,做第二步有m2种不同的方法,……,做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×…×mn种不同的方法,这一原理叫做乘法原理。公式:阶乘公式,规定0!=1;全排列公式选排列公式、圆排列:n个不同元素不分首位围成一个圆圈达到圆排列,则排列数为:组合数公式、规定、、)提示:(1)全排列问题和选排列问题,都可根据乘法原理推导出来。(2)书写方式:记为P(n,r);记为C(n,r)。加法原理例题:图1中从A点走到B点共有多少种方法?(答案:4+2+3=9)乘法原理例题:图2中从A点走到B点共有多少种方法?(答案:4×6=24)加法原理与乘法原理综合:图3、图4中从A走到B共有多少种方法?(答案:28、42)注意:在信息学奥赛中,有许多只需计数而不需具体方案的问题,都可以通过思维转换或方法转换,最后变为两类问题:一类是转变为排列组合问题,另一类是转变为递推公式问题。因此对于加法原理、乘法原理、排列、组合等知识,需要非常熟练,以达到简化问题的目的。加法原理、乘法原理、排列、组合例题:(1)用数字0、1、2、3能组成多少个三位数?(2)要求数字不能重复,又能组成多少个三位数?(提示:(1)先确定百位数,只能是1、2、3之间的数字;再确定十位数,可以为0、1、2、3任何一个;最后确定个位数,可以为0、1、2、3任何一个。根据乘法原理,共有3×4×4=48个。(2)同理,先确定百位数、再确定十位数、最后确定个位数,根据乘法原理,共有3×3×2个)国际会议洽谈贸易,有5家英国公司,6家日本公司,8家中国公司,彼此都希望与异国的每个公司单独洽谈一次,问需要安排多少个会谈场次?(提示:共分为中英、中日、英日会谈三类,对于中英会谈,先选定中方公司有8种选法,在选定英方公司有5种选法,故根据乘法原理有5×8:同理中日8×6;英日5×6;总的会谈:118)有编号为1、2、3、4、5的五本书需要摆放在书架上,问有多少种不同的摆放方案数。(提示:此题为全排列,故摆放方案总数为P(5,5)=5!=120种。也可以按乘法原理思考,即摆放第一本书有5种选择,摆放第二本数有4种选择,……,最后结果为5×4×3×2×1即5!)有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上,问有多少种不同方案。(提示:可根据选排列公式计算,总数为P(5,3)。也可以根据乘法原理计算,答案为5×4×3=60)有编号为1、2、3、4、5的五本书需要任选3本书,问有多少种方法。(提示:此题为组合问题,答案为=10)五种不同颜色的珠子串成一圈项链,问有多少种不同的方法。(提示:此题属于圆排列问题,答案为(5-1)!=24)把两个红色球、两个蓝色球、三个黄色球摆放在球架上,问有多少种方案。(提示:此题为排列问题。摆放方案总数为(2+2+3)!种,但是两个红球一样,所以要除以2!,同理两个蓝球,除以2!,三个黄球,除以3!,即摆放方案总数为)有男女各5人,其中3对是夫妻,他们坐成一排,若每对夫妻必须相邻而坐,问有多少种方法?(提示:因为3对夫妻必须相邻而坐,因此可以将每对夫妻看为一个整体进行排列,这样排列总数为(7!)种方法,又因为每对夫妻可以可以左右调换位置,因此总的方案为(7!×2×2×2))(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)自行求解。解答(3):这一类问题,我们称为重复组合问题,其求解公式为C(n+r-1,r)。请记住该公式即可。)排列组合练习习题:有5本日文书、7本英文书、10本中文书。问(1)从中任取2本书有多少种方案?(2)从中取2本相同文字的书有多少种方案?(3)从中取2本不同文字的书有多少种方案?(提示:此题为组合问题。答案分别为:、、)把八个“车”放在8×8的国际象棋棋盘上,如果它们两两均不能互吃(即在任何一行、任何一列都只有一个“车”),那么称八个“车”处于一个安全状态。问共有多少种不同的安全状态?(提示:乘法原理。先在第一行放置一个“车”,有8种选法,再在第二行放置一个“车”,还有7种选法,同理……,总共有8×7×…×2×1,即8!种不同的安全状态。)从1~300之间任取3个不同的数,使得这3个数的和正好被3除尽,问有多少种方案?(提示:1~300之间的数被3除的余数共有三类,分别是余数为0、余数为1、余数为2,每类各100个数。任取3个数且这3个数相加的和正好被3除尽的情况只能是以下四种情况之一:余数为0+1+2;0+0+0;1+1+1;2+2+2。再根据乘法原理和加法原理即可求解。答案为:100×100×100+100×99×98+100×99×98+100×99×98)5对夫妇围绕圆桌坐下吃饭,共有多少种方案?如果要求夫妇必须坐在一起,又有多少种方案?(提示:此题为圆排列问题。第一问的答案为(10-1)!。对于第二问,因为夫妇必须坐在一起,因此可以将每对夫妇看为一个整体先行进行圆排列,排列方案为(5-1)!,又因为每对夫妇可以左右交换位置,因此总的排列方案为(5-1)!×2×2×2×2×2。)N个男同学和N个女同学围绕圆桌坐下,要求男女必须交替就座,问共有多少种就座方法?(提示:先经这N个男同学进行圆排列,方案为(N-1)!,然后每个女同学依次坐入到两个男同学中间,第一个女同学有N个位置可以选,第二个女同学有N-1个位置可以选,依此类推。根据乘法原理,所有的就座方案为(N-1)!×N!)8人站成一排排队,如果其中的甲和乙两人要求一定站在一起,问有多少种排队方法?如果甲和乙两人要求一定不站在一起,又有多少种方法?(提示:第一问中,甲和乙一定站在一起,因此可以先将此二人看为一个整体,则排队方法为7!,又因为甲和乙可以交换位置,因此总的方案为7!×2。对于第二问,则用8个人的总排队方案数减去甲和乙站在一起的方案数即可,答案为8!-7!×2。)有N个男同学和M个女同学站成一排,其中这M个女同学要求站在一起,问共有多少种排队方法?(提示:排列问题+乘法原理。分两步:第一,先将这M个女同学看成一个整体排列;第二,再将这M个女同学再排列。然后根据乘法原理即可求得。答案为:(N+1)!×M!)一个长度为N+M个字符的01字符串,问其中有N个1的字符串有多少个?(提示:组合问题。现有N+M个字符,如果把1看作取字符,把0看作不取字符,那么其中有N个1的字符串即相当于从N+M个字符中,任取N个字符的组合。答案为:C(N+M,N))一个N*M(N表示行,M表示列)的网格,从左上角(1,1)点开始走到右下角(N,M)点,每次只能向右或者向下走,问有多少种不同的路径。(方法一:从(1,1)点走到(N,M)点,无论如何走一共都要走(N-1)+(M-1)步,其中N-1步向右走,M-1步向下走,因为只有两种走法,不妨用二进制表示走路方式,1表示向右走,0表示向下走。则可用一个长度为(N+M-2)的二进制串来表示走路方法,其中如果出现了N-1个1,则表示找到了一种路径。从而把题目转化为求长度为N+M-2的2进制串中有N-1个1的个数,即求组合数学公式C(N+M-2,N-1)的值。方法二:对本题稍加分析就能发现,要到达棋盘上的某个点,只能从该点的上边过来,或者从该点的左边过来,根据加法原理,要到达该点的路径数目,就等于到达该点上点的路径与该点左点的路径数目之和,因此我们可以按照逐行递推的方法求出从起点到终点的路径数目。初始化,左上角第一个元素值为1,其它点的值为上点与左点的和。)对于如右图的网格,用方法一的答案为C(4+3,3)=35;用方法二逐行递推的方法得到网格上的数字,最后答案也为35。比较两种方法,当数据较小时,采用公式一比较直接,但如果数据较大时,公式一的乘法运算量较大,这时可考虑用方法二逐行递推求得答案。在上题中,若规定N
本文档为【(信息学奥赛辅导)排列与组合基础知识】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。