nbhkdz.com冰点文库

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

时间:2015-01-09


第1页

排列与组合基础知识 有关排列与组合的基本理论和公式: 加法原理:做一件事,完成它可以有 n 类办法,在第一类办法中有 m1 种不同的方法,在第二类中办 法中有 m2 种不同的方法,……,在第 n 类办法中有 mn 种不同方法。那么完成这件事共有 N=m1+m2+…+mn 种不同的方法,这一原理叫做加法原理。 乘法原理:做一件事,完成它需要分成 n 个

步骤,做第一步有 m1 种不同的方法,做第二步有 m2 种 不同的方法,……,做第 n 步有 mn 种不同的方法,那么完成这件事共有 N=m1×m2×…× mn 种不同的方法,这一原理叫做乘法原理。 公式:阶乘公式 n! ? n ? (n ? 1) ? (n ? 2)
n 全排列公式 P n ? n!

3 ? 2 ?1 ,规定 0!=1;

选排列公式 Pn ? n(n ? 1)(n ? 2)
m

(n ? m ? 1) ?

n! m m m 、P n ? Cn P m (n ? m)!
n! ? (n ? 1)! n

圆排列:n 个不同元素不分首位围成一个圆圈达到圆排列,则排列数为:
m 组合数公式 Cn ?

Pnm n(n ? 1)(n ? 2) (n ? m ? 1) n! 0 、规定 Cn ? ? ?1 m Pm m! m!(n ? m)!
n ? Cn ? 2n )

0 1 2 m n?m m m m?1 、 Cn 、 Cn ? Cn ? Cn ? Cn ? Cn ?1 ? Cn ? Cn

提示: (1)全排列问题和选排列问题,都可根据乘法原理推导出来。
r r (2)书写方式: P ; Cn 记为 C(n,r) 。 n 记为 P(n,r)

加法原理例题:图 1 中从 A 点走到 B 点共有多少种方法?(答案:4+2+3=9) 乘法原理例题:图 2 中从 A 点走到 B 点共有多少种方法?(答案:4×6=24) 加法原理与乘法原理综合:图 3、图 4 中从 A 走到 B 共有多少种方法?(答案:28、42)

A

B

A

B

图1

图2

A

B

A

B

图3

图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)同理,先确定百位数、再确定十位数、最后确定个位数,根据乘法原理,共有 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 本书,问有多少种方法。 (提示:此题为组合问题,答案为 C5 ?
3

5? 4? 3 =10) 3!

6.

五种不同颜色的珠子串成一圈项链,问有多少种不同的方法。 (提示:此题属于圆排列问题,答案为(5-1) !=24) 7. 把两个红色球、两个蓝色球、三个黄色球摆放在球架上,问有多少种方案。 (提示:此题为排列问题。摆放方案总数为(2+2+3) !种,但是两个红球一样,所以要除以 2! , 同理两个蓝球,除以 2! ,三个黄球,除以 3! ,即摆放方案总数为 8.

(2 ? 2 ? 3)! ? 210 ) 2!? 2!? 3!

有男女各 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 类;对于第一类 3、0、 0、 0 的方法, 共有 P 4 种方法,但是有 3 个 0 是一样的,所以应该除以 P 3 ,

即第一类分法的方法数为 P 4 /P 3 种,同理,第二种分法的方法数为 P 4 /P 2 ,第三种分法的方法 数为 P 4 /P 3 ,所以总共的方法数为( P 4 /P 3 +P 4 /P 2 +P 4 /P 3 )种。 解答(2)自行求解。 解答(3) :这一类问题, 我们称为重复组合问题, 其求解公式为 C(n+r-1,r) 。请记住该公式即可。 )
4 3 4 3 4 2 4 3

4

3

4

2

第3页

排列组合练习习题: 1. 有 5 本日文书、7 本英文书、10 本中文书。问(1)从中任取 2 本书有多少种方案?(2)从中取 2 本相同文字的书有多少种方案?(3)从中取 2 本不同文字的书有多少种方案?
2 2 2 2 2 2 2 2 (提示:此题为组合问题。答案分别为: C5 ?7 ?10 、 C5 ? C7 ? C10 、 C5?7?10 ? (C5 ? C7 ? C10 ) )

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 1 1 1 1 走,因为只有两种走法,不妨用二进制表示走路方式,1 表示向 1 2 3 4 5 右走,0 表示向下走。则可用一个长度为(N+M-2)的二进制 1 3 6 10 15 串来表示走路方法,其中如果出现了 N-1 个 1,则表示找到了 1 4 10 20 35 一种路径。从而把题目转化为求长度为 N+M-2 的 2 进制串中 有 N-1 个 1 的个数,即求组合数学公式 C(N+M-2,N-1) 的值。

第4页

方法二:对本题稍加分析就能发现,要到达棋盘上的某个点,只能从该点的上边过来,或者从该 点的左边过来,根据加法原理,要到达该点的路径数目,就等于到达该点上点的路径与该点左点 的路径数目之和,因此我们可以按照逐行递推的方法求出从起点到终点的路径数目。初始化,左 上角第一个元素值为 1,其它点的值为上点与左点的和。 ) 对于如右图的网格,用方法一的答案为 C(4+3,3)=35; 用方法二逐行递推的方法得到网格上的数字,最后答案也为 35。 比较两种方法,当数据较小时,采用公式一比较直接,但如果数据较大时,公式一的乘法运算 量较大,这时可考虑用方法二逐行递推求得答案。 10. 在上题中,若规定 N<M,行走方向仍然只能是向右或者向下行走,并且要求所经过的每一个点的 坐标(a,b)恒满足 a<b 的关系(a 为行坐标,b 为列坐标) ,问有多少条路径? (测试数据: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??。对于此问题,有许多变形应用,请熟记该公式。 ) ① 1 ② 1 ③ (举一反三:一个由 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 人数即为:A+B+C-A∩B-B∩C-C∩A+A∩B∩C=150+120+100 -21-16-8+5=330)

第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 六个字母进行排列,其字符排列中不出现“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 个格子。现有两个不同颜色的球要放在其中,要求两个球不能相 邻,问共有多少种摆放方案。 (提示:在所有的摆放方案中,减去两个球相邻的摆放方案,即将此二球看为一个整体, (注意此
6 二球可以左右交换位值) ,因为有六个格子一样,最后需要除以 P 6 。答案:
8 7 P 8 ? 2P 7 =42 种) P66

20. 有一排格子排成一排,已知共有 8 个格子。现有三个不同颜色的球要放在其中,要求任意两个球不 能相邻,问共有多少种摆放方案。
8 (提示: 为了方便理解说明, 不妨将这三个不同颜色的球编号为 1、 2、 3 号。 所有的摆放方案为 P 8 ,

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

P88 ? 6 P77 ? 6P66 =120 种) P55

21. 有一排格子排成一排,已知共有 8 个格子。现有 2 个红色球和 3 个蓝色球要放在其中,要求如下: (1)每个格子最多摆放一个球; (2)同一种颜色的球必须相邻摆放; (3)不同颜色的球之间至少 空出一个格子。问共有多少种摆放方案。如下是其中一种摆放方案。 红 红 蓝 蓝 蓝

P55 ? 2P44 (提示:将每种颜色的球看作一个整体后方法同上。答案: =12 种) P33
22. 有一排格子排成一排,已知共有 12 个格子。现有 3 个红色球、2 个蓝色球和 1 个黄色球要放在其 中,要求如下: (1)每个格子最多摆放一个球; (2)同一种颜色的球必须相邻摆放; (3)不同颜色

第6页

的球之间至少空出一个格子。问共有多少种摆放方案。如下是其中一种摆放方案。 红 红 红 蓝 蓝 黄

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

P99 ? 6 P88 ? 6 P77 =210 种) P66

23. 有一排格子排成一排,已知共有 8 个格子。现有两个相同的球要放在其中,要求两个球不能相邻, 问共有多少种摆放方案。
2 (提示:在 19 题的基础上,只是因为两个球相同而已,所以最后需除以 P 2 ,答案:
8 7 P 8 ? 2P 7 ) P66 ? P22

24. 有一排格子排成一排,已知共有 8 个格子。现有三个相同的球要放在其中,要求任意两个球不能相 邻,问共有多少种摆放方案。
3 (提示:方法同上题,因为三个球相同,故最后需除以 P 3 ,答案:

P88 ? 6 P77 ? 6P66 =20 种) P55 ? P33

25. 26.


信息学奥赛基础知识习题

信息学奥赛基础知识习题(答案版) 一、选择题(下列各题仅有一个正确答案,请将...151. 在资源管理器右窗格中,如果需要选定多个非连续排列的文件,应按组合键 A...

【精品完整版】信息学奥赛基础知识习题(答案版)

信息学奥赛基础知识习题(答案版) 一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统软件系统总称为 ...

信息学竞赛中问题求解常见题分析(排列组合)

初​中​信​息​学​竞​赛​资​料信息学竞赛中问题求解常见题分析 排列组合问题 排列组合问题一,知识点: 知识点: 1. 分类计数原理 分类计数原...

(信息学奥赛辅导)程序设计试题汇编(答案)

(信息学奥赛辅导)程序设计试题汇编(答案)_学科竞赛_高中教育_教育专区。wenhua ...排列与组合类问题: 13、因子、质因子(质因数)类相关问题: 答案部分:(程序设计...

信息学奥赛 基础知识习集

(信息学奥赛辅导)排列与组... 6页 免费 信息学奥赛——算法入门教... 35页...如果鼠标器突然失灵,则可用组合键 A 来结束一个正在运行的应用程序(任务) . ...

信息学奥赛基础知识习题 (1)

信息学奥赛基础知识习题一、选择题(下列各题仅有一个正确答案,请将你认为是...不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是(...

信息学奥赛(初赛)辅导教材

数据库管理) ⑤信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件...合并排序、快速排序)第 1 页 金华一中信息学(计算机)奥林匹克竞赛辅导教程 ③...

信息学奥赛基础知识

(信息学奥赛辅导)程序设计... 51页 免费 信息学奥赛...基本结构第三章 网络基础知识 第一节 网络的组成与...称为队首,通常也用一个队首指针 f 指向排头元素...

(信息学奥赛辅导)数据结构基础知识

信息学奥赛辅导--基础知识 6页 8财富值 (信息学奥赛辅导)排列与组... 6页...(图 4) 7. 图结构:图是由顶点集 V 和边集 E 组成,一般把图 G 记为 ...

(信息学奥赛辅导)程序设计试题汇编(答案)

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第1页 程序设计试题及答案(...排列与组合类问题: 13、 因子、质因子(质因数)类相关问题: 答案部分: 答案部分...