湖南师大附中 信息学奥林匹克竞赛辅导——排列与组合基础知识 第1 页 排列与组合基础知识 有关排列与组合的基本理论和公式： 加法原理：做一件事，完成它可以有n 类办法，在第一类办法中有m1 种不同的方法，在第二类中办法中有m2 种不同的方法，……，在第n 类办法中有mn 种不同方法。那么完成这件事共有N＝m1＋m2＋…＋mn 种不同的方法，这一原理叫做加法原理。 乘法原理：做一件事，完成它需要分成n 个步骤，做第一步有m1 种不同的方法，做第二步有m2 种不同的方法，……，做第n 步有mn 种不同的方法，那么完成这件事共有N＝m1×m2×…×mn 种不同的方法，这一原理叫做乘法原理。 公式：阶乘公式!(1) (2)3 2 1nnnn，规定 0！＝1； 全排列公式 !nnPn 选排列公式!(1)(2)(1)()!mnnPn nnnmnm、mmmnnmPCP 圆排列：n 个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：!(1)!nnn 组合数公式(1)(2)(1)!!!()!mmnnmmPn nnnmnCPmmnm、规定01nC mnmnnCC、11mmmnnnCCC 、0122nnnnnnCCCC） 提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。 （2）书写方式：rnP 记为P（n,r）；rnC 记为C（n,r）。 加法原理例题：图1 中从A 点走到B 点共有多少种方法？（答案：4＋2＋3＝9） 乘法原理例题：图2 中从A 点走到B 点共有多少种方法？（答案：4×6＝24） 加法原理与乘法原理综合：图3、图4 中从A 走到B 共有多少种方法？（答案：28、42） A B 图1 A B 图2 A B 图3 A B 图4 湖南师大附中 信息学奥林匹克竞赛辅导——排列与组合基础知识 第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）同理，先确定百位数、再确定十位数、最...
