信息学奥赛辅导排列与组合基础知识教程文件.docx
《信息学奥赛辅导排列与组合基础知识教程文件.docx》由会员分享，可在线阅读，更多相关《信息学奥赛辅导排列与组合基础知识教程文件.docx（13页珍藏版）》请在冰点文库上搜索。
信息学奥赛辅导排列与组合基础知识教程文件
（信息学奥赛辅导）排列与组合基础知识
排列与组合基础知识
有关排列与组合的基本理论和公式：
加法原理：
做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类中办法中有m2种不同的方法，……，在第n类办法中有mn种不同方法。
那么完成这件事共有N＝m1＋m2＋…＋mn种不同的方法，这一原理叫做加法原理。
乘法原理：
做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×…×mn种不同的方法，这一原理叫做乘法原理。
公式：
阶乘公式
，规定0！
＝1；
全排列公式
选排列公式
、
圆排列：
n个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：
组合数公式
、规定
、
、
）
提示：
（1）全排列问题和选排列问题，都可根据乘法原理推导出来。
（2）书写方式：
记为P（n,r）；
记为C（n,r）。
加法原理例题：
图1中从A点走到B点共有多少种方法？
（答案：
4＋2＋3＝9）
乘法原理例题：
图2中从A点走到B点共有多少种方法？
（答案：
4×6＝24）
加法原理与乘法原理综合：
图3、图4中从A走到B共有多少种方法？
（答案：
28、42）
注意：
在信息学奥赛中，有许多只需计数而不需具体方案的问题，都可以通过思维转换或方法转换，最后变为两类问题：
一类是转变为排列组合问题，另一类是转变为递推公式问题。
因此对于加法原理、乘法原理、排列、组合等知识，需要非常熟练，以达到简化问题的目的。
加法原理、乘法原理、排列、组合例题：
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本书，问有多少种方法。
（提示：
此题为组合问题，答案为
＝10）
6.五种不同颜色的珠子串成一圈项链，问有多少种不同的方法。
（提示：
此题属于圆排列问题，答案为（5－1）！
＝24）
7.把两个红色球、两个蓝色球、三个黄色球摆放在球架上，问有多少种方案。
（提示：
此题为排列问题。
摆放方案总数为（2＋2＋3）！
种，但是两个红球一样，所以要除以2！
，同理两个蓝球，除以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的方法，共有
种方法，但是有3个0是一样的，所以应该除以
，即第一类分法的方法数为
种，同理，第二种分法的方法数为
，第三种分法的方法数为
，所以总共的方法数为（
＋
＋
）种。
解答
（2）自行求解。
解答（3）：
这一类问题，我们称为重复组合问题，其求解公式为C（n+r-1,r）。
请记住该公式即可。
）
排列组合练习习题：
1.有5本日文书、7本英文书、10本中文书。
问
（1）从中任取2本书有多少种方案？
（2）从中取2本相同文字的书有多少种方案？
（3）从中取2本不同文字的书有多少种方案？
（提示：
此题为组合问题。
答案分别为：
、
、
）
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（测试数据：
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人；同时培训物理、化学的有8人；三科都培训的有5人。
问该年级共有多少人？
（提示：
对于此类问题，我们可以用一个图示法表示，从图中我们看出，总人数即为：
A＋B＋C－A∩B－B∩C－C∩A＋A∩B∩C＝150＋120＋100－21－16－8＋5＝330）
排列组合考试题：
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个格子。
现有两个不同颜色的球要放在其中，要求两个球不能相邻，问共有多少种摆放方案。
（提示：
在所有的摆放方案中，减去两个球相邻的摆放方案，即将此二球看为一个整体，（注意此二球可以左右交换位值），因为有六个格子一样，最后需要除以
。
答案：
＝42种）
20.有一排格子排成一排，已知共有8个格子。
现有三个不同颜色的球要放在其中，要求任意两个球不能相邻，问共有多少种摆放方案。
（提示：
为了方便理解说明，不妨将这三个不同颜色的球编号为1、2、3号。
所有的摆放方案为
，减去任意两个球相邻的摆放方案，共有六种情况（即12、21、13、31、23、32），此时需要注意三个球相邻的情况，三个球相邻的情况有123、312、213、321、132、231共六种情况，在减去任意两个球相邻的情况时，比如减去12相邻的情况时，三个球相邻的情况123和312同时被减去了，同理还有其它五种情况，说明三球相邻的情况各被多减了一次，所以最后需要加上三球相邻的情况。
答案为：
＝120种）
21.有一排格子排成一排，已知共有8个格子。
现有2个红色球和3个蓝色球要放在其中，要求如下：
（1）每个格子最多摆放一个球；
（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少空出一个格子。
问共有多少种摆放方案。
如下是其中一种摆放方案。
红
红
蓝
蓝
蓝
（提示：
将每种颜色的球看作一个整体后方法同上。
答案：
＝12种）
22.有一排格子排成一排，已知共有12个格子。
现有3个红色球、2个蓝色球和1个黄色球要放在其中，要求如下：
（1）每个格子最多摆放一个球；
（2）同一种颜色的球必须相邻摆放；（3）不同颜色的球之间至少空出一个格子。
问共有多少种摆放方案。
如下是其中一种摆放方案。
红
红
红
蓝
蓝
黄
（提示：
将每种颜色的球看作一个整体后方法同上。
答案：
＝210种）
23.有一排格子排成一排，已知共有8个格子。
现有两个相同的球要放在其中，要求两个球不能相邻，问共有多少种摆放方案。
（提示：
在19题的基础上，只是因为两个球相同而已，所以最后需除以
，答案：
）
24.有一排格子排成一排，已知共有8个格子。
现有三个相同的球要放在其中，要求任意两个球不能相邻，问共有多少种摆放方案。
（提示：
方法同上题，因为三个球相同，故最后需除以
，答案：
＝20种）
升级会员 