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

排列与组合基础知识

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

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

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

N ＝m 1＋m 2＋…＋m n 种不同的方法，这一原理叫做加法原理。

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

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

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

公式：阶乘公式!(1)(2)321n n n n =?-?-?? ，规定0！＝1；

全排列公式!n n P n = 选排列公式!(1)(2)(1)()!

m n n P n n n n m n m =---+=- 、m m m n n m P C P = 圆排列：n 个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：

!(1)!n n n =- 组合数公式(1)(2)(1)!!!()!

m m

n n m m P n n n n m n C P m m n m ---+===- 、规定01n C = m n m n n C C -=、11m m m n n n

C C C -+=+、0122n n n n n n C C C C ++++= ） 提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。

（2）书写方式：r n P 记为P （n,r ）

；r n C 记为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

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

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

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本书，问有多少种方法。 （提示：此题为组合问题，答案为355433!

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

（提示：此题属于圆排列问题，答案为（5－1）！＝24）

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

（提示：此题为排列问题。摆放方案总数为（2＋2＋3）！种，但是两个红球一样，所以要除以2！，同理两个蓝球，除以2！，三个黄球，除以3！，即摆放方案总数为(223)!2102!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三

类；对于第一类3、0、0、0的方法，共有44P 种方法，但是有3个0是一样的，所以应该除以33P ，

即第一类分法的方法数为4343/P P 种，同理，第二种分法的方法数为42

42/P P ，第三种分法的方法数为4343/P P ，所以总共的方法数为（4343/P P ＋4242/P P ＋4343/P P ）种。

解答（2）自行求解。

解答（3）：这一类问题，我们称为重复组合问题，其求解公式为C （n+r-1,r ）。请记住该公式即可。） 排列组合练习习题：

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

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

（提示：此题为组合问题。答案分别为：25710C ++、2225710C C C ++、222257105710()C C C C ++-++）

2. 把八个“车”放在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 ）点，

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

（方法一：从（1，1）点走到（N ，M ）点，无论如何走一共都要走（N －1）＋（M －1）步，其中N －1步向右走，M －1步向下走，因为只有两种走法，不妨用二进制表示走路方式，1表示向右走，0表示向下走。则可用一个长度为（N ＋M －2）的二进制串来表示走路方法，其中如果出现了N －1个1，则表示找到了一种路径。从而把题目转化为求长度为N ＋M －2的2进制串中有N －1个1的个数，即求组合数学公式C （N ＋M －2，N －1）

的值。

方法二：对本题稍加分析就能发现，要到达棋盘上的某个点，只能从该点的上边过来，或者从该

点的左边过来，根据加法原理，要到达该点的路径数目，就等于到达该点上点的路径与该点左点的路径数目之和，因此我们可以按照逐行递推的方法求出从起点到终点的路径数目。初始化，左上角第一个元素值为1，其它点的值为上点与左点的和。）

对于如右图的网格，用方法一的答案为C（4＋3，3）＝35；

用方法二逐行递推的方法得到网格上的数字，最后答案也为35。

比较两种方法，当数据较小时，采用公式一比较直接，但如果数据较大时，公式一的乘法运算量较大，这时可考虑用方法二逐行递推求得答案。

10.在上题中，若规定N

坐标(a,b)恒满足a

（测试数据：N＝4，M＝5；答案：）

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

个点的坐标由键盘输入。

（测试数据：N＝5，M＝4，X＝2，这2个障碍点坐标为（2,3）和（4,2）；答案：）

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

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人；

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

（提示：对于此类问题，我们可以用一个图示法表示，从图中我们看出，总人数即为：A＋B＋C－A∩B－B∩C－C∩A＋A∩B∩C＝150＋120＋100－21－16－8＋5＝330）

排列组合考试题：

A

B

C

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 六个字母进行排列，其字符排列中不出现“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. 栈的计数。编号分别为1～N （1<=N<=18）的N 辆列车顺序进入一个栈式结构的站台（先进后出），

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

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

（分析：我们用1表示进栈，0表示出栈，考虑到列车必须先进栈再出栈，因此从左到右1的个数总不少于0的个数（即总是进栈的列车多于或等于出站的列车，否则无列车可以出栈），这样问题就转化为我们已经解决了的问题。答案为：C （2N ，N ）／（N ＋1））

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

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

（提示：在所有的摆放方案中，减去两个球相邻的摆放方案，即将此二球看为一个整体，（注意此

二球可以左右交换位值），因为有六个格子一样，最后需要除以66

P 。答案：878

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

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

（提示：为了方便理解说明，不妨将这三个不同颜色的球编号为1、2、3号。所有的摆放方案为88P ，

减去任意两个球相邻的摆放方案，共有六种情况（即12、21、13、31、23、32），此时需要注意三个球相邻的情况，三个球相邻的情况有123、312、213、321、132、231共六种情况，在减去任意两个球相邻的情况时，比如减去12相邻的情况时，三个球相邻的情况123和312同时被减去了，同理还有其它五种情况，说明三球相邻的情况各被多减了一次，所以最后需要加上三球相邻的情况。答案为：8768765

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

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

（提示：将每种颜色的球看作一个整体后方法同上。答案：545433

2P P P -＝12种） 22. 有一排格子排成一排，已知共有12个格子。现有3个红色球、2个蓝色球和1个黄色球要放在其

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

（提示：将每种颜色的球看作一个整体后方法同上。答案：98798766

66P P P P -+＝210种） 23. 有一排格子排成一排，已知共有8个格子。现有两个相同的球要放在其中，要求两个球不能相邻，

问共有多少种摆放方案。

（提示：在19题的基础上，只是因为两个球相同而已，所以最后需除以22

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

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

（提示：方法同上题，因为三个球相同，故最后需除以33P

，答案：87687653

5366P P P P P -+?＝20种） 三、实力自测

(一)基本题

1、某公司内有副理5人，业务员30人，工人6人，现欲由副理、业务员、工人中各选一人组成考核委员会，则其选法共有多少种？ Ans: 900

2、书架上有不同的国文书7本，不同的英文书4本，不同的数学书5本，不同的会计书3本。今有一同学欲由书架上选取国文、英文、数学、会计书各一本，其取法有多少种？ Ans: 420

3、由甲村到乙村有5条路可通，若一人往返甲乙村，则有多少种不同走法？ Ans: 25

4、试求 ? Ans: 14

5、甲、乙、丙、丁四人排成一列，则其排法有多少种？ Ans: 24

6、试求 ？ Ans: 10

7、用1，2，3，4，5，6，7七个数字排成四位数，数字不可重复，共可排多少个？ Ans: 840

8、将三个相同的a，二个b，一个c排成一列，则排法共有多少种？Ans: 60

9、把五封信投入3个邮筒，方法共有几种？Ans: 243

10、某人有5种酒，4个不同的酒杯，每杯只许倒一种酒，则有倒法有多少种？Ans: 625

11、有三所学校同日招生，若规定每人祇可报考一个学校，则四个人报考之方法共有几种？Ans: 81

12、五对夫妇围一圆桌而坐，则全部的排法有多少种？Ans:9！

13、承上题，男女相间而坐的方法有多少种？Ans: 2880

14、承上题，夫妇相邻之坐法有多少种？Ans: 768

15、个不同的球，选4个串成一项圈之方法有有多少种？Ans: 105

16、颗不同的珠子，可串成多少种项圈？Ans:

17、若，则？Ans: 15

18、由8本书中任取3本，每次必含指定之一本在内，则方法有多少种？Ans: 21

19、平面上相异10点，任三点均不共线，共可决定几个三角形？Ans: 120

20、4个相同的球，赠予2位小朋友，则其法有多少种？Ans: 5

21、一学校有4个班级，选出7人组成委员会的方法有多少种？Ans: 120

22、方程式x+y+z=9有非负整数解及正整数解各共有多少个？Ans: 55,28

23、展开式中若欲求第11项，则r应取多少？Ans: 10

24、展开式中常数项为？Ans: 15

25、展开式中项之系数为？Ans: 80

(二)进阶题

1、一兔穴有进出口共4处，则由不同一口进出的方法有多少种？Ans: 12

2、某戏院有两个入口、三个出口，则进出戏院的方法有多少种？Ans: 6

3、展开式中共有多少项？Ans: 24

4、甲、乙、丙、丁、戊、己等六人排成一列，试求甲必排首，乙必排末的方法有多少种？Ans: 24

5、用0，1，2，3，4，5共六个数字，在数字不重复之下，可组成的六位数有几个？Ans: 600

6、7人排成一列，若其中有二人必相邻的排法有1440种，则此二人必不相邻的排法有多少种？

Ans: 3600

7、将5元硬币4个，1元硬币3个，分给10位儿童，每人至多一个硬币，则分法有多少种？Ans: 4200

8、三男四女排成一列，若首尾均须排男生，则其排法有多少种？Ans: 720

9、容许重复使用1，2，3，4可以作出三位数共有多少种？Ans: 64

10、容许重复使用0，1，2，3可以作出三位数共有多少种？Ans: 48

11、有渡船三只，每只可容纳6人，今有5人，要同时安全渡河，其过渡法有多少种？Ans: 243

12、试求由0，1，3，5，7五个数字，可作出多少个四位数？Ans: 500

13、一对主人夫妇邀宴四对夫妇，共围坐一圆桌，若其中一对林姓夫妇须相邻，而另一对陈姓夫妇不相邻，则其法有多少种？Ans: 60480

14、父母子女共6人围成一圆桌而坐，若父母须相对而坐，试求其坐法有多少种？Ans: 24

15、一对夫妇及三位子女共5人围圆桌而坐，则夫妇相邻的坐法有多少种？Ans: 12

16、若，则？Ans: 7

17、由6个英国人，5个美国人选出5人组成委员会，若委员会中至少有2个美国人，则选法有多少种？Ans: 381

18、承上题，若委员会中英国人、美国人至少各为二人，则选法有多少种？Ans: 350

19、6本相同的书，分给甲、乙、丙三人，每人至少得一本，共有几种分法？Ans: 10

20、x+y+z+w=12的正整数解共有几组？Ans: 165

21、将10个相同的水果，放入4个不同的箱子中，如果每个箱子至少放一个，试求共有多少可能的放法？Ans: 84

22、试求？Ans: 31

23、试求？Ans: 32

24、试求展开时的常数项。Ans: 70

25、若展开式中含有常数项，试求最小自然数n。Ans: 5

(三)挑战题

1、相同的原子笔6枝与相同的铅笔2枝，分给8个小孩，每小孩各得一枝，共有多少种分法？

Ans: 28

2、五男四女排列而坐，同性不得相邻，其排列方法有多少种？Ans: 2880

3、把“我爱人人，人人爱我”八字重新排列，其排法共有多少种？Ans: 420

4、由0、1、2、3、4五个数字，数字不可重复，可构成多少个三位数？Ans: 48

5、甲、乙、丙……等7人排成一列，若规定甲、乙、丙三人必须分离，试求排列的方法有多少种？

Ans: 1440

6、现从0、1、2、3、4、5、6等数字中，任取4个组成一个四位数（不得重复），试求可得多少不同的偶数？Ans: 420

7、设有渡船3只，每只可载5人，今有6人过渡，则安全过渡的方法有多少种？Ans: 726

8、设有渡船三只，每船可载5人，今有7人欲安全渡河，其法有多少种？Ans: 2142

9、有5个不同奖品，分给4位儿童，但是奖品可以同时给同一人，试问其中指定A 儿童至少得一件之分法有多少种？Ans: 781

10、有一对主人夫妇邀四对夫妇共围坐一圆桌进餐，试求男女相间而坐的坐法有多少？Ans: 2880

11、从6男5女中选取男女各3人组成3对拍档，每对均由1男1女组成，则3对拍文件的组合共有几种可能？Ans: 1200

12、将6件不同的玩具，分给3位儿童，每人至少一件，试求其分法有多少种？Ans: 540

13、欲将六位新生平均分发到甲、乙、丙三班，试求共有多少种分法？Ans: 90

14、体操委员会由10位女性委员与5位男性委员组成。委员会要由6位委员组团出国考察，如以性别作分层，并在各层依比例随机抽样，试问此考察团共有多少种组成方式？Ans: 2100

15、由12位立法委员中，任选5人组成一研究小组，试求下列情况之选法各有多少种？每次必含某一委员。每次必不含某一委员。Ans: 330,462

16、某次考试，规定由六题中选作四题，但前二题必须作答，试求选题的方法共有多少种？Ans: 6

17、试求正十二边形总共有几条对角线？Ans: 54

18、以五种不同的酒，倒入3个相同的酒杯，每杯只能倒一种酒的方法有多少种？Ans: 35

19、同时掷4粒相同的骰子，其可能的结果有多少种？Ans: 126

20、候选人4名，选举人18名，则无记名投票之情形有多少种？Ans: 1330

21.试求满足x+y+z≤9的正整数解共有多少组？Ans: 84

22、若a为实数，的展开式中之系数为80，则a值为? Ans: 2

23、若展开式中含有常数项，则最小自然数n为? Ans: 5

24、试求之值。Ans: 0

25、试求之值。Ans: 512

四、历届试题

1、男生8人，女生6人，若要选出两男两女组成一代表队，则共有几种组法？Ans: 420

2、某三位数其百位数字为偶数，个位数数字为奇数，这样的三位数共有多少个？Ans: 200

3、从集合中选取6个不同数字，其中至少有3个奇数的选法有几种？Ans:74

4、从跳棋中取出八个棋子，其中红色有4个，黄色有2个，绿色有2个。将8个棋子排成一列，共有多少种不同的排法？Ans:420Ans: (B)

5、甲、乙、丙、丁、戊五人排成一列，且甲、乙、丙三人必须相连的排法有多少种？Ans:36

6、设代表自n个相异对象中，每次不可重复的取m件为一组的组合数，则之值为：

(A)45 (B)90 (C) (D) (E) 。Ans: (B)

7、依下列个条件将甲、乙、丙、丁、戊五人排成一列，何种条件下的排法最多？Ans:乙不排首位。

8、由0,1,2,3,4,5,6中任取相异三数作成三位数，则不小于340的有多少个？Ans:105

9、现从0,1,2,3,4,5,6等数字中，任取4个组成一个四位数(不得重复取)，则可得几个不同偶数？Ans:420

10、用1,2,3,4四个数字作成四位数，数字不重复，求这所有四位数之和。Ans:66660

11、将六位数字223345的各数字任意排列，若其中的数字2须相邻，但数字3不得相邻，试问可得多少不同的六位数？Ans: 36

12、若，则共有几组整数解？

(A) (B) (C) (D) 。Ans: (A)

13、将〝banana〞一字中，任取3个字母来排列，共有多少种方法？Ans:19

14、n为自然数且，则n=？Ans:3

15、用1,2,3,4等四个数字排成一四位数(数字不可重复)，则全部四位数之总和为？Ans:66660

16、欲将六位新生平均分发到甲、乙、丙三班，则共有几种方法？Ans:90

17、若平面上有八点构成一八边型，则其对角线共有多少条？Ans:20

18、将3,3,4,4,9五个数排成五位数，则其排法共有多少种？Ans:30

19、将6件相同物品，分给甲、乙、丙三人，每人至少得一件之分法共有多少种？Ans:10

20、假设在10件产品中，有3件是不良品，由产品中随机抽取5件，其中至少有2件不良品的取法共有：Ans:126种

21、将MECERRED一字的字母全取排列，排法有几种？Ans: 3360

22、设a,b,c均为正整数，则方程式共有几组解？Ans:36

23、把3本不同的国文课本，4本不同的英文课本和1本数学课本排成一列，又国文课本必须排在一起，且英文课本也必须排在一起，则共有多少种排法？Ans: 864

24、从7名男人，6名女人中选取4人，其中至少2名为男人，1名为女人，试问共有多少选法？

Ans:525。

排列组合知识点总结+典型例题及答案解析

排列组合知识点总结+典型例题及答案解析 一．基本原理 1．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。 注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。 二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -=+---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!! !! 10 =n C 规定： 组合数性质： .2 n n n n n m n m n m n m n n m n C C C C C C C C 21011 =+++=+=+--…… ，， ①；②；③；④ 111 12111212211 r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-++++ +=+++ +=++ +=注： 若1 2 m m 1212m =m m +m n n n C C ==则或 四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。

高中排列组合基础题

排列、组合问题基本题型及解法 同学们在学习排列、组合的过程中，总觉得抽象，解法灵活，不容易掌握.然而排列、组合问题又是历年高考必考的题目.本文将总结常见的类型及相应的解法. 一、相邻问题“捆绑法” 将必须相邻的元素“捆绑”在一起，当作一个元素进行排列. 例1 甲、乙、丙、丁四人并排站成一排，如果甲、乙必须站在一起，不同的排法共有几种？ 分析：先把甲、乙当作一个人，相当于三个人全排列，有33A ＝6种，然后再将甲、乙二人全排列有22A ＝2种，所以共有6×2＝12种排法. 二、不相邻问题“插空法” 该问题可先把无位置要求的元素全排列，再把规定不相邻的元素插入已排列好的元素形成的空位中（注意两端）. 例2 7个同学并排站成一排，其中只有A 、B 是女同学，如果要求A 、B 不相邻，且不站在两端，不同的排法有多少种？. 分析：先将其余5个同学先全排列，排列故是55A ＝120.再把A 、B 插入五个人组成的四个空位（不包括两端）中，（如图0×0×0×0×0“×”表示空位，“0”表示5个同学）有24A ＝2 种方法.则共有52 54A A ＝440种排法. 三、定位问题“优先法” 指定某些元素必须排（或不排）在某位置，可优先排这个元素，后排其他元素. 例3 6个好友其中只有一个女的，为了照像留念，若女的不站在两端，则不同的排法有 种. 分析：优先排女的（元素优先）.在中间四个位置上选一个，有14A 种排法.然后将其余5个 排在余下的5个位置上，有55A 种方法.则共15 45A A ＝480种排法.还可以优先排两端 （位置优先）. 四、同元问题“隔板法” 例4 10本完全相同的书，分给4个同学，每个同学至少要有一本书，共有多少种分法？ 分析：在排列成一列的10本书之间，有九个空位插入三块“隔板”.如图： ×× × ××× ×××× 一种插法对应于一种分法，则共有39C ＝84种分法. 五、先分组后排列 对于元素较多，情形较复杂的问题，可根据结果要求，先分为不同类型的几组，然后对每一组分别进行排列，最后求和. 例5 由数字0，1，2，3，4，5组成无重复数字的六位数，其中个位数字小于十位数字的共有（ ） （A ）210个 （B ）300个 （C ）464个 （D ）600个 分析：由题意知，个位数字只能是0，1，2，3，4共5种类型，每一种类型分别有55A 个、113433A A A 个、113333A A A 个、113233A A A 个、13 33A A 个，合计300个，所以选B 例6 用0，1，2，3，…，9这十个数字组成五位数，其中含有三个奇数数字与两个偶数数字的五位数有多少个? 【解法1】考虑0的特殊要求，如果对0不加限制，应有325555C C A 种， 其中0居首位的有314 544C C A 种，故符合条件的五位数共有325314 555544C C A C C A ＝11040个. 【解法2】按元素分类：奇数字有1，3，5，7，9；偶数字有0，2，4，6，8. 把从五个偶数中任取两个的组合分成两类：①不含0的；②含0的. ①不含0的：由三个奇数字和两个偶数字组成的五位数有325 545C C A 个； ②含0的，这时0只能排在除首位以外的四个数位上，有14A 种排法， 再选三个奇数数与一个偶数数字全排放在其他数位上，共有3141 5444C C A A 种排法. 综合①和②，由分类计数原理，符合条件的五位数共有325545C C A ＋3141 5444C C A A ＝11040个. 例8 由数字1，2，3，4，5可以组成多少个无重复数字，比20000大，且百位数字不是3

排列组合基本题型方法

排列组合方法汇总 排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有13C 然后排首位共有14C 最后排其它位置共有3 4A 由分步计数原理得 113434 288 C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有522522480 A A A =种不同的排 法 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55A 种，第二步将4舞蹈插入第一步排好的6个元素 中间包含首尾两个空位共有种4 6 A 不同的方法,由分步计数原理,节目的不同顺序共有5456A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 4 4 3

排列组合知识点汇总及典型例题(全)

排列组合知识点汇总及典型例题(全)

一．基本原理 1．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。 注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。 二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -= +---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!!!! 10 =n C 规定： 组合数性质：.2 n n n n n m n m n m n m n n m n C C C C C C C C 21011=+++=+=+--……，， ①；②；③；④ 111 12111212211r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-+++++=+++ +=++ +=注： 若1 2 m m 1212m =m m +m n n n C C ==则或 四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。 2．解排列、组合题的基本策略 （1）两种思路：①直接法； ②间接法：对有限制条件的问题，先从总体考虑，再把不符合条件的所有情况去掉。这是解决排列组合应用题时一种常用的解题方法。 （2）分类处理：当问题总体不好解决时，常分成若干类，再由分类计数原理得出结论。注意：分类不重复不遗漏。即：每两类的交集为空集， 所有各类的并集为全集。 （3）分步处理：与分类处理类似，某些问题总体不好解决时，常常分成若干步，再由分步计数原理解决。在处理排列组合问题时，常常既要分 类，又要分步。其原则是先分类，后分步。 （43．排列应用题： （1）穷举法（列举法）：将所有满足题设条件的排列与组合逐一列举出来； (2)、特殊元素优先考虑、特殊位置优先考虑； （3）．相邻问题：捆邦法： 对于某些元素要求相邻的排列问题，先将相邻接的元素“捆绑”起来，看作一“大”元素与其余元素排列，然后再对相邻元素内部进行排列。 （4）、全不相邻问题，插空法：某些元素不能相邻或某些元素要在某特殊位置时可采用插空法.即先安排好没有限制条件的元素，然后再将不相 邻接元素在已排好的元素之间及两端的空隙之间插入。 （5）、顺序一定，除法处理。先排后除或先定后插 解法一：对于某几个元素按一定的顺序排列问题，可先把这几个元素与其他元素一同进行全排列，然后用总的排列数除于这几个元素的全排列数。即先全排，再除以定序元素的全排列。 解法二：在总位置中选出定序元素的位置不参加排列，先对其他元素进行排列，剩余的几个位置放定序的元素，若定序元素要求从左到右或从右到左排列，则只有1种排法；若不要求，则有2种排法； （6）“小团体”排列问题——采用先整体后局部策略 对于某些排列问题中的某些元素要求组成“小团体”时，可先将“小团体”看作一个元素与其余元素排列，最后再进行“小团体”内部的排列。 （7）分排问题用“直排法”把元素排成几排的问题，可归纳为一排考虑，再分段处理。 （8）．数字问题（组成无重复数字的整数） ① 能被2整除的数的特征：末位数是偶数；不能被2整除的数的特征：末位数是奇数。②能被3整除的数的特征：各位数字之和是3的倍数； ③能被9整除的数的特征：各位数字之和是9的倍数④能被4整除的数的特征：末两位是4的倍数。 ⑤能被5整除的数的特征：末位数是0或5。 ⑥能被25整除的数的特征：末两位数是25，50，75。 ⑦能被6整除的数的特征：各位数字之和是3的倍数的偶数。 4．组合应用题：（1）.“至少”“至多”问题用间接排除法或分类法: （2）． “含”与“不含” 用间接排除法或分类法: 3．分组问题： 均匀分组：分步取，得组合数相乘，再除以组数的阶乘。即除法处理。 非均匀分组：分步取，得组合数相乘。即组合处理。 混合分组：分步取，得组合数相乘，再除以均匀分组的组数的阶乘。 4．分配问题： 定额分配：（指定到具体位置）即固定位置固定人数，分步取，得组合数相乘。

2020年高考理科数学易错题《排列组合》题型归纳与训练

2020年高考理科数学《排列组合》题型归纳与训练 【题型归纳】 题型一 计数原理的基本应用 例1 某校开设A 类选修课2门，B 类选修课3门，一位同学从中选3门．若要求两类课程中各至少选一门，则不同的选法共有 A ．3种 B ．6种 C ．9种 D ．18种 【答案】 C . 【解析】 可分以下2种情况：①A 类选修课选1门，B 类选修课选2门，有 62312=?C C 种不同的选法；②A 类选修课选2门，B 类选修课选1门，有31322=?C C 种不同的选法．所以根据分类计数原理知不同的选法共有6+3=9种．故要求两类课程中各至少选一门，则不同的选法共有9种．故选：C 【易错点】注意先分类再分步 【思维点拨】两类课程中各至少选一门，包含两种情况：A 类选修课选1门，B 类选修课选2门；A 类选修课选2门，B 类选修课选1门，写出组合数，根据分类计数原理得到结果. 题型二 特殊元素以及特殊位置 例 1 将F E D C B A ,,,,,六个字母排成一排，且B A ,均在C 的同侧，则不同的排法有（ ）种.（用数字作答） 【答案】 480 【解析】考虑到C B A ,,要求有顺序地排列，所以将这三个字母当作特殊元素对待。先排F E D ,,三个字母，有12036 =A 种排法；再考虑C B A ,,的情况：C 在最左端有2种排法，最右端也是2种排法，所以答案是4804120=?种. 【易错点】注意特殊元素的考虑 【思维点拨】对于特殊元素与特殊位置的考量，需要瞻前顾后，分析清楚情况，做到“不重复不遗漏”；如果情况过于复杂，可以考虑列举法，虽然形式上更细碎一些，但是情况分的越多越细微，每种情况越简单，准确度就越高. 题型三 捆绑型问题以及不相邻问题 例1 由1，2，3，4，5，6组成没有重复数字且1，3都不与5相邻的六位偶数的个数是（ ）个.

信息学奥赛基础知识习题(答案版)

信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU (B)固 件 (C)计算机系统 (D)微处 理机 2．硬件系统是指 D 。 (A)控制器，器运算 (B)存储器，控制器 (C)接口电路，I/O设备 (D)包括(A)、(B)、(C) 3. 计算机软件系统包括 B 。 A) 操作系统、网络软件 B) 系统软件、应用软件 C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。 (A)高级语言 (B)符号语言 (C)汇编语言 (D)机器语言 5．硬盘工作时应特别注意避免 B 。 (A)噪声 (B)震动 (C)潮 湿 (D)日光 6．计算机中数据的表示形式是 C 。 (A)八进制 (B)十进制 (C)二进 制 (D)十六进制

7．下列四个不同数制表示的数中，数值最大的是 A 。 (A)二进制数11011101 (B)八进制数334 (C)十进制数219 (D)十六进制 数DA 8．Windows 9x操作系统是一个 A 。 (A)单用户多任务操作系统 (B)单用户单任务操 作系统 (C)多用户单任务操作系统 (D)多用户多任务操 作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11. 在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D） 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。 （A）采用超大规模集成电路（B）采用CPU作为中央核心部件 （C）采用操作系统（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 (A)用鼠标左键单击该图标 (B)用鼠标右键单击该 图标 (C)用鼠标左键双击该图标 (D)用鼠标右键双击该 图标

(完整版)排列组合知识点与方法归纳

排列组合知识点与方法归纳 一、知识要点 1.分类计数原理与分步计算原理 （1）分类计算原理（加法原理）： 完成一件事，有n类办法，在第一类办法中有m1种不同的方法，在第二类办 法中有m2种不同的方法，……，在第n类办法中有m n种不同的方法，那么完 成这件事共有N= m1+ m2+…+ m n种不同的方法。 （2）分步计数原理（乘法原理）： 完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有 m2种不同的方法，……，做第n步有m n种不同的方法，那么完成这件事共有 N= m1× m2×…× m n种不同的方法。 2.排列 （1）定义 从n个不同元素中取出m（）个元素的所有排列的个数，叫做从n个不 同元素中取出m个元素的排列数，记为 . （2）排列数的公式与性质 a)排列数的公式： =n（n-1）（n-2）…（n-m+1）= 特例：当m=n时， =n！=n（n-1）（n-2）…×3×2×1规定：0！ =1 b)排列数的性质： （Ⅰ） =（Ⅱ） （Ⅲ） 3.组合 （1）定义

a)从n个不同元素中取出个元素并成一组，叫做从n个不同元素中取 出m个元素的一个组合 b)从n个不同元素中取出个元素的所有组合的个数，叫做从n个不同 元素中取出m个元素的组合数，用符号表示。 （2）组合数的公式与性质 a)组合数公式：（乘积表示） （阶乘表示） 特例： b)组合数的主要性质： （Ⅰ）（Ⅱ） 4.排列组合的区别与联系 （1）排列与组合的区别在于组合仅与选取的元素有关，而排列不仅与选取的元素有关，而且还与取出元素的顺序有关。因此，所给问题是否与取出元素的顺序有关，是判断这一问题是排列问题还是组合问题的理论依据。 （2）注意到获得（一个）排列历经“获得（一个）组合”和“对取出元素作全排列”两个步骤，故得排列数与组合数之间的关系： 二、经典例题 例1、某人计划使用不超过500元的资金购买单价分别为60、70元的单片软件和盒装磁盘，要求软件至少买3片，磁盘至少买2盒，则不同的选购方式是（） A .5种 B.6种 C. 7种 D. 8种 解：注意到购买3片软件和2盒磁盘花去320元，所以，这里只讨论剩下的180元如何使用，可从购买软件的情形入手分类讨论：第一类，再买3片软件，不买磁盘，只有1种方法；第二类，再买2片软件，不买磁盘，只有1种方法； 第三类，再买1片软件，再买1盒磁盘或不买磁盘，有2种方法；第四类，不买软件，再买2盒磁盘、1盒磁盘或不买磁盘，有3种方法；于是由分类计数原理可知，共有

排列组合题型总结

排列组合题型总结 排列组合问题千变万化，解法灵活，条件隐晦，思维抽象，难以找到解题的突破口。因而在求解排列组合应用题时，除做到：排列组合分清，加乘原理辩明，避免重复遗漏外，还应注意积累排列组合问题得以快速准确求解。 一．直接法、 1． 特殊元素法 例1用1，2，3，4，5，6这6个数字组成无重复的四位数，试求满足下列条件的四位数各有多少个 （1）数字1不排在个位和千位 （2）数字1不在个位，数字6不在千位。 分析：（1）个位和千位有5个数字可供选择25A ，其余2位有四个可供选择24A ，由乘法原理： 25A 24A =240 2．特殊位置法 （2）当1在千位时余下三位有35A =60，1不在千位时，千位有14A 种选法，个位有14A 种，余下的有24A ， 共有14A 1 4A 24A =192所以总共有192+60=252 二．间接法当直接法求解类别比较大时，应采用间接法。如上例中（2）可用间接法2435462A A A +-=252 例2 有五张卡片，它的正反面分别写0与1，2与3，4与5，6与7，8与9，将它们任意三张并排放在一起组成三位数，共可组成多少个不同的三维书？ 分析：此例正面求解需考虑0与1卡片用与不用，且用此卡片又分使用0与使用1，类别较复杂，因 而可使用间接计算：任取三张卡片可以组成不同的三位数333352A C ??个，其中0在百位的有 2242?C ?22A 个，这是不合题意的。故共可组成不同的三位数333352A C ??-2242?C ?22A =432 （个） 三．插空法 当需排元素中有不能相邻的元素时，宜用插空法。 例3 在一个含有8个节目的节目单中，临时插入两个歌唱节目，且保持原节目顺序，有多少中插入方 法？ 分析：原有的8个节目中含有9个空档，插入一个节目后，空档变为10个，故有11019A A ?=100中插 入方法。 四．捆绑法 当需排元素中有必须相邻的元素时，宜用捆绑法。 例4 4名男生和3名女生共坐一排，男生必须排在一起的坐法有多少种？ 分析：先将男生捆绑在一起看成一个大元素与女生全排列有44A 种排法，而男生之间又有44A 种排法，又乘法原理满足条件的排法有：44A ×4 4A =576 练习1．四个不同的小球全部放入三个不同的盒子中，若使每个盒子不空，则不同的放法有 种（3324A C ） 2． 某市植物园要在30天内接待20所学校的学生参观，但每天只能安排一所学校，其中有一所学校

信息学奥赛基础知识提纲

信息学奥赛基础知识提纲 （2014年9月） 1 计算机系统 1－1概述 一个完整的计算机系统包括硬件系统和软件系统两大部分，必须具有五大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能。它的工作特点是：运算速度快、运算精度高、记忆能力强、通用性广、自动运算。 计算机按照规模可分为：巨型机、大型机、中型机、小型机、微型机、单片机等几种类型。根据用途不同分为通用机和专用机。 硬件指的是计算机的设备实体；软件通常泛指各类程序和文件。软硬件的关系：硬件是软件的基础。软件是硬件的扩充与完善。硬件与软件在逻辑上是等价的。 1946年，世界上第一台计算机诞生于宾夕法尼亚大学，称为ENIAC 。 1949年,第一台存储计算机EDSAC,英国剑桥大学威尔克斯（Wilkes ）设计和制造的。 1951年，第一台商用计算机是UNIVAC 。 1－2 硬件系统 1－2－1 冯·诺伊曼（J.von Neumann ）机：美籍匈牙利数学家 现代计算机的基本结构被称为冯·诺伊曼结构。它的主要特点是储存程序的概念： （1） 采用二进制形式表示数据和指令。 （2） 将程序（包括操作指令和操作数）事先存入主存储器中，使计算机在工作时能够自 动高速地从存储器中取出指令加以执行。 （3） 由运算器、存储器、控制器、输入设备、输出设备五大基础部件组成计算机系统。 冯·诺伊曼机 运 算 器存 储 器 输出设备 输入设备 控 制 器控 制 台 控制信号请 求 信 号 请 求 信 号 控制信号结 果 程序 反馈信息 操作指令 地址 指令

1－2－2 计算机的总线结构 计算机的各个部件需要以某种方式互联，进行数据交换。最常见的互联结构就是总线互联结构和多总线互联结构。总线是一种连接多种设备的信息传递通道，实际上是一组信号线。 典型的计算机总线结构由内部总线和系统总线组成。 （1） 内部总线：用于连接CPU 内部的各个模块。 （2） 系统总线：又称外部总线，用于连接CPU 、存储器和输入输出设备。系统总线的信 号线分为三类：数据线、地址线和控制线。 数据线（Data Bus ）：数据总线的宽度就是指组成数据总线的信号线的数目，它决定了在该总线上一次可以传送的二进制位数。 地址线（Address Bus ）：用以传递地址信息，来指示数据总线上的数据来源和去向。地址线的数目决定了能够访问空间的大小。 控制线（Control Bus ）：用来控制数据总线和地址总线。 某SRAM 芯片，其存储容量为64K*16位，则该芯片的地址线数目和数据线的数目？ 1－2－3 中央处理器（Central Processor Unit ） 1、CPU 包含了冯机五大部件中的运算器（即加法器）和控制器。 运算器：对信息加工和处理的部件，主要完成各种算术运算和逻辑运算。 控制器：通过读取各种指令，并进行翻译、分析，而后对各部件作出相应的控制。 2、CPU 主要由三大部分组成：寄存器组、算术逻辑单元（ALU ）和控制单元（控制器）。 寄存器组：分为通用寄存器（通用寄存器、数据寄存器、地址寄存器、标志寄存器）和状态控制寄存器（程序计数器PC 、指令寄存器IR 、存储器地址寄存器MAR 、存储器缓冲寄存器MBR ）以及程序状态字PSW 。 算术逻辑单元ALU ： 寄存器、存储器、I/O 设备把待处理的数据输入到ALU 。 控制单元：控制器的基本功能就是时序控制和执行控制。根据当前运行的程序，控 制器使CPU 按一定的时序关系执行一序列 的微操作从而完成程序。 时钟信号：控制器根据时钟电路产生的时钟信号进行定时，以控制各种操作按指定的时序进行。计算机的基本功能是执行程序，而程序由一连串的指令组成；计算机的执行过程由一连串的指令周期组成，每一指 令周期完成一条指令。这些指令周期又可进一步细分为更小的单元，直到微操作uop-----CPU 完成的基本的原子操作。 时钟脉冲发生器的晶振频率成为机器的主频，它产生的时钟脉冲信号是整个机器的时间基准，其周期T 称为该计算机的时钟周期。 完成一个微操作的时间就称为CPU 周期（机器周期）。执行一条机器指令所需的时间称为一个指令周期。 3、指令系统（精简指令系统）：操作类指令和控制类指令 一条指令：操作码 + 地址码 一条机器指令的执行：取指令――分析指令――执行指令 4、CPU 的主要指标有： 字长：CPU 一次所能处理的二进制位数。它决定着寄存器、加法器、数据总线等的位数。主频：计算机的时钟频率。（即内频）单位：MHz 或GHz 。 运算速度：CPU 每秒钟能完成的指令数MIPS 。运算速度=1÷ 执行一条机器指令所需的时间

高中数学排列组合公式大全_高中数学排列组合重点知识

高中数学排列组合公式大全_高中数学排列组合重点知识 1.排列及计算公式 从n个不同元素中，任取mm≤n个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出mm≤n个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 pn,m表示. pn,m=nn-1n-2……n-m+1= n!/n-m!规定0!=1. 2.组合及计算公式 从n个不同元素中，任取mm≤n个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出mm≤n个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号 cn,m 表示. cn,m=pn,m/m!=n!/n-m!*m!;cn,m=cn,n-m; 3.其他排列与组合公式 从n个元素中取出r个元素的循环排列数=pn,r/r=n!/rn-r!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/n1!*n2!*...*nk!. k类元素,每类的个数无限,从中取出m个元素的组合数为cm+k-1,m. 排列Pnmn为下标，m为上标 Pnm=n×n-1....n-m+1;Pnm=n!/n-m!注：!是阶乘符号;Pnn两个n分别为上标和下标=n!;0!=1;Pn1n为下标1为上标=n 组合Cnmn为下标，m为上标 Cnm=Pnm/Pmm ;Cnm=n!/m!n-m!;Cnn两个n分别为上标和下标 =1 ;Cn1n为下标1为上标=n;Cnm=Cnn-m 加法乘法两原理，贯穿始终的法则。与序无关是组合，要求有序是排列。 两个公式两性质，两种思想和方法。归纳出排列组合，应用问题须转化。 排列组合在一起，先选后排是常理。特殊元素和位置，首先注意多考虑。

排列组合基本知识

有关排列组合的基本知识 排列与元素的顺序有关，组合与顺序无关．如231与213是两个排列，2＋3＋1的和与2＋1＋3的和是一个组合． (一)两个基本原理是排列和组合的基础 (1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N＝m1＋m2＋m3＋…＋mn种不同方法． (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×m3×…×mn种不同的方法． 这里要注意区分两个原理，要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加法原理；做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理． 这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来． (二)排列和排列数 (1)排列：从n个不同元素中，任取m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列． 从排列的意义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法． (2)排列数公式：从n个不同元素中取出m(m≤n)个元素的所有排列,当m＝n时，为全排列Pnn=n(n－1)(n－1)…3·2·1＝n！

(三)组合和组合数 (1)组合：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合． 从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合． (2)组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个 这里要注意排列和组合的区别和联系，从n个不同元素中，任取m(m≤n)个元素，“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的． 一、排列组合部分是中学数学中的难点之一，原因在于 (1)从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽象思维能力 (2)限制条件有时比较隐晦，需要我们对问题中的关键性词(特别是逻辑关联词和量词)准确理解； (3)计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大； (4)计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。 二、两个基本计数原理及应用 (1)加法原理和分类计数法 1．加法原理 2．加法原理的集合形式 3．分类的要求 每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)

排列组合常见题型及解答

排列组合常见题型 一．可重复的排列求幂法：重复排列问题要区分两类元素：一类可以重复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，则通过“住店法”可顺利解题，在这类问题使用住店处理的策略中，关键是在正确判断哪个是底数，哪个是指数 【例1】（1）有4名学生报名参加数学、物理、化学竞赛，每人限报一科，有多少种不同的报名方法？ （2）有4名学生参加争夺数学、物理、化学竞赛冠军，有多少种不同的结果？ （3）将3封不同的信投入4个不同的邮筒，则有多少种不同投法？ 【解析】：（1）43（2）34（3）34 【例2】把6名实习生分配到7个车间实习共有多少种不同方法？ 【解析】：完成此事共分6步，第一步；将第一名实习生分配到车间有7种不同方案， 第二步：将第二名实习生分配到车间也有7种不同方案，依次类推，由分步计数原理知共有67种不同方案. 【例3】 8名同学争夺3项冠军，获得冠军的可能性有（）A、38 B、83 C、 3 8 A D、 3 8 C 【解析】：冠军不能重复，但同一个学生可获得多项冠军，把8名学生看作8家“店”，3项冠军看作3个“客”，他们都可能住进任意一家“店”，每个“客”有8种可能，因此共有38种 不同的结果。所以选A 二．相邻问题捆绑法：题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列. 【例1】A,B,C,D,E五人并排站成一排，如果A,B必须相邻且B在A的右边，那么不同的排

法种数有 【解析】：把A,B 视为一人，且B 固定在A 的右边，则本题相当于4人的全排列，4424A =种 【例2】（2009四川卷理）3位男生和3位女生共6位同学站成一排，若男生甲不站两端，3位女生中有且只有两位女生相邻，则不同排法的种数是（ ） A. 360 B. 188 C. 216 D. 96 【解析】： 间接法 6位同学站成一排，3位女生中有且只有两位女生相邻的排法有，22223242C A A A =432，其中男生甲站两端的有1222223232A C A A A =144，符合条件的排法故共有288 三．相离问题插空法 ：元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 【例1】七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是 【解析】：除甲乙外，其余5个排列数为55A 种，再用甲乙去插6个空位有26A 种，不同的排 法数是52563600A A = 【例2】 书架上某层有6本书，新买3本插进去，要保持原有6本书的顺序，有 种不同的插法（数字作答） 【解析】： 1 11789A A A =504 【例3】 高三（一）班学要安排毕业晚会的4各音乐节目，2个舞蹈节目和1个曲艺节目的演出顺序，要求两个舞蹈节目不连排，则不同排法的种数是 【解析】：不同排法的种数为5256A A ＝3600 【例4】 某工程队有6项工程需要单独完成，其中工程乙必须在工程甲完成后才能进行，工程丙必须在工程乙完成后才能进行，有工程丁必须在工程丙完成后立即进行。那么安排这6项工程的不同排法种数是 【解析】：依题，只需将剩余两个工程插在由甲、乙、丙、丁四个工程形成的5个空中，可得有25A ＝20种不同排法。

信息学奥赛一本通题解目录-信息学奥赛取消

信息学奥赛一本通题解目录:信息学奥赛取消 第1章 数论1．1 整除1．2 同余1．3 最大公约数1．3．1 辗转相除法1．3．2 进制算法1．3．3 最小公倍数1．3．4 扩展欧几里得算法1．3．5 求解线性同余方程1．4 逆元1．5 中国剩余定理1．6 斐波那契数1．7 卡特兰数1．8 素数1．8．1 素数的判定1．8．2 素数的相关定理1．8．3 Miller-Rabin素数测试1．8．4 欧拉定理1．8．5 PollardRho算法求大数因子1．9

Baby-Step-Giant-Step及扩展算法1．10 欧拉函数的线性筛法1．11 本章习题第2章群论2．1 置换2．1．1 群的定义2．1．2 群的运算2．1．3 置换2．1．4 置换群2．2 拟阵2．2．1 拟阵的概念2．2．2 拟阵上的最优化问题2．3 Burnside引理2．4 Polya定理2．5 本章习题第3章组合数学3．1 计数原理3．2 稳定婚姻问题3．3 组合问题分类3．3．1 存在性问题3．3．2 计数性问题3．3．3 构造性问题3．3．4 最优化问题3．4 排列3．4．1

选排列3．4．2 错位排列3．4．3 圆排列3．5 组合3．6 母函数3．6．1 普通型母函数3．6．2 指数型母函数3．7 莫比乌斯反演3．8 Lucas定理3．9 本章习题第4章概率4．1 事与概率4．2 古典概率4．3 数学期望4．4 随机算法4．5 概率函数的收敛性4．6 本章习题第5章计算几何5．1 解析几何初步5．1．1 平面直角坐标系5．1．2 点5．1．3 直线5．1．4 线段5．1．5 多边形5．1．6

两个计数原理与排列组合知识点及例题

两个计数原理与排列组合知识点及例题两个计数原理内容 1、分类计数原理： 完成一件事，有n类办法，在第1类办法中有m1种不同的方法，在第2类办法中有m2种不同的方法……在第n类办法中有m n种不同的方法，那么完成这件事共有N=m1 +m2 +……+m n种不同的方法. 2、分步计数原理： 完成一件事，需要分n个步骤，做第1步骤有m1种不同的方法，做第2步骤有m2种不同的方法……做第n步骤有m n种不同的方法，那么完成这件事共有N=m1×m2×……×m n种不同的方法. 例题分析 例1 某学校食堂备有5种素菜、3种荤菜、2种汤。现要配成一荤一素一汤的套餐。问可以配制出多少种不同的品种？ 分析：1、完成的这件事是什么？ 2、如何完成这件事？（配一个荤菜、配一个素菜、配一汤） 3、它们属于分类还是分步？（是否独立完成） 4、运用哪个计数原理？ 5、进行计算. 解：属于分步：第一步配一个荤菜有3种选择 第二步配一个素菜有5种选择 第三步配一个汤有2种选择 共有N=3×5×2=30（种） 例2 有一个书架共有2层，上层放有5本不同的数学书，下层放有4本不同的语文书。 （1）从书架上任取一本书，有多少种不同的取法？ （2）从书架上任取一本数学书和一本语文书，有多少种不同的取法？ （1）分析：1、完成的这件事是什么？ 2、如何完成这件事？ 3、它们属于分类还是分步？（是否独立完成） 4、运用哪个计数原理？ 5、进行计算。 解：属于分类：第一类从上层取一本书有5种选择 第二类从下层取一本书有4种选择 共有N=5+4=9（种） （2）分析：1、完成的这件事是什么？ 2、如何完成这件事？ 3、它们属于分类还是分步？（是否独立完成） 4、运用哪个计数原理？ 5、进行计算. 解：属于分步：第一步从上层取一本书有5种选择 第二步从下层取一本书有4种选择 共有N=5×4=20（种） 例3、有1、2、3、4、5五个数字. （1）可以组成多少个不同的三位数？ （2）可以组成多少个无重复数字的三位数？ （3）可以组成多少个无重复数字的偶数的三位数？ （1）分析： 1、完成的这件事是什么？ 2、如何完成这件事？（配百位数、配十位数、配个位数） 3、它们属于分类还是分步？（是否独立完成） 4、运用哪个计数原理？ 5、进行计算. 略解：N=5×5×5=125（个） 【例题解析】 1、某人有4条不同颜色的领带和6件不同款式的衬衣，问可以有多少种不同的搭配方法？

排列组合的基本理论和公式

排列组合的基本理论和公式 排列与元素的顺序有关，组合与顺序无关．如231与213是两个排列，2＋3＋1的和与2＋1＋3的和是一个组合． (一)两个基本原理是排列和组合的基础 (1)加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N＝m1＋m2＋m3＋…＋mn种不同方法． (2)乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×m3×…×mn种不同的方法．这里要注意区分两个原理，要做一件事，完成它若是有n类办法，是分类问题，第一类中的方法都是独立的，因此用加法原理；做一件事，需要分n个步骤，步与步之间是连续的，只有将分成的若干个互相联系的步骤，依次相继完成，这件事才算完成，因此用乘法原理． 这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来． (二)排列和排列数 (1)排列：从n个不同元素中，任取m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列．从排列的意义可知，如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同，这就告诉了我们如何判断两个排列是否相同的方法． (2)排列数公式：从n个不同元素中取出m(m≤n)个元素的所有排列 当m＝n时，为全排列Pnn=n(n－1)(n－2)…3·2·1＝n！ (三)组合和组合数 (1)组合：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n 个不同元素中取出m个元素的一个组合． 从组合的定义知，如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同时，才是不同的组合． (2)组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个

完整版排列组合题型归纳

排列组合难题二十一种方法 排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。 教学目标 1. 进一步理解和应用分步计数原理和分类计数原理。 2. 掌握解决排列组合问题的常用策略；能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3. 学会应用数学思想和方法解决排列组合问题. 复习巩固 1. 分类计数原理（加法原理） 完成一件事，有n类办法，在第1类办法中有m1种不同的方法，在第2类办法中有 m2种不同的方法，…，在第n类办法中有m n种不同的方法，那么完成这件事共有： N mi m2 L m n 种不同的方法. 2. 分步计数原理（乘法原理） 完成一件事，需要分成n个步骤，做第1步有口种不同的方法，做第2步有m2种不同的方法，…，做第n步有m n种不同的方法，那么完成这件事共有： N mi m2 L m n 种不同的方法. 3. 分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件. 解决排列组合综合性问题的一般过程如下： 1. 认真审题弄清要做什么事 2. 怎样做才能完成所要做的事，即采取分步还是分类，或是分步与分类同时进行,确定分多少步及多少类。 3. 确定每一步或每一类是排列问题（有序）还是组合（无序）问题,元素总数是多少及取出多少个元素. 4. 解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5 可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求，应该优先安排，以免不合要求的元素占了这两个位置.

信息学奥赛试题汇编

第19届全国青少年信息学（计算机）奥林匹克BASIC 试题说明： 请考生注意，所有试题的答案要求全部做在答题纸上。 一、基础知识单项选择题（共10题，每小题3分，共计30分） 1、存储容量2GB相当于（） A、2000KB B、2000MB C、2048MB D、2048KB 2、输入一个数（可能是小数），再按原样输出，则程序中处理此数的变量最好使用（） A、字符串类型 B、整数类型 C、实数类型 D、数组类型 3、下列关于计算机病毒的说法错误的是（） A、尽量做到使用正版软件，是预防计算机病毒的有效措施。 B、用强效杀毒软件将U盘杀毒后，U盘就再也不会感染病毒了。 C、未知来源的程序很可能携带有计算机病毒。 D、计算机病毒通常需要一定的条件才能被激活。 4、国标码的“中国”二字在计算机内占（）个字节。 A、2 B、4 C、8 D、16 5、在计算机中，ASCⅡ码是( )位二进制代码。 A、8 B、7 C、12 D、16 6、将十进制数2013转换成二进制数是( )。 A、11111011100 B、11111001101 C、11111011101 D、11111101101 7、现有30枚硬币(其中有一枚假币，重量较轻)和一架天平，请问最少需要称几次，才能找出假币( )。 A、3 B、4 C、5 D、6 8、下列计算机设备中，不是输出设备的是（）。 A、显示器 B、音箱 C、打印机 D、扫描仪 9、在windows窗口操作时，能使窗口大小恢复原状的操作是（） A、单击“最小化”按钮 B、单击“关闭”按钮 C、双击窗口标题栏 D、单击“最大化”按钮 10、世界上第一台电子计算机于1946年诞生于美国，它是出于（）的需要。 A、军事 B、工业 C、农业 D、教学二、问题求解（共2题，每小题5分，共计10分） 1、请观察如下形式的等边三角形： 边长为 2 边长为4 当边长为２时，有4个小三角形。 问：当边长为6时，有________个小三角形。 当边长为n时，有________个小三角形。 2、A、B、C三人中一位是工人，一位是教师，一位是律师。已知：C比律师年龄大，A和教师不同岁，B比教师年龄小。问：A、B、C分别是什么身分？ 答：是工人，是教师，是律师。 三、阅读程序写结果（共4题，每小题8分，共计32分） 1、REM Test31 FOR I =1 TO 30 S=S+I\5 NEXT I PRINT S END 本题的运行结果是：( １) 2、REM Test32 FOR I =1 TO 4 PRINT TAB (13-3*I)； N=0 FOR J =1 TO 2*I-1 N=N+1 PRINT N； NEXT J PRINT NEXT I END 本题的运行结果是：( ２)