常见的一些排列、组合模式和解法

#1111P*P*P*P6982排列按照元素的排列方式又可分为三种排列⑴线排列；⑵圆排列；⑶重排列。一、线排列：先考察一个简单的问题，有红、蓝、白三只球，要放到编号为1，2，„，10的十个盒子中，如果每个盒子只能装一只球，问把球放到盒子中的不同放法的种类。分析：每次放一只球，不妨依此顺序：放红球T放蓝球T放白球。放红球的方法有10种(红球可放在10个盒子的任一个中)放蓝球的方法有9种(红球可放在9个盒子的任一个中)放白球的方法有8种(红球可放在8个盒子的任一个中)根据乘法原理：这些球的不同放法总共有10X9X8=720(种)根据上例，不难推广到一般，得到线排列的定义：从n个不同的元素中，取r个按次序排列，称为从n中取r个排列，记为P(n,r)。显然，P(n,r)=n(n-1)(n-2)・・・(n-r+1)=n!/(n-r)!其中，当r=0时，一个元素也不取，算作是取0个元素的一种排列，即P(n,0)=1；当r=n时，有P(n,n)=n!，即n的全排列；而把0<r<n的情况称为选排列。［例］在五天之内安排三次考试，且不允许一天内有两次考试，那末一共有多少种安排法？解：不妨把三次考试看作是三只颜色不同的球，五天看作是五个编号不同的盒子，P(5,3)=5x4x3=60［思考］确定各位数中不重复的四位十进制数的个数。、圆排列：从集合S={a「a2,a3,…,a}的n个不同元素中，取出r个元素按照某种次序(如逆时针)排成一个圆圈，称这样的排列为圆排列。气週屯…牛,週屯…牛％a3a4^ana1a25毎气週…％-!需要注意的是，一个圆排列旋转可得另一个圆排列，这两个圆排列是相同的，例如取出r个元素气週屯…牛,週屯…牛％a3a4^ana1a25毎气週…％-!这r个线排列在圆排列中只能算一个。一个圆排列可以产生r个线排列，而总共有P(n,r)个线排列，因此圆排列的个数为：P(n,r)/r=n!/(r(n-1)!)［例］有8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多P(8,8)8P(8,8)8二7!(种)少种就座方式？解：n=8,r=8,因此8人围圆桌就餐的就座方式有：设不愿坐在一起的两人为甲和乙。不妨考虑甲乙坐在一起时的情况。此时，相当于7人围桌而坐,其就坐方式为7!/7（n=7,r=7）。而甲乙坐在一起又有两种情况，这样，甲和乙坐在一起时共有2X6!种就坐方式。因此，甲和乙不坐在一起的就座方式共有：7!-2X6!=3600（种）三、重排列：前面讨论的是从n个互不相同的元素组成的集合S=｛a「a2,…,aj中选r个元素进行排列、在每种排列中每个元素至多只出现一次的情况。现在考虑允许重复出现的情况，即考虑在重集S=｛中］,k2・a2,…,/aj中选r个元素进行排列。根据重复数k1，k2，„,kn是否趋向I重排列又可分为无限重排列和有限重排列。1．无限重排列：考查把三个不同颜色的球放在十个不同的盒子中问题。若每个盒子能容纳的球的只数无限，那么，蓝球和白球也能像红球一样放入十个盒子中的任一个，所以放置的方法总数是：10X10X10=103=1000（种）一般地，从n个不同元素中取r个按次序排列，若每个元素无限次重复（即k1=k2=„=k=-），则称排列为无限次排列，其排列数等于nr。"［例］无线电收发报机有‘•’和‘一’（短、长）两种信号，用四个信号代表一个阿拉伯数码，问可以表示多少个不同码？解：对无线电收发报机来说，有两种信号，取四个表示一个数码，这是一种重排列：四个信号：□□□□每个信号两种表示：•—………因此，总共可以表示不同的数码个数是：24=16（个）这样，对于十进制记数法中只有十个不同的数码是完全够用了。同理，通用明码用四个数码表示一个汉字，可以表示出的汉字个数为104=10000。若不允许重复，四个十进制码仅能表示P（10,4）=5040个汉字，显然是不够的。2．有限重排列：若允许元素有限次重复，那S=｛匕牛,k2・a2,…,叫叫｝（ki#^），则从所有元素中取r个有次序排列的种数又如何计算呢？［例］有两只红球、一只蓝球和一只白球放到编号不同的十个盒子中去的方法总数是多少？解：将两只红球分别涂成深红色和浅红色，使之能区别，于是问题转化为四只不同颜色的球放到十个盒子中去的方法种数是：P（io,4）=5040。在这5040种方法中,若不区分红球的深浅，那么两种方法变成一种方法，因此，两只红球、一只蓝球和一只白球放入十个编号不同的盒子的方法种数有：5040/2=2520。一般地，把r只彩色球放到n个编号不同的盒子中去的方法种数是：P（n,r）r!r!...r!i2t其中，ri表示第i种彩球有ri只，i=1,2，3,…，t,且有r=r1+r2Hrt。当r=n时，有：n!n!...n!12t其中，n1表示n1个相同元素，…,叫表示nt个相同元素且有片+出叫=n。［思考］某市区中的一处棋盘形街道，有南北方向街道（纵街）5条，东西方向街道（横街）8条，见下图，某人从东南角走到西北角，要按最短路径走（就是只能向西或向北走），共有几种走法？南

附：第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（初中组竞赛用时：3小时）―、设有一个N*M方格的棋盘（1WNW100,1WMW100）。（30%）求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）例如：当N=2，M=3时：正方形的个数有8个，即边长为1的正方形有6个；边长为2的正方形有2个。a

bc

de

其中：a〜i分别表示1,2,…，9中的一个数字，并要求满足下列条件：⑴a<f<i；⑵b<d，g<h，c<e；⑶a+b+d+f=f+g+h+i=i+e+c+a=P程序要求：根据输入的边长P，输出所有满足上述条件的三角形的个数及其中的一种方案。三、设有一个N*M（1WNW50,1WMW50）的街道（如下图）：（40%）北东南B(9,5)A(1,北东南B(9,5)A(1,1)规定行人从A出发，在街道上只能向东或向北方向行走。如下为N=3,M=3的街道图，从A出发到达B共有6条可供走的路径:B(N,M)A5A2A—A1—A2—A5—B(N,M)A5A2A—A1—A4—A5—BA—A1—A4—A7—BA—A3—A4—A5—BA—A3—A4—A7—BA—A3—A6—A7—B若在N*M的街道中，设置一个矩形障碍区域（包括围住该区域的街道）不让行人通过，如上图中用“*”表示的部分。此矩形障碍区域用2对顶点坐标给出，图中的2对顶点