《排列组合专题》PPT课件.ppt

《《排列组合专题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《排列组合专题》PPT课件.ppt（85页珍藏版）》请在三一办公上搜索。

1、加法原理和乘法原理,加法原理和乘法原理是排列组合的基础和核心，既可用来推导排列数、组合数公式，也可用来直接解题。它们的共同点都是把一个事件分成若干个分事件来进行计算。利用加法原理，重在分“类”，类与类之间具有独立性和并列性；利用乘法原理，重在分步；步与步之间具有相依性和连续性。比较复杂的问题，常先分类再分步。,1.加法原理:如果完成一项工作有两类相互独立的方式A和B,在方式A中有m种完成任务的途径,在方式B中有n种完成任务的途径,则完成这项工作的总的途径有m+n种.,2.乘法原理:如果完成一项工作有两个连续的步骤A和B,在步骤A中有m种不同的方式,在步骤B中有n种不同的方式,则完成这项工作的总

2、的方法有m*n种.,例1、,从1到4这4个数码中不重复地任取3个构成一个三位数,求这样的三位数一共有多少个?,分析:构成三位数的过程可以看成是由连续的三步完成:第一步:取百位上的数字,共有4种方法第二步:取十位上的数字,共有3种方法(即不能取百位上已经取走的数码)第三步:取个位上的数字,共有2种方法(即不能取百位和十位上已经取走的数码)因此由乘法原理,这样的三位数一共有:4*3*2=24种.,例2、,一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它“吃掉”后一个三位数，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位数共有多少个

3、？,百位上有5、6、7、8、9五种选择，十位上有8、9两种选择，个位上有7，8，9三种选择，所以共有523=30（个）三位数。,例3、,如图，一方形花坛分成编号为，四块，现有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色的花，且相邻的两块种不同颜色的花。如果编号为的已经种上红色花，那么其余三块不同的种法有 种。,21,编号为的有三种选择，对于编号为的，可以分成以下二类：1、若编号为的与编号为的同色，则编号为的有三种选择。这种情况下共有33种方案。2、若编号为的与编号为的不同色，则编号为的有二种选择，编号为的有二种选择。这种情况下共有322种方案。,例4、,用红、黄、绿、蓝、黑五种颜色涂

4、在如下图所示的ABCDE五区域，颜色可重复使用，但同色不相邻，涂法有几种？,AC同色:5*4*4*1*4AC不同色:5*4*4*3*3,1040,例5、,在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有_种。,分析：采取分类的方法。第一类：A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择；第三类：A在第三垄，B有一种选择，同理A、B位置互换，共12种。,例6、,某小组有10人，每人至少会英语和日语的一门，其中8人会英语，5人会日语，从中选出会英语与会日语的各1人，有多少种不同的选法?,由于8+

5、51310，所以10人中必有3人既会英语又会日语。（5+2+3）所以可分三类：52+53+23=31,例7、,在所有的三位数中，有且只有两个数字相同的三位数共有多少个?,（1），（2），（3），,（1），（2），（3）类中每类都是99种，共有99+99+99399243个只有两个数字相同的三位数。,例8、,求正整数1400的正因数的个数,因为任何一个正整数的任何一个正因数(除1外)都是这个数的一些质因数的积，因此，我们先把1400分解成质因数的连乘积1400=23527.所以这个数的任何一个正因数都是由2，5，7中的若干个相乘而得到(有的可重复)。,于是取1400的一个正因数，这件事情是分如下

6、三个步骤完成的：(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,例9、,从1到300的自然数中，完全不含有数字3的有多少个？,将0到299的整数都看成三位数，其中数字3不出现的，百位数字可以是0，1或2三种情况。十位数字与个位数字均有九种，因此除去0共有3991=242(个),例10、,在小于10000的自然数中，含有数字1的数有多少个？,不妨将0至9999的自然数均看作四位数，凡位数不到四位的自然数在前面补0,使之成为四位数。

7、先求不含数字1的这样的四位数共有几个，即有0，2，3，4，5，6，7，8，9这九个数字所组成的四位数的个数。由于每一位都可有9种写法，所以，根据乘法原理，由这九个数字组成的四位数个数为99996561。于是，小于10000且含有数字1的自然数共有9999-6561=3438个,排列的定义,数学上，把若干元素，按照任何一种顺序排成一列，叫做排列。如果两个排列满足下列条件之一，它们就被认为是不同的排列：1.所含元素不全相同 2.所含元素相同，但顺序不同。,相异元素不重复的排列,从 n个不同的元素中，取出r个不重复的元素，按次序排成一列，当rn时，称为从n个中取r个的一种选排列。,如：从a,b,c这

8、三个字母中，每次取出2个，有多少种排列方法?第一步：确定左边的字母，在三个字母中任取一个，有种方法；第二步：确定右边的字母，从剩下的个字母中选取一个，有种方法；根据乘法原理，共有种不同的排法.ab ac ba bc ca cb,一般地，从n个不同的元素中取出r个元素的选排列数用 表示，则 n!/(n-r)!,例全国足球甲级（组）联赛共有队参加，每队都要与其它各队在主、客场分别比赛一次，共进行多少场比赛？,任何二个队进行一次主场比赛和一场客场比赛，相当于从14个元素中任取2个元素的一个排列，共需进行的比赛场次是=14!/12!=14*13=182,当n=r时,叫做n个不同元素的全排列n个不同元素

9、的全排列数Pnn n!,例个人站成一排照相，共有多少种不同的排列方法？,!,例3、求有多少个没有重复数字且能被5整除的四位奇数。,要能被5整除又是奇数，所以个位上数字只能是5,有1种选法，由于5已用过，又不可能是0,所以千位上数有P18种选法,已用过2个数，所以百位、十位上的数有P28种选法。所以符合题意的个数为：1 P18 P28448,例4、用0、1、2、3、4、5六个数字，可以组成多少个没有重复数字的三位偶数？,1.个位为0,十位为1、2、3、4、5中的一个，百位为剩下的四个数字中的一个，所以这样的偶数共有1P15P14,2.个位为2,百位为1、3、4、5中的一个，十位为剩下的四个数字中

10、的一个，所以这样的偶数共有1P14P14,3.个位为4,百位为1、2、3、5中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有1P14P14,所以符合题意的个数为20161652,例5、8位同学排成相等的两行，要求某两位同学必须排在前排，有多少种排法？,这两个同学排在前排4个位置的排列数是P24，其它同学在余下的6个位置排的排列数是6！，所以符合题意的个数为P246！127208640。,例6、某车站有编号为1到6的6个入口处，每个入口处每次只能进一人，问一个小组4人进站的方案有几种？,第一个人有6种方案，第二个人有7种方案，因为他选择和第一个人相同入口处时，还有前后之分9*8*7*6

11、=3024,相异元素的可重复排列,从n个不同元素中取出r个元素的可重复的排列种数为nr.,93=729,例7由数字1,2,3,9共能组成多少个三位数？,相异元素的循环排列,n个不同元素不分首尾排成一个圆圈，称为循环排列。其排列数为n!/n=(n-1)!。如1,2,3三个数的循环排列只有，二种。,例8在圆形花坛外侧摆放盆菊花和盆兰花，要求兰花不能相邻摆放，一共有多少种摆法？,盆菊花摆成一周的排列方法有n1=！盆兰花插入个空中的排列总数有n2=P=8!/4!摆放总数为n=n1*n2=8467200,例9有男女各五个人，其中有对是夫妻，沿圆桌就座，若每对夫妻都坐在相邻的位置，问有多少种坐法？,设对夫

12、妻分别为和a,和b,和c，先让，三人和另外个人沿圆桌就座的方法为！种又对上述每种坐法，a坐在的邻座的方式有左右两种，b,c也如此所以共有！种,不全相异元素的排列,如果在n个元素中，有n1个元素彼此相同，有n2个元素彼此相同，,又有nm个元素彼此相同，若n1+n2+nm=n，则这n个元素的全排列叫做不全相异元素的全排列，其排列数为:n!/(n1!*n2!*nm!).,若n1+n2+nm=rn，则这n个元素的全排列叫做不全相异元素的选排列，其排列数为:prn/(n1!*n2!*nm!).,例10、将N个红球和M个黄球排成一行。如:N=2,M=3可得到10种排法。问题:当N=4,M=3时有 种不同排

13、法?,7!/(4!*3!)=35,NOIP2002,例11、把两个红球、一个蓝球和一个白球放到十个编号不同的盒子中去，有多少种方法？,排列数为p410/(2!*1!*1!)2520,生成排列的算法,下面程序的功能是利用递归方法生成从1到n(n10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）：123 132 213 231 321 312,求全排列(06年初赛题),var i,n,k:integer;a:array1.10 of integer;count:longint;procedure perm(k:integer);var j,p,t:in

14、teger;begin if()then begin();for p:=1 to k do write(ap:1);write();if()then writeln;exit;end;,for j:=k to n do begin t:=ak;ak:=aj;aj:=t;perm(k+1);t:=ak;()end end;begin writeln(Entry n:);read(n);count:=0;for i:=1 to n do ai:=i;()end.,perm(1),K=n,inc(count),count mod 5=0,ak:=aj;aj:=t;,123 132 213 231 3

15、21 312,算法过程:用数组：a:array1.r of integer;表示排列;初始化时，ai:=i(i=1,2,r);设中间的某一个排列为a1,a2,，ar，则求出下一个排列的算法为：从后面向前找，直到找到一个顺序为止（设下标为j-1,则aj-1aj）从aj ar中，找出一个比aj-1大的最小元素ak将aj-1与ak交换将aj，aj+1ar由小到大排序。,问题描述:用生成法求出1，2，r的全排列(r=8).1999年提高组,const r=7;var n,i,s,k,j,i1,t:intger;a:array1.rof integer;procedure print1;var ik:i

16、nteger;begin for ik:=1 to r do write(aik:8);writeln;endbegin for i:=1 to r do _;print1;输出第一个排列 s:=1;for i:=2 to r do s:=s*i;总排列数为r!s:=s-1;还需生成s-1个排列 for i:=_ _do begin j:=r;while_ _do j:=j-1;k:=j;for i1:=j+1 to r do if _ _ then k:=i1;,t:=aj-1;aj-1:=ak;ak:=t;for i1:=j to r-1 do for k:=i1+1 to r do if

17、 _then begin t:=ai1;ai1:=ak;ak:=t;end;print1;end;end.,ai:=i,1 to s,aj-1aj,(ai1aj-1)and(ai1ak),ai1ak,1 3 2 5 41 3 4 5 21 3 4 2 5,【问题描述】人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。火星人用一种非常简单的方式来表示数字掰手

18、指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的

19、数字：,火星人（04年普及组）,现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。【输入文件】输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1=N=10000）。第二行是一个正整数M，表示要加上去的小整数（1=M=100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。【输出文件】输出文件martian.out只有一行，这一行

20、含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。【样例输入】531 2 3 4 5【样例输出】1 2 4 5 3【数据规模】对于30%的数据，N=15；对于60%的数据，N=50；对于全部的数据，N=10000；,var n,m,i,ss,j,k,temp:integer;min:longint;a:array1.10000of integer;begin readln(n);readln(m);for i:=1 to n do read(ai);while m0 do一次循环产生下一个排列 begin j:=n;while(j1)and(a

21、jaj-1 min:=aj;k:=j;for i:=j to n do if(aiaj-1)and(aimin)then begin k:=i;min:=ai;end;从aj到an,找出一个比aj-1大的最小值 temp:=aj-1;aj-1:=ak;ak:=temp;交换,for i:=j to n-1 do begin ss:=i;for k:=i+1 to n do if assak then ss:=k;if ssi then begin temp:=ai;ai:=ass;ass:=temp;end;end;在j到n中，从小到大排列 m:=m-1;end;for i:=1 to n d

22、o write(ai,);end.,531 2 3 4 51 2 3 5 4 1 2 4 5 3 1 2 4 3 51 2 4 5 3,组合的定义,数学上，把若干元素，不论次序并成一组，叫做组合。如果两个组合中，至少有一个元素不同，它们就被认为是不同的组合。abc,abd,相异元素不重复的组合,设从n个不同的元素中，取出m个不同元素，不考虑顺序并成一组，叫作从n个不同的元素中，取出m个不同元素的一个组合。,如：写出从a,b,c,d四个元素中，任取三个元素的所有组合。,abc,abd,acd,bcd,从n个不同的元素中，取出m个不同元素的组合数记为Cmn;则有CmnPmn/m!=n!/m!(n-

23、m)!规定C0n=1,abc,bac,cab,acb,bca,cba,例1、八年级6个班进行排球比赛，每班的排球队要与其他5个班分别比赛一场，求共要进行多少场比赛？,C26P26/2!=6*5/2*1=15,例2、平面上有n个点且无三点或三点以上共线，任意两点可以连成一条直线，一共能连成多少条直线？,C2nn*(n-1)/2,例3、某班第一组有10名同学，第二组有8名同学，现要求每组选出2名学生代表参加座谈会，有多少种选法？,C210C281260,例4.一元、二元、五元、十元人民币各一张，一共可以组成多少种不同的币值？,C14C24C34C44464115,例5、5年级有8个班，六年级有6个

24、班，先分别举行各年级的篮球赛，采用单循环制，然后由两个年级的第一名争夺冠军，共需要比赛多少场？,C28C26+1=8*7/2+6*5/2+1=28+15+1=44,例6：某班第一组有10名同学，其中有4名女同学，现要求选出3名学生代表,其中至少有一名女同学去参加座谈会，有多少种选法？,代表中有1名女同学的选法为C14C26种，代表中有2名女同学的选法为C24C16种，代表中有3名女同学的选法为C34种，,C14C26C24C16C34100,例7、欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有()。,例8、A的一边AB上有4个点，另一边AC上有5个点，连同A的顶点共10个

25、点，以这些点为顶点，可以构成_个三角形.,90,例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,例10、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形?（2001年t）,C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(

26、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,例11、10名划船运动员中，3人只会划左舷，2人只会划右舷，5人左右舷都会划，从中选6人，平均分在左、右舷，共有多少种不同的选法？,675,例12、小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤

27、顺序不能打乱，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有 种。(2009年p),70,排列组合+加法原理: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、b

28、4、b5 有C(7,4)=35种。加起来1+4+10+20+35=70。,例13、袋中有已编号的20个球，其中110号是红球，1120号是白球，每取得一个红球得2分，取得一个白球得3分，若取得若干个球，共得20分，有多少种不同取法？,2x+3y=20,y必是偶数，所以y=0,2,4,6；相应地x=10,7,4,1；,C010C1010C210C710 C410C410 C610C110 51601,例14、从1300之间任取3个不同的数，使得这3个数的和恰好被3除尽，有多少种方法？,被3除所得的余数不外乎：0，1，2。所以可把1300之间的数分成三组：A1,4,7,298 B2,5,8,299

29、 C3,6,9,300 三个数同属于集合A，有C3100种，三个数同属于集合B，有C3100种，三个数同属于集合C，有C3100种，三个数分属于集合A，B，C，有1003种。加起来等于 1485100种。,例15、若将一个正整数化为二进制数，在此二进制数中，我们将数字0的个数多于数字1的个数的这类二进制数称为A类数。例如：（24）10=（11000）2 其中1的个数为2，0的个数为3，则称此数为A类数；请你求出1112之中（包括1与112），全部A类数的个数。,（112）10=（1110000）2可根据二进制数的前缀来分类。,111：这类数中A类数只有一个，即1110000,0：位数不确定，需

30、对位数进行讨论。,1位数，即1,不是A类数，2位数，即1，10和11都不是A类数，3位数，即1，只有100一个，4位数，即1，只有1000一个，5位数，即1，A类数个数有C44C345,6位数，即1，A类数个数有C55C456,1516（1156）35,例16、,某城市有4条东西街道和6条南北的街道，街道之间的间距相同。若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法?(2007年p),M,N,（一）从M到N必须向上走三步，向右走五步，共走八步。（二）每一步是向上还是向右，决定了不同的走法。（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。从而，任务可叙述为：从八

31、个步骤中选出哪三步是向上走，就可以确定走法数。本题答案为56。,相异元素的可重复组合,设从n个不同的元素中，取出m个不同元素，若允许这个元素可以重复使用，也允许mn，则把这样的组合称为重复组合，其组合数记为Hmn。Hmn=Cmn+m-1 如1,2,3,4,四个数字中取三个，允许重复的组合有以下20种：111,122,134,224,333 112,123,144,233,334 113,124,222,234,344 114,133,223,244,444,组合的生成算法,从1,2,3,n共n个数中任取m个数，请输出所有组合并计算组合数。,var n,m,i,k,s:integer;a,b:a

32、rray0.100 of integer;begin readln(n,m);for i:=1 to m do begin ai:=i;bi:=;end;k:=m;s:=0;repeat if then begin s:=s+1;for i:=1 to m do write(ai);write();end;if akbk then begin;if km then for k:=k+1 to m do;end else;until k=0;writeln;writeln(s=,s);end.,n-m+i,k=m,ak:=ak+1,ak:=ak-1+1,k:=k-1,Jam的计数法,【问题描述】

33、Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用b,c,d,e,f,g,h,i,j这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”

34、，则UV，且不存在Jam数字P，使UPV）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。,【输入文件】输入文件counting.in 有2行，第1行为3个正整数，用一个空格隔开：s t w（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1st26,2wt-s）第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。【输出文件】输出文件counting.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有

35、几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。【输入样例】2 10 5 bdfij【输出样例】bdghibdghjbdgijbdhijbefgh,var i,j,s,t,w,n:longint;st:string;a:array0.30of integer;begin readln(s,t,w);readln(st);输入起始字符串 for i:=1 to w do ai:=ord(sti)-(ord(a)+s)+2;将字符串转变为数字串 a0:=0;n:=0;控制开关变0和生成个数清0 while(a0=0)and(n0)do i:=i-1;inc

36、(ai);for j:=i+1 to w do aj:=aj-1+1;产生下一个组合 if a00 then begin halt;end else begin for i:=1 to w do write(chr(ord(a)+ai+s-2);writeln;n:=n+1;个数加1 end;end;end.,2 10 5bdfij先转换：98-(97+2)+2=1 1 3 5 8 9初始组合i=5时，t-s-w+i+1=10-2-5+5+1=9 a5最大可取9产生下一个组合：1 3 6 7 8输出：i=1时,chr(97+1+2-2)=b bdghi,排列组合题型总结,排列组合问题千变万化，

37、解法灵活，条件隐晦，思维抽象，难以找到解题的突破口。因而在求解排列组合应用题时，除做到：排列组合分清，加乘原理辩明，避免重复遗漏外，还应注意积累排列组合问题得以快速准确求解。,直接法,1.特殊元素法,用1，2，3，4，5，6这6个数字组成无重复的四位数，试求满足下列条件的四位数各有多少个（1）数字1不排在个位和千位;（2）数字1不在个位，数字6不在千位。,分析：（1）个位和千位有5个数字可供选择，其余2位有四个可供选择，由乘法原理：=240,特殊元素，优先处理；特殊位置，优先考虑。,2.特殊位置法,（2）当1在千位时余下三位有=60，1不在千位时，千位有 种选法，个位有 种，余下的有，共有=1

38、92,所以总共有192+60=252,间接法,当直接法求解类别比较大时，应采用间接法。如上例中（2）可用间接法,有五张卡片，它的正反面分别写0与1，2与3，4与5，6与7，8与9，将它们任意三张并排放在一起组成三位数，共可组成多少个不同的三位数？,8位同学排成一行，要求某两位同学互不相邻，有多少种排法？,8位同学排成一行的总数是8！把排在一起的的两个同学看成一个人的排列总数是7！因为排在一起的两个同学的位置可以互换，所以两位同学排在一起的排列数是27！所以符合题意的个数为8！27！30240,正方体8个顶点中取出4个，可组成多少个四面体?,所求问题的方法数=任意选四点的组合数-共面四点的方法数

39、，-12=70-12=58个。,插空法,在一个含有8个节目的节目单中，临时插入两个歌唱节目，且保持原节目顺序，有多少种插入方法？,原有的8个节目中含有9个空档，插入一个节目后，空档变为10个，故有=90中插入方法。,8位同学排成一行，其中有4位女同学，要求女同学不相邻，有多少种排法？,四位男同学排成一行的总数是4！，在他们首尾两个位置和他们两两之间的位置（共5个）分别插入一个女同学的排列数是A45120，所以符合题意的个数是4！1202880,马路上有编号为l，2，3，10 十个路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求

40、满足条件的关灯方法共有多少种?,关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。共=20种方法。,捆绑法,当需排元素中有必须相邻的元素时，宜用捆绑法。,4名男生和3名女生共坐一排，男生必须排在一起的坐法有多少种？,分析：先将男生捆绑在一起看成一个大元素与女生全排列有 种排法，而男生之间又有 种排法，由乘法原理满足条件的排法有：=576,四个不同的小球全部放入三个不同的盒子中，若使每个盒子不空，则不同的放法有 种。,一定有两个球放在同一个盒子中,某市植物园要在30天内接待20所学校的学生参观，但每天只能安排一所学

41、校，其中有一所学校人数较多，要安排连续参观2天，其余只参观一天，则植物园30天内不同的安排方法有（）.,注意连续参观2天，即需把30天中的连续两天捆绑看成一天作为一个整体来选有，其余的就是19所学校选28天进行排列。,书架上有四本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。满足A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有（）种摆法。（2008年p）,闸板法,名额分配或相同物品的分配问题，适宜采用闸板法.,某校准备组建一个由12人组成的篮球队，这12个人由8个班的学生组成，每班至少一人，名

42、额分配方案共 种。,分析：此例的实质是12个名额分配给8个班，每班至少一个名额，可在12个名额中的11个空当中插入7块闸板，一种插法对应一种名额的分配方式，故有 种。,若m,nN,mn，把n写成m个自然数之和，如：m3,n5时，5113131311221212122.问共有多少种表示法？,511（111）1（111）1（111）11（11）（11）1（11）1（11）1（11）（11）,对n=1+1+1+1有几种加括号的方法，也就是在n-1个加号中，保留m-1个加号，将其余的各部分元素分别加起来。,Cm-1n-1,平均分堆,6本不同的书平均分成三堆，有多少种不同的方法？,分析：分出三堆书（a1

43、,a2）,(a3,a4)，（a5,a6）,由顺序不同可以有=6种，而这6种分法只算一种分堆方式，故6 本不同的书平均分成三堆方式有=15种,合并单元格,如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则不同的着色方法共有 种。,分析：颜色相同的区域可能是2、4;3、5下面分情况讨论:()当2、4颜色相同且3、5颜色不同时，将2、4合并成一个单元格，此时不同的着色方法相当于4个元素 的全排列数（）当2、4颜色不同且3、5颜色相同时，与情形()类似同理可得 种着色法（）当2、4与3、5分别同色时，将2、4；3、5分别合并，这样仅有三个单元格 从4种

44、颜色中选3种来着色这三个单元格，计有 种方法由加法原理知：不同着色方法共有2=72（种）,一个有N级台阶的楼梯,一次可以跨一级台阶,也可以跨两级台阶,问上这个楼梯一共有多少种不同的走法.,递推是组合数学的一个重要内容,是我们解决计数问题时一种强有力的武器.,递推法,分析:按最后一步的走法可以将上这个楼梯的所有走法分成两类:(1)最后一步跨一级台阶(2)最后一步跨两级台阶.这两种分类方法显然是相互独立的,因此由加法法则有:所有走法=最后一步跨一级的所有走法+最后一步跨两级的所有走法.设上N级台阶的所有走法的总数记为F(N),因此有:最后一步跨一级台阶的所有走法为F(N-1);最后一步跨两级台阶的

45、所有走法为F(N-2);于是(1)式写为:F(N)=F(N-1)+F(N-2).特别地:F(1)=1,F(2)=2,d0d1排列,n个0与n个1组成的数，从最左边算起，任何位置0的个数不得少于1的个数，这样的排列有多少种？,例、公园门票每张5角,如果有2n个人排队购票,每人一张，并且其中一半人恰有角钱,另一半人恰有元钱,而票房无零钱可找，那么有多少种方法将这2n个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间？,Cn2n-Cn-12n,用回溯法解决：const maxn=10;var a:array1.maxn*2 of integer;n,num:integer;procedur

46、e try(k,n0,n1:integer);var i,j:integer;begin if()then begin inc(num);write(No.,num,);for i:=1 to 2*n do write(ai:2);writeln;();end;if(n0=n1)and(n0n)then begin ak:=0;try();end;,if()and(n0n)then begin for i:=0 to 1 do begin ak:=i;if i=0 then try(k+1,n0+1,n1)else try(k+1,n0,n1+1);end;end;if()then begin ak:=1;try(k+1,n0,n1+1);end;end;beginfillchar(a,sizeof(a),0);readln(n);num:=0;try(1,0,0);end.,k=2*n+1,k+1,n0+1,n1,n0n1,n0=n,exit,n0是有角钱的人数n1是有元钱的人数,正整数的有序拆分,一位小朋友有n块奶糖，他每天至少吃一块，吃完为止，有多少种不同方案？,2n-1,这个问题与正整数的有序拆分有关，例如4的有序且允许重复的分割方案数为8.4=44=1+34=3+14=2+24=2+1+14=1+2+14=1+1+24=1+1+1+1,