(信息学奥赛辅导)排列与组合基础知识

排列与组合基础知识

有关排列与组合的基本理论和公式：

加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类中办

法中有m2种不同的方法，……，在第n类办法中有mn种不同方法。那么完成这件事共有

N＝m1＋m2＋…＋mn种不同的方法，这一原理叫做加法原理。

乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种

不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×…×

mn种不同的方法，这一原理叫做乘法原理。

公式：阶乘公式n! n (n 1) (n 2) 3 2 1，规定0！＝1；

全排列公式Pnn n! 选排列公式Pn n(n 1)(n 2) (n m 1) mn!mmm、Pn Cn Pm (n m)!

圆排列：n个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：

m

nn! (n 1)! nPnmn(n 1)(n 2) (n m 1)n!0 组合数公式C m 、规定Cn 1 Pmm!m!(n m)!

012nnmn mmmm 1、Cn、Cn Cn Cn Cn 2） Cn Cn 1 Cn Cn

提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。

（2）书写方式：Pn记为P（n,r）；Cn记为C（n,r）。

加法原理例题：图1中从A点走到B点共有多少种方法？（答案：4＋2＋3＝9）

乘法原理例题：图2中从A点走到B点共有多少种方法？（答案：4×6＝24）

加法原理与乘法原理综合：图3、图4中从A走到B共有多少种方法？（答案：28、42） rr

A B A B

图1 图2

A B A B

图3 图4

而排列组合都是研究事物在某种给定的模式下所有可能的配置的数目问题，他们之间主要的区别在于是否要考虑选出元素的先后顺序，不需要考虑顺序的是组合问题，需要考虑顺序的是排序问题。

注意：在信息学奥赛中，有许多只需计数而不需具体方案的问题，都可以通过思维转换或方法转换，最后变为两类问题：一类是转变为排列组合问题，另一类是转变为递推公式问题。因此对于加法原理、乘法原理、排列、组合等知识，需要非常熟练，以达到简化问题的目的。

加法原理、乘法原理、排列、组合例题：

1. （1）用数字0、1、2、3能组成多少个三位数？（2）要求数字不能重复，又能组成多少个三位数？

2. 国际会议洽谈贸易，有5家英国公司，6家日本公司，8家中国公司，彼此都希望与异国的每个公

司单独洽谈一次，问需要安排多少个会谈场次？

3. 有编号为1、2、3、4、5的五本书需要摆放在书架上，问有多少种不同的摆放方案数。

4. 有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上，问有多少种不同方案。

5. 有编号为1、2、3、4、5的五本书需要任选3本书，问有多少种方法。

6. 五种不同颜色的珠子串成一圈项链，问有多少种不同的方法。

7. 把两个红色球、两个蓝色球、三个黄色球摆放在球架上，问有多少种方案。

8. 有男女各5人，其中3对是夫妻，他们坐成一排，若每对夫妻必须相邻而坐，问有多少种方法？

（提示：因为3对夫妻必须相邻而坐，因此可以将每对夫妻看为一个整体进行排列，这样排列总数为（7!）种方法，又因为每对夫妻可以可以左右调换位置，因此总的方案为（7！×2×2×2））

9. （1）把3个相同的球放到4个不同颜色的盒子中去，问有多少种方法？

（2）把4个相同的球放到3个不同颜色的盒子中去，问有多少种方法？

（3）推广开来，把R个相同的球放到N个不同颜色的盒子中去，问有多少种方法？

排列组合练习习题：

1. 有5本日文书、7本英文书、10本中文书。问（1）从中任取2本书有多少种方案？（2）从中取2

本相同文字的书有多少种方案？（3）从中取2本不同文字的书有多少种方案？

2. 把八个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃（即在任何一行、任何一列

都只有一个“车”），那么称八个“车”处于一个安全状态。问共有多少种不同的安全状态？

3. 从1～300之间任取3个不同的数，使得这3个数的和正好被3除尽，问有多少种方案？

4. 5对夫妇围绕圆桌坐下吃饭，共有多少种方案？如果要求夫妇必须坐在一起，又有多少种方案？

5. N个男同学和N个女同学围绕圆桌坐下，要求男女必须交替就座，问共有多少种就座方法？

6. 8人站成一排排队，如果其中的甲和乙两人要求一定站在一起，问有多少种排队方法？如果甲和乙

两人要求一定不站在一起，又有多少种方法？

7. 有N个男同学和M个女同学站成一排，其中这M个女同学要求站在一起，问共有多少种排队方法？

8. 一个长度为N＋M个字符的01字符串，问其中有N个1的字符串有多少个？

9. 一个N*M（N表示行，M表示列）的网格，从左上角（1，1）点开始走到右下角（N，M）点，

每次只能向右或者向下走，问有多少种不同的路径。

10. 在上题中，若规定N<M，行走方向仍然只能是向右或者向下行走，并且要求所经过的每一个点的

坐标(a,b)恒满足a<b的关系（a为行坐标，b为列坐标），问有多少条路径？

11. 在上上题中，如果其中有X个点设置有障碍而无法通过，问有多少条路径？其中X的值以及这X

个点的坐标由键盘输入。

12. 一个由N个0和N个1组成的01字符串，要求从左往右，1的个数始终不少于0的个数的字符串

共有多少个？如N＝1时，只有字符串10；如N＝2时，有1100、1010两个字符串；如N＝3时，有111000、110100、110010、101100、101010五个字符串。

（提示：该字符串的长度为2N，其中规定有N个1，即相当于从2N个字符中取出N个字符，方案数为C（2N，N）。该题还规定从左往右，1的个数始终不少于0的个数，那么在C（2N，N）个方案中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我们看N＝2的例子，此时所有的排列方案有0011、0101、0110、1001、1010、1100六种，其中只有1010和1100两种方案符合要求，为什么呢？实际上，在N＝2时，即有N个1，这样，我们将任意一个0填充到这N个1中的方案数有N＋1种，如下图有①、②、③三个格子可以填充0，但是要保证所有的0总在1之后，因此也就只有③的位置符合要求（如1100和1010我们都认为是所有的0在1的右边，而1001则有一个0不在1的右边），即只有C（2N，N）的1／（N＋1）种方案符合要求。所以答案为：C（2N，N）／（N＋1））。该数列称为Catalan数列，其数列为1、2、5、14、42

（举一反三：一个由N个0和N个1组成的01字符串，要求从左往右，1的个数始终不多于0的

个数的字符串共有多少个？

同理：相当于1的位置只能排在所有0的位置之后，因此个数同样为：C（2N，N）／（N＋1）。）

13. 用N个A和N个B排列成一个字符串，要求从左往右的任意一位，A的个数不能少于B的个数，

问有多少种排列方案。

14. 有2N个顾客排队购买一种产品，该产品的售价为5元，其中N个顾客手持5元的货币，其余N

个顾客手持10元货币。由于售货员手中没有零钱找零，因此售货员必须将这2N个顾客按照一定的次序排好队，问有多少种排队方式可以依次顺利发售货品，而不出现无法找零的情况。

15. 学校某年级参加数学、物理、化学的培训，人数分别是150、120、100人。

同时培训数学、物理两门课的学生有21人；同时培训数学、化学的有16人；

A 同时培训物理、化学的有8人；三科都培训的有5人。问该年级共有多少人？

B C 排列组合考试题：

16. 在15个同学中准备选出4名同学参加国际信息学奥林匹克竞赛，其中学生甲

和学生乙两人中，至少有一人必须被选中，问共有多少种选法？

17. 用A、B、C、D、E、F六个字母进行排列，其字符排列中不出现“ACE”或“DF”字串的排列方

案有多少种？

18. 栈的计数。编号分别为1～N（1<=N<=18）的N辆列车顺序进入一个栈式结构的站台（先进后出），

试问这N辆列车开出车站的所有可能次序有多少种序列。

（此题为NOIP2003年第九届普及组复赛试题第三题）

19. 有一排格子排成一排，已知共有8个格子。现有两个不同颜色的球要放在其中，要求两个球不能相

邻，问共有多少种摆放方案。

20. 有一排格子排成一排，已知共有8个格子。现有三个不同颜色的球要放在其中，要求任意两个球不

能相邻，问共有多少种摆放方案。

21. 有一排格子排成一排，已知共有8个格子。现有2个红色球和3个蓝色球要放在其中，要求如下：

（1）每个格子最多摆放一个球；（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少

22. 中，要求如下：（1）每个格子最多摆放一个球；（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少空出一个格子。问共有多少种摆放方案。如下是其中一种摆放方案。

23. 有一排格子排成一排，已知共有8个格子。现有两个相同的球要放在其中，要求两个球不能相邻，

问共有多少种摆放方案。

24. 有一排格子排成一排，已知共有8个格子。现有三个相同的球要放在其中，要求任意两个球不能相

邻，问共有多少种摆放方案。