精品word 名师归纳总结 - - - - - - - - - - - -信息学奥林匹克竞赛——排列与组合基础学问 第 1 页排列与组合基础学问有关排列与组合的基本理论和公式：加法原理：做一件事，完成它可以有 n 类方法，在第一类方法中有 m1 种不同的方法，在其次类中方法中有 m2 种不同的方法， ，在第 n 类方法中有 m n 种不同方法；那么完成这件事共有N ＝ m1＋ m2＋ ＋ mn 种不同的方法，这一原理叫做加法原理；乘法原理：做一件事，完成它需要分成 n 个步骤，做第一步有 m1 种不同的方法，做其次步有 m2 种不同的方法， ， 做第 n 步有 m n 种不同的方法， 那么完成这件事共有 N ＝m1× m 2× × m n 种不同的方法，这一原理叫做乘法原理；公式：阶乘公式 n.n 〔n1〕 〔n2〕 3 2 1 ，规定 0！＝ 1；Pn全排列公式 n选排列公式 Pmn.n〔n1〕〔n2〕 〔n m 1〕n . 、 PmC m Pmn〔n m〕.n n m圆排列： n 个不同元素不分首位围成一个圆圈达到圆排列，就排列数为：n . 〔n n1〕.组合数公式PmC m nn〔 n1〕〔n2〕 〔 n m 1〕n. 、规定C 0 1Pn mmC m C n m 、 C mm.Cm C m1 、 C 0m.〔 n m〕.C1 C 2 Cnn2n ）n n n 1 n n n n n n提示：（ 1）全排列问题和选排列问题，都可依据乘法原理推导出来；（ 2）书写方式：Pr 记为 P（n,r ）； C r 记为 C（ n,r）；n n加法原理例题：图 1 中从 A 点走到 B 点共有多少种方法？（答案： 4＋ 2＋ 3＝9）乘法原理例题：图 2 中从 A 点走到 B 点共有多少种方法？（答案： 4× 6＝ 24）加法原理与乘法原理综合：图 3、图 4 中从 A 走到 B 共有多少种方法？（答案： 28、42）A AB B图 1 图 2A AB B图 3 图 4精选名师 优秀名师 - - - - - - - - - -第 1 页，共 6 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -信息学奥林匹克竞赛——排列与组合基础学问 第 2 页留意：在信息学奥赛中，有很多只需计数而不需详细方案的问题，都可以通过思维转换或方法转换，最终变为两类问题：一类是转变为排列组合问题，另一类是转变为递推公式问题；因此对于加法原理、乘法原理、排列、组合等学问，需要特别娴熟，以达到简化问题的目的；加法原理、乘法原理、排列、组合例题：1. （ 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 个）2. 国际会议洽谈贸易，有 5 家英国公司， 6 家日本公司， 8 家中国公司，彼此都期望与异国的每个公司单独洽谈一次，问需要支配多少个会谈场次？（提示：共分为中英、中日、英日会谈三类，对于中英会谈，先选定中方公司有 8 种选法，在选定英方公司有 5 种选法，故依据乘法原理有 5× 8：同理中日 8×6；英日 5× 6；总的会谈： 118）3. 有编号为 1、2、3、 4、5 的五本书需要摆放在书架上，问有多少种不同的摆放方案数；（提示：此题为全排列，故摆放方案总数为 P〔5,5〕=5.=120 种；也可以按乘法原理摸索，即摆放第一本书有 5 种挑选，摆放其次本数有 4 种挑选， ,, ，最终结果为 5× 4× 3×2× 1 即 5！）4. 有编号为 1、2、3、 4、5 的五本书需要任选 3 本书摆放在书架上，问有多少种不同方案；（提示：可依据选排列公式运算，总数为 P〔5,3〕；也可以依据乘法原理运算，答案为 5×4× 3＝ 60）5. 有编号为 1、2、3、 4、5 的五本书需要任选 3 本书，问有多少种方法；（提示：此题为组合问题，答案为3 5 4 3C5 ＝ 10）3.6. 五种不同颜色的珠子串成一圈项链，问有多少种不同的方法；（提示：此题属于圆排列问题，答案为（ 5－ 1）！＝ 24）7. 把两个红色球、两个蓝色球、三个黄色球摆放在球架上，问有多少种方案；（提示：此题为排列问题；摆放方案总数为（ 2＋ 2＋3）！种，但是两个红球一样，所以要除以 2！，同理两个蓝球，除以 2！，三个黄球，除以 3！，即摆放方案总数为 〔2 2 3〕. 210 ）2. 2. 3.8. 有男女各 5 人，其中 3 对是夫妻，他们坐成一排，如每对夫妻必需相邻而坐，问有多少种方法？（提示：由于 3 对夫妻必需相邻而坐，因此可以将每对夫妻看为一个整体进行排列，这样排列总数为（ 7. ）种方法，又由于每对夫妻可以可以左右调换位置，因此总的方案为（ 7！× 2× 2× 2）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 三4类；对于第一类 3、0、0、0 的方法， 共有P4 种方法， 但是有 3 个 0 是一样的， 所以应当除以P3 ，3即第一类分法的方法数为P4 / P3 种，同理，其次种分法的方法数为 P4 / P2 ，第三种分法的方法4 3 4 2数为 P 4 / P3 ，所以总共的方法数为（ P4 / P3 ＋ P4 / P2 ＋ P4 / P3 ）种；4 3 4 3 4 2 4 3解答（ 2）自行求解；解答（ 3）：这一类问题， 我们称为重复组合问题， 其求解公式为 C（ n+r-1,r ）；请记住该公式即可 ；）排列组合练习习题：精选名师 优秀名师 - - - - - - - - - -第 2 页，共 6 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -信息学奥林匹克竞赛——排列与组合基础学问 第 3 页1. 有 5 本日文书、 7 本英文书、 10 本中文书；问（ 1）从中任取 2 本书有多少种方案？（ 2）从中取 2本相同文字的书有多少种方案？（ 3）从中取 2 本不同文字的书有多少种方案？（提示：此题为组合问题；答案分别为：C2 、 C 2 C 2C2 、 C 2〔C2C2 C 2 〕 ）5 7 105 7 105 7 10 5 7 102. 把八个“车”放在 8× 8 的国际象棋棋盘上，假如它们两两均不能互吃（即在任何一行、任何一列都只有一个“车” ），那么称八个“车”处于一个安全状态；问共有多少种不同的安全状态？（提示：乘法原理；先在第一行放置一个“车” ，有 8 种选法，再在其次行放置一个“车” ，仍有 7种选法，同理 ,, ，总共有 8× 7×, × 2× 1，即 8！种不同的安全状态； ）3. 从 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）4. 5 对夫妇环绕圆桌坐下吃饭，共有多少种方案？假如要求夫妇必需坐在一起，又有多少种方案？（提示：此题为圆排列问题；第一问的答案为（ 10－ 1）！；对于其次问，由于夫妇必需坐在一起， 因此可以将每对夫妇看为一个整体先行进行圆排列， 排列方案为 （ 5－ 1）！，又由于每对夫妇可以左右交换位置，因此总的排列方案为（ 5－1）！× 2×2× 2× 2× 2；）5. N 个男同学和 N 个女同学环绕圆桌坐下，要求男女必需交替就座，问共有多少种就座方法？（提示：先经这 N 个男同学进行圆排列，方案为（ N－ 1）！，然后每个女同学依次坐入到两个男同学中间，第一个女同学有 N 个位置可以选，其次个女同学有 N －1 个位置可以选，依此类推；依据乘法原理，全部的就座方案为（ N－ 1）！× N！）6. 8 人站成一排排队，假如其中的甲和乙两人要求肯定站在一起，问有多少种排队方法？假如甲和乙两人要求肯定不站在一起，又有多少种方法？（提示：第一问中，甲和乙肯定站在一起，因此可以先将此二人看为一个整体，就排队方法为 7！，又由于甲和乙可以交换位置，因此总的方案为 7！× 2；对于其次问，就用 8 个人的总排队方案 数减去甲和乙站在一起的方案数即可，答案为 8！－ 7！× 2；）7. 有 N 个男同学和 M 个女同学站成一排， 其中这 M 个女同学要求站在一起， 问共有多少种排队方法？（提示：排列问题＋乘法原理；分两步：第一，先将这 M 个女同学看成一个整体排列；其次，再将这 M 个女同学再排列；然后依据乘法原理即可求得；答案为： （N ＋ 1）！× M ！）8. 一个长度为 N ＋M 个字符的 01 字符串，问其中有 N 个 1 的字符串有多少个？（提示：组合问题；现有 N＋ M 个字符，假如把 1 看作取字符，把 0 看作不取字符，那么其中有 N个 1 的字符串即相当于从 N ＋M 个字符中，任取 N 个字符的组合；答案为： C（ N＋ M ， N）9. 一个 N*M （N 表示行， M 表示列）的网格，从左上角（ 1，1）点开头走到右下角（ N， M ）点，每次只能向右或者向下走，问有多少种不同的路径；1111112345136101514102035（方法一：从（ 1， 1）点走到（ N， M ）点，无论如何走一共都要 走（ N － 1）＋（ M － 1）步，其中 N － 1 步向右走， M － 1 步向下走，由于只有两种走法，不妨用二进制表示走路。
