排列组合专题

排列组合专题第1页，共85页，2023年，2月20日，星期五1.加法原理:

如果完成一项工作有两类相互独立的方式A和B,在方式A中有m种完成任务的途径,在方式B中有n种完成任务的途径,则完成这项工作的总的途径有m+n种.2.乘法原理:

如果完成一项工作有两个连续的步骤A和B,在步骤A中有m种不同的方式,在步骤B中有n种不同的方式,则完成这项工作的总的方法有m*n种.第2页，共85页，2023年，2月20日，星期五例1、从1到4这4个数码中不重复地任取3个构成一个三位数,求这样的三位数一共有多少个?分析:构成三位数的过程可以看成是由连续的三步完成:第一步:取百位上的数字,共有4种方法第二步:取十位上的数字,共有3种方法(即不能取百位上已经取走的数码)第三步:取个位上的数字,共有2种方法(即不能取百位和十位上已经取走的数码)因此由乘法原理,这样的三位数一共有:4*3*2=24种.第3页，共85页，2023年，2月20日，星期五例2、一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它“吃掉”后一个三位数，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位数共有多少个？百位上有5、6、7、8、9五种选择，十位上有8、9两种选择，个位上有7，8，9三种选择，所以共有5×2×3=30（个）三位数。第4页，共85页，2023年，2月20日，星期五例3、如图，一方形花坛分成编号为①，②，③，④四块，现有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色的花，且相邻的两块种不同颜色的花。如果编号为①的已经种上红色花，那么其余三块不同的种法有

种。21

编号为②的有三种选择，对于编号为③的，可以分成以下二类：1、若编号为④的与编号为②的同色，则编号为③的有三种选择。这种情况下共有3×3种方案。2、若编号为④的与编号为②的不同色，则编号为③的有二种选择，编号为④的有二种选择。这种情况下共有3×2×2种方案。第5页，共85页，2023年，2月20日，星期五例4、用红、黄、绿、蓝、黑五种颜色涂在如下图所示的ABCDE五区域，颜色可重复使用，但同色不相邻，涂法有几种？

AC同色:5*4*4*1*4AC不同色:5*4*4*3*31040

第6页，共85页，2023年，2月20日，星期五例5、在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有______种。分析：采取分类的方法。第一类：A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择；第三类：A在第三垄，B有一种选择，同理A、B位置互换，共12种。第7页，共85页，2023年，2月20日，星期五例6、某小组有10人，每人至少会英语和日语的一门，其中8人会英语，5人会日语，从中选出会英语与会日语的各1人，有多少种不同的选法?

由于8+5＝13＞10，所以10人中必有3人既会英语又会日语。（5+2+3）所以可分三类：

5×2+5×3+2×3=31第8页，共85页，2023年，2月20日，星期五例7、在所有的三位数中，有且只有两个数字相同的三位数共有多少个?

（1）△△□，（2）△□△，（3）□△□，（1），（2

），（3）类中每类都是9×9种，共有9×9+9×9+9×9＝3×9×9＝243个只有两个数字相同的三位数。

第9页，共85页，2023年，2月20日，星期五例8、求正整数1400的正因数的个数．因为任何一个正整数的任何一个正因数(除1外)都是这个数的一些质因数的积，因此，我们先把1400分解成质因数的连乘积1400=23527.所以这个数的任何一个正因数都是由2，5，7中的若干个相乘而得到(有的可重复)。于是取1400的一个正因数，这件事情是分如下三个步骤完成的：

(1)取23的正因数是20，21，22，23，共3+1种；

(2)取52的正因数是50，51，52，共2+1种；

(3)取7的正因数是70，71，共1+1种．

所以1400的正因数个数为(3+1)×(2+1)×(1+1)=24．第10页，共85页，2023年，2月20日，星期五例9、从1到300的自然数中，完全不含有数字3的有多少个？将0到299的整数都看成三位数，其中数字3不出现的，百位数字可以是0，1或2三种情况。十位数字与个位数字均有九种，因此除去0共有3×9×9－1=242(个)．第11页，共85页，2023年，2月20日，星期五例10、在小于10000的自然数中，含有数字1的数有多少个？不妨将0至9999的自然数均看作四位数，凡位数不到四位的自然数在前面补0,使之成为四位数。

先求不含数字1的这样的四位数共有几个，即有0，2，3，4，5，6，7，8，9这九个数字所组成的四位数的个数。由于每一位都可有9种写法，所以，根据乘法原理，由这九个数字组成的四位数个数为9×9×9×9＝6561。

于是，小于10000且含有数字1的自然数共有9999-6561=3438个．第12页，共85页，2023年，2月20日，星期五排列的定义数学上，把若干元素，按照任何一种顺序排成一列，叫做排列。如果两个排列满足下列条件之一，它们就被认为是不同的排列：

1.所含元素不全相同

2.所含元素相同，但顺序不同。第13页，共85页，2023年，2月20日，星期五相异元素不重复的排列从n个不同的元素中，取出r个不重复的元素，按次序排成一列，当r<n时，称为从n个中取r个的一种选排列。如：从a,b,c这三个字母中，每次取出2个，有多少种排列方法?第一步：确定左边的字母，在三个字母中任取一个，有３种方法；第二步：确定右边的字母，从剩下的２个字母中选取一个，有２种方法；根据乘法原理，共有３×２＝６种不同的排法.abacbabccacb

第14页，共85页，2023年，2月20日，星期五一般地，从n个不同的元素中取出r个元素的选排列数用表示，则＝n!/(n-r)!第15页，共85页，2023年，2月20日，星期五例１．全国足球甲级（Ａ组）联赛共有１４队参加，每队都要与其它各队在主、客场分别比赛一次，共进行多少场比赛？任何二个队进行一次主场比赛和一场客场比赛，相当于从14个元素中任取2个元素的一个排列，共需进行的比赛场次是

=14!/12!=14*13=182第16页，共85页，2023年，2月20日，星期五当n=r时,叫做n个不同元素的全排列．n个不同元素的全排列数Pnn

＝n!例２．３个人站成一排照相，共有多少种不同的排列方法？＝３!＝６第17页，共85页，2023年，2月20日，星期五例3、求有多少个没有重复数字且能被5整除的四位奇数。要能被5整除又是奇数，所以个位上数字只能是5,有1种选法，由于5已用过，又不可能是0,所以千位上数有P18种选法,已用过2个数，所以百位、十位上的数有P28种选法。所以符合题意的个数为：

1×P18×P28＝448第18页，共85页，2023年，2月20日，星期五例4、用0、1、2、3、4、5六个数字，可以组成多少个没有重复数字的三位偶数？1.个位为0,十位为1、2、3、4、5中的一个，百位为剩下的四个数字中的一个，所以这样的偶数共有1×P15×P142.个位为2,百位为1、3、4、5中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有1×P14×P143.个位为4,百位为1、2、3、5中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有1×P14×P14所以符合题意的个数为20＋16＋16＝52第19页，共85页，2023年，2月20日，星期五例5、

8位同学排成相等的两行，要求某两位同学必须排在前排，有多少种排法？这两个同学排在前排4个位置的排列数是P24，其它同学在余下的6个位置排的排列数是6！，所以符合题意的个数为P24×6！＝12×720＝8640。第20页，共85页，2023年，2月20日，星期五例6、某车站有编号为1到6的6个入口处，每个入口处每次只能进一人，问一个小组4人进站的方案有几种？第一个人有6种方案，第二个人有7种方案，因为他选择和第一个人相同入口处时，还有前后之分……9*8*7*6=3024

o︱

︱o︱

︱o︱o在两个入口之间加一个标志︱，共5个无区别的标志，问题归结为9个元素中有5个无区别的元素，4个不同元素的排列数。所以4个人进站的方案数有：9！/5！＝9*8*7*6=3024第21页，共85页，2023年，2月20日，星期五相异元素的可重复排列从n个不同元素中取出r个元素的可重复的排列种数为nr.93=729例7．由数字1,2,3,…,9共能组成多少个三位数？第22页，共85页，2023年，2月20日，星期五相异元素的循环排列

n个不同元素不分首尾排成一个圆圈，称为循环排列。其排列数为n!/n=(n-1)!。

如1,2,3三个数的循环排列只有１２３，１３２二种。第23页，共85页，2023年，2月20日，星期五例8．在圆形花坛外侧摆放８盆菊花和４盆兰花，要求兰花不能相邻摆放，一共有多少种摆法？８盆菊花摆成一周的排列方法有n1=７！４盆兰花插入８个空中的排列总数有n2=P４８=8!/4!摆放总数为n=n1*n2=8467200第24页，共85页，2023年，2月20日，星期五例9．有男女各五个人，其中有３对是夫妻，沿圆桌就座，若每对夫妻都坐在相邻的位置，问有多少种坐法？设３对夫妻分别为Ａ和a,Ｂ和b,Ｃ和c，先让Ａ，Ｂ，Ｃ三人和另外４个人沿圆桌就座的方法为６！种．又对上述每种坐法，a坐在Ａ的邻座的方式有左右两种，b,c也如此．所以共有６！＊２＊２＊２＝５７６０种．第25页，共85页，2023年，2月20日，星期五不全相异元素的排列如果在n个元素中，有n1个元素彼此相同，有n2个元素彼此相同，…,又有nm个元素彼此相同，若n1+n2+…+nm=n，则这n个元素的全排列叫做不全相异元素的全排列，其排列数为:n!/(n1!*n2!*…*nm!).若n1+n2+…+nm=r<n，则这n个元素的全排列叫做不全相异元素的选排列，其排列数为:prn/(n1!*n2!*…*nm!).第26页，共85页，2023年，2月20日，星期五例10、将N个红球和M个黄球排成一行。如:N=2,M=3可得到10种排法。问题:当N=4,M=3时有

种不同排法?7!/(4!*3!)=35NOIP2002

第27页，共85页，2023年，2月20日，星期五例11、把两个红球、一个蓝球和一个白球放到十个编号不同的盒子中去，有多少种方法？排列数为p410/(2!*1!*1!)＝2520第28页，共85页，2023年，2月20日，星期五生成排列的算法下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。

例如，输入3，则应该输出（每行输出5个排列）：

123132213231321312

求全排列(06年初赛题)第29页，共85页，2023年，2月20日，星期五vari,n,k:integer;a:array[1..10]ofinteger;count:longint;procedureperm(

k:integer);varj,p,t:integer;begin

if()thenbegin();forp:=1tokdowrite(a[p]:1);write('');if()thenwriteln;exit;end;

forj:=ktondobegint:=a[k];a[k]:=a[j];a[j]:=t;perm(k+1);t:=a[k];()

endend;beginwriteln('Entryn:');read(n);count:=0;fori:=1tondoa[i]:=i;()end.perm(1)K=ninc(count)countmod5=0a[k]:=a[j];a[j]:=t;123

132

213

231

321

312第30页，共85页，2023年，2月20日，星期五算法过程:用数组：a:array[1..r]ofinteger;表示排列;初始化时，a[i]:=i(i=1,2,…r);设中间的某一个排列为a[1],a[2],…，a[r]，则求出下一个排列的算法为：①从后面向前找，直到找到一个顺序为止（设下标为j-1,则a[j-1]<a[j]）②从a[j]～a[r]中，找出一个比a[j-1]大的最小元素a[k]③将a[j-1]与a[k]交换④将a[j]，a[j+1]……a[r]由小到大排序。

问题描述:用生成法求出1，2，…，r的全排列(r<=8).{1999年提高组}第31页，共85页，2023年，2月20日，星期五constr=7;varn,i,s,k,j,i1,t:intger;a:array[1..r]ofinteger;procedureprint1;varik:integer;beginforik:=1tordowrite(a[ik]:8);writeln;endbeginfori:=1tordo_____________;print1;{输出第一个排列}s:=1;fori:=2tordos:=s*i;{总排列数为r!}s:=s-1;{还需生成s-1个排列}fori:=______

____do

begin

j:=r;while______

_______doj:=j-1;k:=j;fori1:=j+1tordoif_____________thenk:=i1;

t:=a[j-1];a[j-1]:=a[k];a[k]:=t;fori1:=jtor-1dofork:=i1+1tordoif_______________thenbegint:=a[i1];a[i1]:=a[k];a[k]:=t;end;print1;

end;end.a[i]:=i

1tosa[j-1]>a[j](a[i1]>a[j-1])and(a[i1]<a[k])a[i1]>a[k]132541345213425第32页，共85页，2023年，2月20日，星期五【问题描述】

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指—拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：三进制数123132213231312321代表的数字123456火星人（04年普及组）第33页，共85页，2023年，2月20日，星期五现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。【输入文件】输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1<=N<=10000）。第二行是一个正整数M，表示要加上去的小整数（1<=M<=100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。【输出文件】输出文件martian.out只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。【样例输入】5312345【样例输出】12453【数据规模】对于30%的数据，N<=15；对于60%的数据，N<=50；对于全部的数据，N<=10000；第34页，共85页，2023年，2月20日，星期五varn,m,i,ss,j,k,temp:integer;min:longint;a:array[1..10000]ofinteger;beginreadln(n);readln(m);fori:=1tondoread(a[i]);whilem>0do{一次循环产生下一个排列}beginj:=n;while(j>1)and(a[j]<a[j-1])doj:=j-1;{从右到左寻找出a[j]>a[j-1]}min:=a[j];k:=j;fori:=jtondoif(a[i]>a[j-1])and(a[i]<min)thenbegink:=i;min:=a[i];end;{从a[j]到a[n],找出一个比a[j-1]大的最小值}temp:=a[j-1];a[j-1]:=a[k];a[k]:=temp;{交换}第35页，共85页，2023年，2月20日，星期五

fori:=jton-1dobeginss:=i;fork:=i+1tondoifa[ss]>a[k]thenss:=k;ifss<>ithenbegintemp:=a[i];a[i]:=a[ss];a[ss]:=temp;end;end;{在j到n中，从小到大排列}m:=m-1;end;fori:=1tondowrite(a[i],'');end.531234512354

124531243512453第36页，共85页，2023年，2月20日，星期五组合的定义数学上，把若干元素，不论次序并成一组，叫做组合。如果两个组合中，至少有一个元素不同，它们就被认为是不同的组合。abc,abd第37页，共85页，2023年，2月20日，星期五相异元素不重复的组合设从n个不同的元素中，取出m个不同元素，不考虑顺序并成一组，叫作从n个不同的元素中，取出m个不同元素的一个组合。如：写出从a,b,c,d四个元素中，任取三个元素的所有组合。abc,abd,acd,bcd从n个不同的元素中，取出m个不同元素的组合数记为Cmn;则有Cmn＝Pmn/m!=n!/m!(n-m)!规定C0n=1abc,bac,cab,acb,bca,cba第38页，共85页，2023年，2月20日，星期五例1、八年级6个班进行排球比赛，每班的排球队要与其他5个班分别比赛一场，求共要进行多少场比赛？C26＝P26/2!=6*5/2*1=15第39页，共85页，2023年，2月20日，星期五例2、平面上有n个点且无三点或三点以上共线，任意两点可以连成一条直线，一共能连成多少条直线？

C2n＝n*(n-1)/2第40页，共85页，2023年，2月20日，星期五例3、某班第一组有10名同学，第二组有8名同学，现要求每组选出2名学生代表参加座谈会，有多少种选法？C210×C28＝1260第41页，共85页，2023年，2月20日，星期五例4.一元、二元、五元、十元人民币各一张，一共可以组成多少种不同的币值？

C14＋C24＋C34＋C44＝4＋6＋4＋1＝15第42页，共85页，2023年，2月20日，星期五例5、5年级有8个班，六年级有6个班，先分别举行各年级的篮球赛，采用单循环制，然后由两个年级的第一名争夺冠军，共需要比赛多少场？

C28＋C26+1=8*7/2+6*5/2+1=28+15+1=44第43页，共85页，2023年，2月20日，星期五例6：某班第一组有10名同学，其中有4名女同学，现要求选出3名学生代表,其中至少有一名女同学去参加座谈会，有多少种选法？

代表中有1名女同学的选法为C14×C26种，

代表中有2名女同学的选法为C24×C16种，

代表中有3名女同学的选法为C34种，C14×C26＋C24×C16＋C34＝100第44页，共85页，2023年，2月20日，星期五例7、欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有()。

第45页，共85页，2023年，2月20日，星期五例8、∠A的一边AB上有4个点，另一边AC上有5个点，连同∠A的顶点共10个点，以这些点为顶点，可以构成_____个三角形.90第46页，共85页，2023年，2月20日，星期五例9、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？（2001年p）C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751第47页，共85页，2023年，2月20日，星期五例10、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形?（2001年t）C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+C(7,2)*5*6+C(5,2)*7*6+C(6,2)*5*7=21*10+21*15+10*15+21*5*6+10*7*6+15*5*7=2250第48页，共85页，2023年，2月20日，星期五

例11、10名划船运动员中，3人只会划左舷，2人只会划右舷，5人左右舷都会划，从中选6人，平均分在左、右舷，共有多少种不同的选法？

1.会划左舷的全划左舷：2.派一个全能划左舷：3.派二个全能划左舷：4.派三个全能划左舷：675第49页，共85页，2023年，2月20日，星期五例12、小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有

种。(2009年p)70第50页，共85页，2023年，2月20日，星期五排列组合+加法原理:B任务中的b1一定做，而且肯定是第一个做的。除了b1外，第一类：完成A任务只有1种。第二类：完成A任务和b2有C(4,1)=4种。第三类：完成A任务和b2、b3有C(5,2)=10种。第四类：完成A任务和b2、b3、b4有C(6,3)=20种。第五类：完成A任务和b2、b3、b4、b5有C(7,4)=35种。加起来1+4+10+20+35=70。b2a1a2a3a1b2

a2a3a1a2b2a3a1a2a3b2

第51页，共85页，2023年，2月20日，星期五例13、袋中有已编号的20个球，其中1－10号是红球，11－20号是白球，每取得一个红球得2分，取得一个白球得3分，若取得若干个球，共得20分，有多少种不同取法？2x+3y=20,y必是偶数，所以y=0,2,4,6；相应地x=10,7,4,1；

C010×C1010＋C210×C710＋C410×C410

＋C610×C110

＝51601第52页，共85页，2023年，2月20日，星期五例14、从1－300之间任取3个不同的数，使得这3个数的和恰好被3除尽，有多少种方法？被3除所得的余数不外乎：0，1，2。所以可把1－300之间的数分成三组：

A＝{1,4,7,…,298}B＝{2,5,8,…,299}C＝{3,6,9,…,300}

三个数同属于集合A，有C3100种，三个数同属于集合B，有C3100种，三个数同属于集合C，有C3100种，三个数分属于集合A，B，C，有1003种。加起来等于

1485100种。第53页，共85页，2023年，2月20日，星期五例15、若将一个正整数化为二进制数，在此二进制数中，我们将数字0的个数多于数字1的个数的这类二进制数称为A类数。例如：（24）10=（11000）2

其中1的个数为2，0的个数为3，则称此数为A类数；请你求出1～112之中（包括1与112），全部A类数的个数。（112）10=（1110000）2可根据二进制数的前缀来分类。第54页，共85页，2023年，2月20日，星期五111××××：这类数中A类数只有一个，即1110000110××××：这类数中A类数个数为：

C44＋C34＝510×××××：这类数中A类数个数为：

C55＋C45＋C35

＝160××××××：位数不确定，需对位数进行讨论。第55页，共85页，2023年，2月20日，星期五1位数，即1,不是A类数，2位数，即1×，10和11都不是A类数，3位数，即1××，只有100一个，4位数，即1×××，只有1000一个，5位数，即1××××，A类数个数有C44＋C34＝5,6位数，即1×××××，A类数个数有C55＋C45＝6,1＋5＋16＋（1＋1＋5＋6）＝35第56页，共85页，2023年，2月20日，星期五例16、某城市有4条东西街道和6条南北的街道，街道之间的间距相同。若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法?(2007年p)MN（一）从M到N必须向上走三步，向右走五步，共走八步。（二）每一步是向上还是向右，决定了不同的走法。（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数。

∴本题答案为56。第57页，共85页，2023年，2月20日，星期五相异元素的可重复组合设从n个不同的元素中，取出m个不同元素，若允许这个元素可以重复使用，也允许m>n，则把这样的组合称为重复组合，其组合数记为Hmn。

Hmn=Cmn+m-1

如1,2,3,4,四个数字中取三个，允许重复的组合有以下20种：

111,122,134,224,333112,123,144,233,334113,124,222,234,344114,133,223,244,444第58页，共85页，2023年，2月20日，星期五组合的生成算法从1,2,3,…,n共n个数中任取m个数，请输出所有组合并计算组合数。varn,m,i,k,s:integer;a,b:array[0..100]ofinteger;beginreadln(n,m);fori:=1tomdobegina[i]:=i;b[i]:=

;end;k:=m;s:=0;repeatif

thenbegins:=s+1;fori:=1tomdowrite(a[i]);write('');end;ifa[k]<b[k]thenbegin

;ifk<mthenfork:=k+1tomdo

;endelse

;untilk=0;writeln;writeln('s=',s);end.n-m+ik=ma[k]:=a[k]+1a[k]:=a[k-1]+1k:=k-1第59页，共85页，2023年，2月20日，星期五Jam的计数法【问题描述】Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V，且不存在Jam数字P，使U<P<V）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。第60页，共85页，2023年，2月20日，星期五

【输入文件】输入文件counting.in有2行，第1行为3个正整数，用一个空格隔开：stw（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s<t≤26,2≤w≤t-s）第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。【输出文件】输出文件counting.out最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。【输入样例】2105bdfij【输出样例】bdghibdghjbdgijbdhijbefgh第61页，共85页，2023年，2月20日，星期五vari,j,s,t,w,n:longint;st:string;a:array[0..30]ofinteger;beginreadln(s,t,w);readln(st);{输入起始字符串}fori:=1towdoa[i]:=ord(st[i])-(ord('a')+s)+2;{将字符串转变为数字串}a[0]:=0;n:=0;{控制开关变0和生成个数清0}while(a[0]=0)and(n<5)dobegini:=w;while(a[i]=t-s+1-w+i)and(i>0)doi:=i-1;inc(a[i]);forj:=i+1towdoa[j]:=a[j-1]+1;{产生下一个组合}ifa[0]<>0thenbeginhalt;endelsebeginfori:=1towdowrite(chr(ord('a')+a[i]+s-2));writeln;n:=n+1;{个数加1}end;end;end.2105bdfij先转换：98-(97+2)+2=113589{初始组合}i=5时，t-s-w+i+1=10-2-5+5+1=9a[5]最大可取9产生下一个组合：13678输出：i=1时,chr(97+1+2-2)=bbdghi第62页，共85页，2023年，2月20日，星期五排列组合题型总结排列组合问题千变万化，解法灵活，条件隐晦，思维抽象，难以找到解题的突破口。因而在求解排列组合应用题时，除做到：排列组合分清，加乘原理辩明，避免重复遗漏外，还应注意积累排列组合问题得以快速准确求解。第63页，共85页，2023年，2月20日，星期五直接法1.特殊元素法

用1，2，3，4，5，6这6个数字组成无重复的四位数，试求满足下列条件的四位数各有多少个（1）数字1不排在个位和千位;（2）数字1不在个位，数字6不在千位。分析：（1）个位和千位有5个数字可供选择，其余2位有四个可供选择，由乘法原理：=240

特殊元素，优先处理；特殊位置，优先考虑。第64页，共85页，2023年，2月20日，星期五2.特殊位置法

（2）当1在千位时余下三位有=60，1不在千位时，千位有种选法，个位有种，余下的有，共有

=192,所以总共有192+60=252第65页，共85页，2023年，2月20日，星期五间接法当直接法求解类别比较大时，应采用间接法。如上例中（2）可用间接法

第66页，共85页，2023年，2月20日，星期五有五张卡片，它的正反面分别写0与1，2与3，4与5，6与7，8与9，将它们任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？

分析：此例正面求解需考虑0与1卡片用与不用，且用此卡片又分使用0与使用1，类别较复杂，因而可使用间接计算：任取三张卡片可以组成不同的三位数个，其中0在百位的有个，这是不合题意的。故共可组成不同的三位数=432（个）.第67页，共85页，2023年，2月20日，星期五

8位同学排成一行，要求某两位同学互不相邻，有多少种排法？8位同学排成一行的总数是8！把排在一起的的两个同学看成一个人的排列总数是7！因为排在一起的两个同学的位置可以互换，所以两位同学排在一起的排列数是2×7！所以符合题意的个数为8！－2×7！＝30240第68页，共85页，2023年，2月20日，星期五正方体8个顶点中取出4个，可组成多少个四面体?所求问题的方法数=任意选四点的组合数-共面四点的方法数，∴-12=70-12=58个。第69页，共85页，2023年，2月20日，星期五插空法在一个含有8个节目的节目单中，临时插入两个歌唱节目，且保持原节目顺序，有多少种插入方法？原有的8个节目中含有9个空档，插入一个节目后，空档变为10个，故有=90中插入方法。第70页，共85页，2023年，2月20日，星期五

8位同学排成一行，其中有4位女同学，要求女同学不相邻，有多少种排法？四位男同学排成一行的总数是4！，在他们首尾两个位置和他们两两之间的位置（共5个）分别插入一个女同学的排列数是A45＝120，所以符合题意的个数是4！×120＝2880第71页，共85页，2023年，2月20日，星期五马路上有编号为l，2，3，……，10十个路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法共有多少种?

关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。∴共=20种方法。

第72页，共85页，2023年，2月20日，星期五捆绑法当需排元素中有必须相邻的元素时，宜用捆绑法。

4名男生和3名女生共坐一排，男生必须排在一起的坐法有多少种？分析：先将男生捆绑在一起看成一个大元素与女生全排列有种排法，而男生之间又有种排法，由乘法原理满足条件的排法有：×=576第73页，共85页，2023年，2月20日，星期五四个不同的小球全部放入三个不同的盒子中，若使每个盒子不空，则不同的放法有

种。一定有两个球放在同一个盒子中．第74页，共85页，2023年，2月20日，星期五某市植物园要在30天内接待20所学校的学生参观，但每天只能安排一所学校，其中有一所学校人数较多，要安排连续参观2天，其余只参观一天，则植物园30天内不同的安排方法有（）.注意连续参观2天，即需把30天中的连续两天捆绑看成一天作为一个整体来选有，其余的就是19所学校选28天进行排列。第75页，共85页，2023年，2月20日，星期五书架上有四本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。满足A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有（）种摆法。（2008年p）第76页，共85页，2023年，2月20日，星期五闸板法名额分配或相同物品的分配问题，适宜采用闸板法.

某校准备组建一个由12人组成的篮球队，这12个人由8个班的学生组成，每班至少一人，名额分配方案共

种。分析：此例的实质是12个名额分配给8个班，每班至少一个名额，可在12个名额中的11个空当中插入7块闸板，一种插法对应一种名额的分配方式，故有种。第77页，共85页，2023年，2月20日，星期五若m,n∈N,m≦n，把n写成m个自然数之和，如：m＝3,n＝5时，5＝1＋1＋3＝1＋3＋1＝3＋1＋1＝2＋2＋1＝2＋1＋2＝1＋2＋2.问共有多少种表示法？5＝1＋1＋（1＋1＋1）＝1＋（1＋1＋1）＋1＝（1＋1＋1）＋1＋1＝（1＋1）＋（1＋1）＋1＝（1＋1）＋1＋（1＋1）＝1＋（1＋1）＋（1＋1）对n=1+1+1+…+1有几种加括号的方法，也就是在n-1个加号中，保留m-1个加号，将其余的各部分元素分别加起来。

Cm-1n-1第78页，共85页，2023年，2月20日，星期五平均分堆6本不同的书平均分成三堆，有多少种不同的方法？

分析：分出三堆书（a1,a2）,(a3,a4)，（a5,a6）,由顺序不同可以有=6种，而这6种分法只算一种分堆方式