2022年排列与组合基础知识 .pdf

《2022年排列与组合基础知识 .pdf》由会员分享，可在线阅读，更多相关《2022年排列与组合基础知识 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息学奥林匹克竞赛辅导排列与组合基础知识第 1 页排列与组合基础知识有关排列与组合的基本理论和公式：加法原理：做一件事，完成它可以有n 类办法，在第一类办法中有m1种不同的方法，在第二类中办法中有m2种不同的方法，在第n 类办法中有mn种不同方法。那么完成这件事共有Nm1m2 mn种不同的方法，这一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n 个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第 n 步有 mn种不同的方法，那么完成这件事共有Nm1m2mn种不同的方法，这一原理叫做乘法原理。公式：阶乘公式!(1)(2)3 2 1nnnn，规定 0！1；全排列公式!nn

2、Pn选排列公式!(1)(2)(1)()!mnnPn nnnmnm、mmmnnmPCP圆排列：n 个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：!(1)!nnn组合数公式(1)(2)(1)!()!mmnnmmPn nnnmnCPmm nm、规定01nCmn mnnCC、11mmmnnnCCC、0122nnnnnnCCCC）提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。（2）书写方式：rnP记为 P（n,r）；rnC记为 C（n,r）。加法原理例题：图1中从 A 点走到 B 点共有多少种方法？（答案：4 239）乘法原理例题：图2中从 A 点走到 B 点共有多少种方法？（答

3、案：4 624）加法原理与乘法原理综合：图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）要求数字不能重复，又能组成多少个三位数

4、？（提示：（1）先确定百位数，只能是1、2、3 之间的数字；再确定十位数，可以为0、1、2、3 任何一个；最后确定个位数，可以为0、1、2、3任何一个。根据乘法原理，共有34448 个。（2）同理，先确定百位数、再确定十位数、最后确定个位数，根据乘法原理，共有3 32 个）2.国际会议洽谈贸易，有5 家英国公司，6 家日本公司，8家中国公司，彼此都希望与异国的每个公司单独洽谈一次，问需要安排多少个会谈场次？（提示：共分为中英、中日、英日会谈三类，对于中英会谈，先选定中方公司有8 种选法，在选定英方公司有5 种选法，故根据乘法原理有58：同理中日86；英日 56；总的会谈：118）3.有编号为1

5、、2、3、4、5 的五本书需要摆放在书架上，问有多少种不同的摆放方案数。（提示：此题为全排列，故摆放方案总数为P(5,5)=5!=120 种。也可以按乘法原理思考，即摆放第一本书有5 种选择，摆放第二本数有4 种选择，,，最后结果为5432 1 即 5！）4.有编号为1、2、3、4、5 的五本书需要任选3 本书摆放在书架上，问有多少种不同方案。（提示：可根据选排列公式计算，总数为P(5,3)。也可以根据乘法原理计算，答案为54 360）5.有编号为1、2、3、4、5 的五本书需要任选3 本书，问有多少种方法。（提示：此题为组合问题，答案为355433!C10）6.五种不同颜色的珠子串成一圈项链

6、，问有多少种不同的方法。（提示：此题属于圆排列问题，答案为（5 1）！24）7.把两个红色球、两个蓝色球、三个黄色球摆放在球架上，问有多少种方案。（提示：此题为排列问题。摆放方案总数为（223）！种，但是两个红球一样，所以要除以2！，同理两个蓝球，除以2！，三个黄球，除以3！，即摆放方案总数为(223)!2102!2!3!）8.有男女各5 人，其中3 对是夫妻，他们坐成一排，若每对夫妻必须相邻而坐，问有多少种方法？（提示：因为3 对夫妻必须相邻而坐，因此可以将每对夫妻看为一个整体进行排列，这样排列总数为（7!）种方法，又因为每对夫妻可以可以左右调换位置，因此总的方案为（7！2 22）9.（1）

7、把 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 的方法，共有44P种方法，但是有 3 个 0 是一样的，所以应该除以33P，即第一类分法的方法数为4343/PP种，同理，第二种分法的方法数为4242/PP，第三种分法的方法数为4343/PP，所以总共的方法数为（4

8、343/PP4242/PP4343/PP）种。解答（2）自行求解。解答（3）：这一类问题，我们称为重复组合问题，其求解公式为C（n+r-1,r）。请记住该公式即可。）排列组合练习习题：文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S

9、10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码

10、:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7

11、O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H1

12、0 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y

13、9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T

14、7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z

15、5F2Y9S10信息学奥林匹克竞赛辅导排列与组合基础知识第 3 页1.有 5 本日文书、7 本英文书、10 本中文书。问（1）从中任取2 本书有多少种方案？（2）从中取 2本相同文字的书有多少种方案？（3）从中取2 本不同文字的书有多少种方案？（提示：此题为组合问题。答案分别为：25 7 10C、2225710CCC、22225 7 105710()CCCC）2.把八个“车”放在88 的国际象棋棋盘上，如果它们两两均不能互吃（即在任何一行、任何一列都只有一个“车”），那么称八个“车”处于一个安全状态。问共有多少种不同的安全状态？（提示：乘法原理。先在第一行放置一个“车”，有 8 种选法，再在第

16、二行放置一个“车”，还有 7种选法，同理,，总共有87,21，即 8！种不同的安全状态。）3.从 1300 之间任取3 个不同的数，使得这3 个数的和正好被3 除尽，问有多少种方案？（提示：1300 之间的数被3 除的余数共有三类，分别是余数为0、余数为1、余数为2，每类各100 个数。任取3 个数且这3 个数相加的和正好被3 除尽的情况只能是以下四种情况之一：余数为 012；0 00；111；222。再根据乘法原理和加法原理即可求解。答案为：10010010010099 98100999810099 98）4.5 对夫妇围绕圆桌坐下吃饭，共有多少种方案？如果要求夫妇必须坐在一起，又有多少种方

17、案？（提示：此题为圆排列问题。第一问的答案为（101）！。对于第二问，因为夫妇必须坐在一起，因此可以将每对夫妇看为一个整体先行进行圆排列，排列方案为（51）！，又因为每对夫妇可以左右交换位置，因此总的排列方案为（51）！2222 2。）5.N 个男同学和N 个女同学围绕圆桌坐下，要求男女必须交替就座，问共有多少种就座方法？（提示：先经这N 个男同学进行圆排列，方案为（N1）！，然后每个女同学依次坐入到两个男同学中间，第一个女同学有N 个位置可以选，第二个女同学有N1 个位置可以选，依此类推。根据乘法原理，所有的就座方案为（N1）！N！）6.8 人站成一排排队，如果其中的甲和乙两人要求一定站在一

18、起，问有多少种排队方法？如果甲和乙两人要求一定不站在一起，又有多少种方法？（提示：第一问中，甲和乙一定站在一起，因此可以先将此二人看为一个整体，则排队方法为7！，又因为甲和乙可以交换位置，因此总的方案为7！2。对于第二问，则用8 个人的总排队方案数减去甲和乙站在一起的方案数即可，答案为8！7！2。）7.有 N 个男同学和M 个女同学站成一排，其中这 M 个女同学要求站在一起，问共有多少种排队方法？（提示：排列问题乘法原理。分两步：第一，先将这M 个女同学看成一个整体排列；第二，再将这 M 个女同学再排列。然后根据乘法原理即可求得。答案为：（N1）！M！）8.一个长度为NM 个字符的01 字符串

19、，问其中有N 个 1 的字符串有多少个？（提示：组合问题。现有NM 个字符，如果把1 看作取字符，把0 看作不取字符，那么其中有N个 1 的字符串即相当于从NM 个字符中，任取N 个字符的组合。答案为：C（NM，N）9.一个 N*M（N 表示行，M 表示列）的网格，从左上角（1，1）点开始走到右下角（N，M）点，每次只能向右或者向下走，问有多少种不同的路径。（方法一：从（1，1）点走到（N，M）点，无论如何走一共都要走（N1）（M 1）步，其中N1 步向右走，M1 步向下走，因为只有两种走法，不妨用二进制表示走路方式，1 表示向右走，0 表示向下走。则可用一个长度为（NM2）的二进制串来表示走

20、路方法，其中如果出现了N1 个 1，则表示找到了一种路径。从而把题目转化为求长度为NM2 的 2 进制串中有 N1 个 1 的个数，即求组合数学公式C（NM2，N 1）的值。方法二：对本题稍加分析就能发现，要到达棋盘上的某个点，只能从该点的上边过来，或者从该1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10

21、文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:C

22、V2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1

23、W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10

24、HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C

25、3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7

26、ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F

27、2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10信息学奥林匹克竞赛辅导排列与组合基础知识第 4 页点的左边过来，根据加法原理，要到达该点的路径数目，就等于到达该点上点的路径与该点左点的路径数目之和，因此我们可以按照逐行递推的方法求出从起点到终点的路径数目。初始化，左上角第一个元素值为1，其它点的值为上点与左点的和。）对于如右图的网格，用方法一的答案为C（43，3）35；用方法二逐行递推的方法得到网格上的数字，最后答案也为35。比较两种方法，当数据较小时，采用公式一

28、比较直接，但如果数据较大时，公式一的乘法运算量较大，这时可考虑用方法二逐行递推求得答案。10.在上题中，若规定NM，行走方向仍然只能是向右或者向下行走，并且要求所经过的每一个点的坐标(a,b)恒满足 ab 的关系（a 为行坐标，b 为列坐标），问有多少条路径？（测试数据：N4，M5；答案：）11.在上上题中，如果其中有X 个点设置有障碍而无法通过，问有多少条路径？其中X 的值以及这X个点的坐标由键盘输入。（测试数据：N5，M4，X2，这 2 个障碍点坐标为（2,3）和（4,2）；答案：）12.一个由 N 个 0 和 N 个 1 组成的 01 字符串，要求从左往右，1 的个数始终不少于0 的个数

29、的字符串共有多少个？如N1 时，只有字符串10；如 N2 时，有 1100、1010 两个字符串；如N3 时，有 111000、110100、110010、101100、101010 五个字符串。（提示：该字符串的长度为2N，其中规定有N 个 1，即相当于从2N 个字符中取出N 个字符，方案数为 C（2N，N）。该题还规定从左往右，1 的个数始终不少于0 的个数，那么在C（2N，N）个方案中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我们看N2 的例子，此时所有的排列方案有0011、0101、0110、1001、1010、1100 六种，其中只有1010 和 1100 两种方案符合

30、要求，为什么呢？实际上，在N2 时，即有 N 个 1，这样，我们将任意一个0 填充到这 N 个 1 中的方案数有N1 种，如下图有、三个格子可以填充0，但是要保证所有的 0 总在 1 之后，因此也就只有的位置符合要求（如1100 和 1010 我们都认为是所有的0 在 1的右边，而1001 则有一个0 不在 1 的右边），即只有 C（2N，N）的 1（N1）种方案符合要求。所以答案为：C（2N，N）（N1）。该数列称为Catalan 数列，其数列为1、2、5、14、42,。对于此问题，有许多变形应用，请熟记该公式。）1 1（举一反三：一个由N 个 0 和 N 个 1 组成的 01 字符串，要求

31、从左往右，1 的个数始终不多于0 的个数的字符串共有多少个？同理：相当于 1 的位置只能排在所有0 的位置之后，因此个数同样为：C（2N，N）（N1）。）13.用 N 个 A 和 N 个 B 排列成一个字符串，要求从左往右的任意一位，A 的个数不能少于B 的个数，问有多少种排列方案。14.有 2N 个顾客排队购买一种产品，该产品的售价为5 元，其中N 个顾客手持5 元的货币，其余N个顾客手持10 元货币。由于售货员手中没有零钱找零，因此售货员必须将这2N 个顾客按照一定的次序排好队，问有多少种排队方式可以依次顺利发售货品，而不出现无法找零的情况。15.学校某年级参加数学、物理、化学的培训，人数

32、分别是150、120、100 人。同时培训数学、物理两门课的学生有21 人；同时培训数学、化学的有16 人；同时培训物理、化学的有8 人；三科都培训的有5 人。问该年级共有多少人？（提示：对于此类问题，我们可以用一个图示法表示，从图中我们看出，总人数即为：ABCABBCCAABC 150 120 100211685330）排列组合考试题：A B C 文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S

33、10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码

34、:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7

35、O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H1

36、0 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y

37、9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T

38、7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z

39、5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10信息学奥林匹克竞赛辅导排列与组合基础知识第 5 页16.在 15 个同学中准备选出4 名同学参加国际信息学奥林匹克竞赛，其中学生甲和学生乙两人中，至少有一人必须被选中，问共有多少种选法？（提示：15 人中任意选出4 人的总方案为C（15，4），15 人中选 4 人并且甲和乙都不选的方案为C（13，4），这样答案为：C（15，4）C（13，4）17.用 A、B、C、D、E、F 六个字母进行排列，其字符排列中不出现“

40、ACE”或“DF”字串的排列方案有多少种？（提示：六个字母的总排列方案为P（6，6），又因为要求排列的字符串中不得出现“ACE”或“DF”字串，因此我们可以将“ACE”看作一个整体，排列方案为P（4，4），将“DF”看作一个整体，排列方案为P（5，5），“ACE”和“DF”同时出现的方案为P（3，3），所以答案为：P（6，6）P（4，4）P（5，5）P（3，3）；即 6！（4！5！）3！。）18.栈的计数。编号分别为1N（1=N=18）的 N 辆列车顺序进入一个栈式结构的站台（先进后出），试问这 N 辆列车开出车站的所有可能次序有多少种序列。（此题为NOIP 第九届普及组复赛试题第三题）（分析

41、：我们用1 表示进栈，0 表示出栈，考虑到列车必须先进栈再出栈，因此从左到右1 的个数总不少于0 的个数（即总是进栈的列车多于或等于出站的列车，否则无列车可以出栈），这样问题就转化为我们已经解决了的问题。答案为：C（2N，N）（N1）19.有一排格子排成一排，已知共有8 个格子。现有两个不同颜色的球要放在其中，要求两个球不能相邻，问共有多少种摆放方案。（提示：在所有的摆放方案中，减去两个球相邻的摆放方案，即将此二球看为一个整体，（注意此二球可以左右交换位值），因为有六个格子一样，最后需要除以66P。答案：8787662PPP 42 种）20.有一排格子排成一排，已知共有8 个格子。现有三个不同

42、颜色的球要放在其中，要求任意两个球不能相邻，问共有多少种摆放方案。（提示：为了方便理解说明，不妨将这三个不同颜色的球编号为1、2、3 号。所有的摆放方案为88P，减去任意两个球相邻的摆放方案，共有六种情况（即12、21、13、31、23、32），此时需要注意三个球相邻的情况，三个球相邻的情况有123、312、213、321、132、231 共六种情况，在减去任意两个球相邻的情况时，比如减去12 相邻的情况时，三个球相邻的情况123 和 312 同时被减去了，同理还有其它五种情况，说明三球相邻的情况各被多减了一次，所以最后需要加上三球相邻的情况。答案为：8768765566PPPP120 种）2

43、1.有一排格子排成一排，已知共有8 个格子。现有2 个红色球和3 个蓝色球要放在其中，要求如下：（1）每个格子最多摆放一个球；（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少空出一个格子。问共有多少种摆放方案。如下是其中一种摆放方案。红红蓝蓝蓝（提示：将每种颜色的球看作一个整体后方法同上。答案：5454332PPP 12 种）22.有一排格子排成一排，已知共有12 个格子。现有3 个红色球、2 个蓝色球和1 个黄色球要放在其中，要求如下：（1）每个格子最多摆放一个球；（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少空出一个格子。问共有多少种摆放方案。如下是其中一种摆放方

44、案。文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码

45、:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7

46、O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H1

47、0 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y

48、9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T

49、7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z

50、5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10文档编码:CV2P7O1W4H10 HV3Y9C3N5T7 ZM8Z5F2Y9S10信息学奥林匹克竞赛辅导排列与组合基础知识第 6 页红红红蓝蓝黄（提示：将每种颜色的球看作一个整体后方法同上。答案：9879876666PPPP 210 种）23.有