(信息学奥赛辅导)排列与组合基础知识(DOC可编).docVIP

排列与组合基础知识 有关排列与组合的基本理论和公式： 加法原理：做一件事，完成它可以有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本不同文字的书有多少种方