《排列组合专题》PPT课件

1、加法原理和乘法原理加法原理和乘法原理 加法原理和乘法原理是排列组合的基础和核心，既可加法原理和乘法原理是排列组合的基础和核心，既可用来推导排列数、组合数公式，也可用来直接解题。它们用来推导排列数、组合数公式，也可用来直接解题。它们的共同点都是把一个事件分成若干个分事件来进行计算。的共同点都是把一个事件分成若干个分事件来进行计算。 利用加法原理，重在分利用加法原理，重在分“类类”，类与类之间具有独立，类与类之间具有独立性和并列性；性和并列性； 利用乘法原理，重在分步；步与步之间具有相依性和利用乘法原理，重在分步；步与步之间具有相依性和连续性。连续性。 比较复杂的问题，常先分类再分步。比较复杂的问

2、题，常先分类再分步。1.加法原理加法原理: 如果完成一项工作有两类如果完成一项工作有两类相互独立的方式相互独立的方式A和和B,在方式在方式A中有中有m种完成任务的途径种完成任务的途径,在方式在方式B中有中有n种完成任务的途种完成任务的途径径,则完成这项工作的总的途径有则完成这项工作的总的途径有m+n种种.2.乘法原理乘法原理: 如果完成一项工作有两个如果完成一项工作有两个连续的步骤连续的步骤A和和B,在步骤在步骤A中有中有m种不同的方式种不同的方式,在步骤在步骤B中有中有n种不同的方式种不同的方式,则完成则完成这项工作的总的方法有这项工作的总的方法有m*n种种.例例1、 从从1到到4这这4个数

3、码中个数码中不重复地任取不重复地任取3个构成一个构成一个三位数个三位数,求这样的三位数一共有多少个求这样的三位数一共有多少个?分析分析:构成三位数的过程可以看成是由连续的三步完成构成三位数的过程可以看成是由连续的三步完成:第一步第一步:取百位上的数字取百位上的数字,共有共有4种方法种方法第二步第二步:取十位上的数字取十位上的数字,共有共有3种方法种方法(即不能取百位上已即不能取百位上已经取走的数码经取走的数码)第三步第三步:取个位上的数字取个位上的数字,共有共有2种方法种方法(即不能取百位和十即不能取百位和十位上已经取走的数码位上已经取走的数码)因此由因此由乘法原理乘法原理,这样的三位数一共有

4、这样的三位数一共有:4*3*2=24种种.例2、 一个三位数，如果它的每一位数字都不小于另一一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它个三位数对应数位上的数字，就称它“吃掉吃掉”后一个后一个三位数，例如三位数，例如543吃掉吃掉432，543吃掉吃掉543，但是，但是543不能吃掉不能吃掉534。那么能吃掉。那么能吃掉587的三位数共有多的三位数共有多少个？少个？ 百位上有百位上有5、6、7、8、9五种选择，十位上有五种选择，十位上有8、9两种选两种选择，个位上有择，个位上有7，8，9三种选择，所以共有三种选择，所以共有523=30（个）（个）三位数。三位数。例

5、例3、 如图，一方形花坛分成编号为如图，一方形花坛分成编号为，四块，现四块，现有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色的花，且相邻的两块种不同颜色的花。颜色的花，且相邻的两块种不同颜色的花。如果编号为如果编号为的的已经种上红色花已经种上红色花，那么其余三块不同的种法有，那么其余三块不同的种法有 种。种。21 编号为编号为的有三种选择，对于编号为的有三种选择，对于编号为的，可以分成以下二类：的，可以分成以下二类：1、若编号为若编号为的与编号为的与编号为的同色的同色，则编，则编号为号为的有三种选择。这种情况下共有的有三种选择。这种

6、情况下共有33种方案。种方案。2、若编号为若编号为的与编号为的与编号为的不同色的不同色，则，则编号为编号为的有二种选择，编号为的有二种选择，编号为的有二种的有二种选择。这种情况下共有选择。这种情况下共有322种方案。种方案。例例4、 用红、黄、绿、蓝、黑五种颜色涂在如用红、黄、绿、蓝、黑五种颜色涂在如下图所示的下图所示的ABCDE五区域，颜色可重复使用，五区域，颜色可重复使用，但同色不相邻，涂法有几种？但同色不相邻，涂法有几种？ AC同色同色:5*4*4*1*4AC不同色不同色:5*4*4*3*31040 例例5、 在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利

7、于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有_种。分析：采取分类的方法。 第一类：A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择； 第三类：A在第三垄，B有一种选择， 同理A、B位置互换 ，共12种。 例例6、 某小组有某小组有10人，每人至少会英语和日语的一门，人，每人至少会英语和日语的一门，其中其中8人会英语，人会英语，5人会日语，从中选出会英语与会人会日语，从中选出会英语与会日语的各日语的各1人，有多少种不同的选法人，有多少种不同的选法? 由于由于8+51310，所以，所以10人中必有人中必有3人既会英人既会英语又会日语。语又会日语。（5+2+3）所以可分三

8、类：所以可分三类： 52 + 53 + 23=31例例7、 在所有的三位数中，有且只有两个数字相同在所有的三位数中，有且只有两个数字相同的三位数共有多少个的三位数共有多少个? （1），（2），（3），（1），（），（2 ），（），（3）类中每类都是）类中每类都是99种，共有种，共有99+99+99399243个只有两个数字相同的个只有两个数字相同的三位数。三位数。 例例8、求正整数求正整数1400的正因数的个的正因数的个数数 因为因为任何一个正整数的任何一个正因数任何一个正整数的任何一个正因数(除除1外外)都是这个都是这个数的一些质因数的积数的一些质因数的积，因此，我们先把，因此，我们先把14

9、00分解成质因数的分解成质因数的连乘积连乘积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+

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

11、然数在前面补0, ,使之成为四位数。使之成为四位数。先求不含数字先求不含数字1的这样的四位数共有几个，即有的这样的四位数共有几个，即有0，2，3，4，5，6，7，8，9这九个数字所组成的四位数的个数。这九个数字所组成的四位数的个数。由于每一位都可有由于每一位都可有9种写法，所以，根据乘法原理，由这九种写法，所以，根据乘法原理，由这九个数字组成的四位数个数为个数字组成的四位数个数为99996561。 于是，小于于是，小于10000且含有数字且含有数字1的自然数共有的自然数共有9999-6561=3438个个排列的定义排列的定义 数学上，把若干元素，按照任何一种顺序排成数学上，把若干元素，按照任何

12、一种顺序排成一列，叫做排列。一列，叫做排列。 如果两个排列满足下列条件之一，它们就被认如果两个排列满足下列条件之一，它们就被认为是不同的排列：为是不同的排列： 1.所含元素不全相同所含元素不全相同 2.所含元素相同，但顺序不同。所含元素相同，但顺序不同。相异元素不重复的排列相异元素不重复的排列 从从 n个不同的元素中，取出个不同的元素中，取出r个不重复的元素，个不重复的元素，按次序排成一列，当按次序排成一列，当rn时，称为从时，称为从n个中取个中取r个的个的一种选排列。一种选排列。如：从如：从a,b,c这三个字母中，每次取出这三个字母中，每次取出2个，有多少种排列方法个，有多少种排列方法?第一

13、步：确定左边的字母，在三个字母中任取一个，有种方法；第一步：确定左边的字母，在三个字母中任取一个，有种方法；第二步：确定右边的字母，从剩下的个字母中选取一个，有种第二步：确定右边的字母，从剩下的个字母中选取一个，有种方法；方法；根据根据乘法原理乘法原理，共有，共有种不同的排法种不同的排法. ab ac ba bc ca cb 一般地，从一般地，从n个不同的元素中取出个不同的元素中取出r个元素的个元素的选排列数用选排列数用 表示，则表示，则 n!/(n-r)!rnPrnP例例全国足球甲级（组）联赛共有队参全国足球甲级（组）联赛共有队参加，每队都要与其它各队在加，每队都要与其它各队在主、客场主、客

14、场分别比赛一分别比赛一次，共进行多少场比赛？次，共进行多少场比赛？ 任何二个队进行一次主场比赛和一场客场比任何二个队进行一次主场比赛和一场客场比赛，相当于从赛，相当于从14个元素中任取个元素中任取2个元素的一个排个元素的一个排列，共需进行的比赛场次是列，共需进行的比赛场次是 =14!/12!=14*13=182214P当当n=r时时,叫做叫做n个不同元素的个不同元素的全排列全排列n个不同元素的全排列数个不同元素的全排列数Pnn n!例例个人站成一排照相，共有多少种不同的排个人站成一排照相，共有多少种不同的排列方法？列方法？ !33P例例3、求有多少个、求有多少个没有重复数字没有重复数字且能被且

15、能被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中的一个

16、，百位为剩下的中的一个，百位为剩下的四个数字中的一个，所以这样的偶数共有四个数字中的一个，所以这样的偶数共有1P15P142.个位为个位为2,百位为百位为1、3、4、5中的一个，十位为剩下的四个中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有数字中的一个，所以这样的偶数共有1P14P143.个位为个位为4,百位为百位为1、2、3、5中的一个，十位为剩下的四个中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有数字中的一个，所以这样的偶数共有1P14P14所以符合题意的个数为所以符合题意的个数为20161652例例5、 8位同学排成相等的两行，要求某两位同位同学排成相等的两行，要

17、求某两位同学必须排在前排，有多少种排法？学必须排在前排，有多少种排法？ 这两个同学排在前排这两个同学排在前排4个位置的排列数是个位置的排列数是P24，其它同学在余下的其它同学在余下的6个位置排的排列数是个位置排的排列数是6！，所！，所以符合题意的个数为以符合题意的个数为P246！127208640。例例6、某车站有编号为某车站有编号为1到到6的的6个入口处，每个个入口处，每个入口处入口处每次只能进一人每次只能进一人，问一个小组，问一个小组4人进站的人进站的方案有几种？方案有几种？第一个人有第一个人有6种方案，第二个人有种方案，第二个人有7种方案，因为种方案，因为他选择和第一个人相同入口处时，还

18、有前后之他选择和第一个人相同入口处时，还有前后之分分9*8*7*6=3024 o o oo 在两个入口之间加一个标志，在两个入口之间加一个标志，共共5个无区别的标志，问题归结为个无区别的标志，问题归结为9个元素中有个元素中有5个无个无区别的元素，区别的元素，4个不同元素的排列数。所以个不同元素的排列数。所以4个人进站个人进站的方案数有：的方案数有：9！/5！9*8*7*6=3024相异元素的可重复排列相异元素的可重复排列 从从n个不同元素中取出个不同元素中取出r个元素的可重复的排列个元素的可重复的排列种数为种数为nr.93=729例例7由数字由数字1,2,3,9共能组成多少个三位数？共能组成多

19、少个三位数？相异元素的循环排列相异元素的循环排列 n个不同元素不分首尾排成一个圆圈，称为循环个不同元素不分首尾排成一个圆圈，称为循环排列。其排列数为排列。其排列数为n!/n=(n-1)!。 如如1,2,3三个数的循环排列只有，三个数的循环排列只有，二种。二种。例例8在圆形花坛外侧摆放盆菊花和盆兰花，在圆形花坛外侧摆放盆菊花和盆兰花，要求兰花不能相邻摆放，一共有多少种摆法？要求兰花不能相邻摆放，一共有多少种摆法？盆菊花摆成一周的排列方法有盆菊花摆成一周的排列方法有n1=！盆兰花插入个空中的排列总数有盆兰花插入个空中的排列总数有n2=P=8!/4!摆放总数为摆放总数为n=n1*n2=8467200

20、例例9有男女各五个人，其中有对是夫妻，沿有男女各五个人，其中有对是夫妻，沿圆桌就座，若每对夫妻都坐在相邻的位置，问有圆桌就座，若每对夫妻都坐在相邻的位置，问有多少种坐法？多少种坐法？设对夫妻分别为和设对夫妻分别为和a,和和b,和和c，先让，先让，三人和另外个人沿圆桌就座的方法为！种三人和另外个人沿圆桌就座的方法为！种又对上述每种坐法，又对上述每种坐法，a坐在的邻座的方式有左右两坐在的邻座的方式有左右两种，种，b,c也如此也如此所以共有！种所以共有！种不全相异元素的排列不全相异元素的排列 如果在如果在n个元素中，有个元素中，有n1个元素彼此相同，有个元素彼此相同，有n2个元素彼此相同，个元素彼此

21、相同，,又有又有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时有时有 种不同种不同排法排法?7!/(4!

22、*3!)=35NOIP2002 例例11、把两个红球、一个蓝球和一个白球放到、把两个红球、一个蓝球和一个白球放到十个编号不同的盒子中去，有多少种方法？十个编号不同的盒子中去，有多少种方法？排列数为排列数为p410/(2!*1!*1!)2520生成排列的算法生成排列的算法 下面程序的功能是利用递归方法生成从下面程序的功能是利用递归方法生成从1到到n(n10)的的n个数的全部可能的排列（不一定按升个数的全部可能的排列（不一定按升序输出）。序输出）。 例如，输入例如，输入3，则应该输出（每行输出，则应该输出（每行输出5个排个排列）：列）： 123 132 213 231 321 312 求全排列求全

23、排列(06年初赛题年初赛题)var var i i,n,k:integer; ,n,k:integer; a a:array1.10 of integer; :array1.10 of integer; count:longint count:longint; ; procedure perm(procedure perm( k k:integer); :integer); var var j,p,t:integer; j,p,t:integer; begin begin if( )then if( )then begin begin ( ); ( ); for p:=1 to k do fo

24、r p:=1 to k do write(ap:1); write(ap:1); write( ); write( ); if( )then if( )then writeln writeln; ; exit; exit; end; end; for j:=k to n do for j:=k to n do begin begin t:=ak; t:=ak; ak ak:=aj; :=aj; aj aj:=t;:=t; perm(k+1) perm(k+1) ; ; t:=ak;( ) t:=ak;( ) end end end; end; begin begin writeln(Entry

25、 writeln(Entry n:); n:); read(n); read(n); count:=0; count:=0; for i:=1 to n do ai:=i; for i:=1 to n do ai:=i; ( ) ( ) end.end.perm(1)K=ninc(count)count mod 5=0ak:=aj; aj:=t ;123 132 213 231 321 312算法过程算法过程:用数组：用数组：a:array1.r of integer ;表示排列表示排列; 初始化时，初始化时，ai:=i(i=1,2,r);设中间的某一个排列为设中间的某一个排列为a1,a2,，

26、ar，则求出下一个排列的算法为：，则求出下一个排列的算法为：从后面向前找，直到找到一个顺序为止从后面向前找，直到找到一个顺序为止（设下标为（设下标为j-1,则则aj-1aj）从从aj ar中，找出一个比中，找出一个比aj-1大的最小元素大的最小元素ak将将aj-1与与ak交换交换将将aj，aj+1ar由小到大排序。由小到大排序。 问题描述问题描述: 用生成法求出用生成法求出1，2，r的全排列的全排列(raj(ai1aj-1)and(ai1ak1 3 2 5 41 3 4 5 21 3 4 2 5【问题描述【问题描述】 人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人人类终于登上了火

27、星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。面，把结果告诉火星人，作为人类的回答。 火星人用一种非常简单的方式来表示数字火星人用一种非常简单的方式来表示数字掰手指。火星人只有

28、一掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3。火星人的任意两根手指都能随意交换位置，他们就是通过这方。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指根手指拇指、食指、中指、无名指和小指分别编号为拇指、食指、中指、无名指和小指分别编号为1，2，3，4和和5，当它们按正常顺序排列时，形成了当它们按正常顺序排列时，形成了5位数位数12345，当你交换

29、无名指和小指的，当你交换无名指和小指的位置时，会形成位置时，会形成5位数位数12354，当你把五个手指的顺序完全颠倒时，会形成，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的，在所有能够形成的120个个5位数中，位数中，12345最小，它表示最小，它表示1；12354第二小，它表示第二小，它表示2；54321最大，它表示最大，它表示120。下表展示了只有。下表展示了只有3根根手指时能够形成的手指时能够形成的6个个3位数和它们代表的数字：位数和它们代表的数字：三进制数三进制数123132213231312321代表的数字代表的数字123456火星人（火星人（04年普及组）年普

30、及组） 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。【输入文件【输入文件】输入文件输入文件martian.in包括三行，第一行有

31、一个正整数包括三行，第一行有一个正整数N，表示火星人手指的，表示火星人手指的数目（数目（1 = N = 10000）。第二行是一个正整数）。第二行是一个正整数M，表示要加上去的小，表示要加上去的小整数（整数（1 = M = 100）。下一行是）。下一行是1到到N这这N个整数的一个排列，用空格个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。隔开，表示火星人手指的排列顺序。【输出文件【输出文件】输出文件输出文件martian.out只有一行，这一行含有只有一行，这一行含有N个整数，表示改变后的火星人个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格

32、。手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。【样例输入【样例输入】531 2 3 4 5【样例输出【样例输出】1 2 4 5 3【数据规模【数据规模】对于对于30%的数据，的数据，N=15；对于对于60%的数据，的数据，N=50；对于全部的数据，对于全部的数据，N0 do一次循环产生下一个排列一次循环产生下一个排列 begin j:=n; while (j1)and(ajaj-1 min:=aj; k:=j; for i:=j to n do if (aiaj-1)and(aiak then ss:=k; if ssi then begin temp:=ai; ai:

33、=ass; ass:=temp; end; end; 在在j到到n中，从小到大排列中，从小到大排列 m:=m-1; end; for i:=1 to n do 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相异元素不重复的组合相异元素不重复的组合 设从设从

34、n个不同的元素中，取出个不同的元素中，取出m个不同元素，个不同元素，不考虑不考虑顺序顺序并成一组，叫作从并成一组，叫作从n个不同的元素中，取出个不同的元素中，取出m个不同个不同元素的一个组合。元素的一个组合。如：写出从如：写出从a,b,c,d四个元素中，任取三个元素的所有组合。四个元素中，任取三个元素的所有组合。abc, abd, acd, bcd从从n个不同的元素中，取出个不同的元素中，取出m个不同元素的组合数记为个不同元素的组合数记为Cmn;则有则有CmnPmn/m!=n!/m!(n-m)!规定规定C0n=1abc,bac,cab,acb,bca,cba例例1、八年级八年级6个班进行排球比

35、赛，每班的排球队个班进行排球比赛，每班的排球队要与其他要与其他5个班分别比赛一场，求共要进行多少场个班分别比赛一场，求共要进行多少场比赛？比赛？C26P26/2!=6*5/2*1=15例例2、平面上有平面上有n个点且无三点或三点以上共线，任个点且无三点或三点以上共线，任意两点可以连成一条直线，一共能连成多少条直线？意两点可以连成一条直线，一共能连成多少条直线？ C2nn*(n-1)/2例例3、某班第一组有、某班第一组有10名同学，第二组有名同学，第二组有8名同学，现要求每名同学，现要求每组选出组选出2名学生代表参加座谈会，有多少种选法？名学生代表参加座谈会，有多少种选法？C210C281260

36、例例4.一元、二元、五元、十元人民币各一张，一共一元、二元、五元、十元人民币各一张，一共可以组成多少种不同的币值？可以组成多少种不同的币值？ C14C24C34C44464115例例5、5年级有年级有8个班，六年级有个班，六年级有6个班，先分别举行各年个班，先分别举行各年级的篮球赛，采用单循环制，然后由两个年级的第一名争级的篮球赛，采用单循环制，然后由两个年级的第一名争夺冠军，共需要比赛多少场？夺冠军，共需要比赛多少场？ C28C26+1=8*7/2+6*5/2+1=28+15+1=44例例6：某班第一组有：某班第一组有10名同学，其中有名同学，其中有4名女同学，现要名女同学，现要求选出求选出

37、3名学生代表名学生代表,其中至少有一名女同学去参加座谈其中至少有一名女同学去参加座谈会，有多少种选法？会，有多少种选法？ 代表中有代表中有1名女同学名女同学的选法为的选法为C14C26种，种， 代表中有代表中有2名女同学名女同学的选法为的选法为C24C16种，种， 代表中有代表中有3名女同学名女同学的选法为的选法为C34种，种，C14C26C24C16C34100例例7 7、欲登上第欲登上第1010级楼梯，如果规定每步只能跨级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有上一级或两级，则不同的走法共有( )( )。 例例8、A的一边的一边AB上有上有4个点，另一边个点，另一边AC上有上

38、有5个点，个点，连同连同A的顶点共的顶点共10个点，以这些点为顶点，可以构个点，以这些点为顶点，可以构成成_个三角形个三角形. 9090541452524CC例例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

39、+210=751例例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 例例11、10名划船运动员中，名划船运动员中，3人只会划

40、左舷，人只会划左舷，2人只会划人只会划右舷，右舷，5人左右舷都会划，从中选人左右舷都会划，从中选6人，平均分在左、右人，平均分在左、右舷，共有多少种不同的选法？舷，共有多少种不同的选法？ 1.会划左舷的全划左舷：会划左舷的全划左舷：35*3733CC300*362315CCC40*3435CC2.派一个全能划左舷：派一个全能划左舷：3.派二个全能划左舷：派二个全能划左舷：4.派三个全能划左舷：派三个全能划左舷：300*351325CCC675例例12、小陈现有小陈现有2个任务个任务A，B要完成，每个任务分别要完成，每个任务分别有若干步骤如下：有若干步骤如下：A=a1-a2-a3，B=b1-b2

41、-b3-b4-b5。在任何时候，小陈只能专心做某个任务的。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，个未做的步骤继续。每个任务的步骤顺序不能打乱，例如例如a2-b2-a3-b3是合法的，而是合法的，而a2-b3-a3-b2是不合法的。小陈从是不合法的。小陈从B任务的任务的b1步步骤开始做，当恰做完某个任务的某个步骤后，就停工骤开始做，当恰做完某个任务的某个步骤后，就停工回家

42、吃饭了。当他回来时，只记得自己已经完成了整回家吃饭了。当他回来时，只记得自己已经完成了整个任务个任务A，其他的都忘了。试计算小陈饭前已做的可，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有能的任务步骤序列共有 种。种。(2009年年p) 70 排列组合排列组合+加法原理加法原理:B任务中的任务中的b1一定做，而且肯定是第一个做的。除了一定做，而且肯定是第一个做的。除了b1外，外，第一类：完成第一类：完成A任务任务 只有只有1种。种。第二类：完成第二类：完成A任务和任务和b2 有有C(4,1)=4种。种。第三类：完成第三类：完成A任务和任务和b2、b3 有有C(5,2)=10种。种。第

43、四类：完成第四类：完成A任务和任务和b2、b3、b4 有有C(6,3)=20种。种。第五类：完成第五类：完成A任务和任务和b2、b3、b4、b5 有有C(7,4)=35种。种。加起来加起来1+4+10+20+35=70。b2 a1 a2 a3a1 b2 a2 a3a1 a2 b2 a3a1 a2 a3 b2 例例13、袋中有已编号的袋中有已编号的20个球，其中个球，其中110号是红球，号是红球，1120号是白球，每取得一个红球得号是白球，每取得一个红球得2分，取得一个分，取得一个白球得白球得3分，若取得若干个球，共得分，若取得若干个球，共得20分，有多少种分，有多少种不同取法？不同取法？2x+

44、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 C3,6,9,300 三个数同属于集合三个数同属于集合A，有，有C3100种，种， 三个数同属于集合

45、三个数同属于集合B，有，有C3100种，种， 三个数同属于集合三个数同属于集合C，有，有C3100种，种， 三个数分属于集合三个数分属于集合A，B，C，有，有1003种。加起来等于种。加起来等于 1485100种。种。例例15、若将一个正整数化为二进制数，在此二进制数中，若将一个正整数化为二进制数，在此二进制数中，我们将数字我们将数字0的个数多于数字的个数多于数字1的个数的这类二进制数称为的个数的这类二进制数称为A类数。类数。 例如：例如： （24）10=（11000）2 其中其中1的个数为的个数为2，0的个数为的个数为3，则称此数为，则称此数为A类数；类数； 请你求出请你求出1112之中（包

46、括之中（包括1与与112），全部），全部A类数类数的个数。的个数。 （112）10=（1110000）2可根据二进制数的前缀来分类。可根据二进制数的前缀来分类。111：这类数中：这类数中A类数只有一个，即类数只有一个，即1110000110：这类数中：这类数中A类数个数为：类数个数为： C44C34510：这类数中：这类数中A类数个数为：类数个数为： C55C45 C35 160：位数不确定，需对位数进行讨论。：位数不确定，需对位数进行讨论。1位数，即位数，即1,不是不是A类数，类数，2位数，即位数，即1，10和和11都不是都不是A类数，类数，3位数，即位数，即1，只有，只有100一个，一个，

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

48、答案为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

49、, 244, 444组合的生成算法组合的生成算法 从1,2,3,n共n个数中任取m个数，请输出所有组合并计算组合数。var n,m,i,k,s:integer; a,b:array0.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

50、do ; end else ; until k=0; writeln; writeln(s=,s);end. n-m+ik=mak:=ak+1ak:=ak-1+1k:=k-1Jam的计数法的计数法【问题描述【问题描述】 Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺

51、序，排在前面的字母小于排在它后面的字母。我们英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的把这样的“数字数字”称为称为Jam数字。在数字。在Jam数字中，每个字母互不相同，数字中，每个字母互不相同，而且从左到右是严格递增的。每次，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，还指定使用字母的范围，例如，从从2到到10，表示只能使用，表示只能使用b,c,d,e,f,g,h,i,j这些字母。如果再规定位这些字母。如果再规定位数为数为5，那么，紧接在，那么，紧接在Jam数字数字“bdfij”之后的数字应该是之后的数字应该是“bdghi”。（如果我们用（如果

52、我们用U、V依次表示依次表示Jam数字数字“bdfij”与与“bdghi”，则，则UV，且不存在且不存在Jam数字数字P，使，使UPV）。你的任务是：对于从文件读入的）。你的任务是：对于从文件读入的一个一个Jam数字，按顺序输出紧接在后面的数字，按顺序输出紧接在后面的5个个Jam数字，如果后面没有数字，如果后面没有那么多那么多Jam数字，那么有几个就输出几个。数字，那么有几个就输出几个。 【输入文件【输入文件】输入文件输入文件counting.in 有有2行，第行，第1行为行为3个正整数，用一个空格隔开：个正整数，用一个空格隔开：s t w（其中（其中s为所使用的最小的字母的序号，为所使用的最

53、小的字母的序号，t为所使用的最大的字母的序号。为所使用的最大的字母的序号。w为数字的位数，这为数字的位数，这3个数满足：个数满足：1st26, 2wt-s ） 第第2行为具有行为具有w个小写字母的字符串，为一个符合要求的个小写字母的字符串，为一个符合要求的Jam数字。数字。【输出文件【输出文件】输出文件输出文件counting.out 最多为最多为5行，为紧接在输入的行，为紧接在输入的Jam数字后面的数字后面的5个个Jam数字，如果后面没有那么多数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只数字，那么有几个就输出几个。每行只输出一个输出一个Jam数字，是由数字，是由w个小写字

54、母组成的字符串，不要有多余的空格。个小写字母组成的字符串，不要有多余的空格。【输入样例【输入样例】 2 10 5 bdfij【输出样例【输出样例】bdghibdghjbdgijbdhijbefghvar 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和生成个数清和生成个数

55、清0 while (a0=0)and(n0)do i:=i-1; inc(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

56、输出：i=1时,chr(97+1+2-2)=b bdghi排列组合题型总结排列组合题型总结 排列组合问题千变万化，解法灵活，条件隐晦，思维排列组合问题千变万化，解法灵活，条件隐晦，思维抽象，难以找到解题的突破口。因而在求解排列组合应用抽象，难以找到解题的突破口。因而在求解排列组合应用题时，除做到：题时，除做到：排列组合分清，加乘原理辩明，避免重复排列组合分清，加乘原理辩明，避免重复遗漏遗漏外，还应注意积累排列组合问题得以快速准确求解。外，还应注意积累排列组合问题得以快速准确求解。直接法直接法1.特殊元素法特殊元素法 用用1 1，2 2，3 3，4 4，5 5，6 6这这6 6个数字组成无重复的

57、四位数，试个数字组成无重复的四位数，试求满足下列条件的四位数各有多少个求满足下列条件的四位数各有多少个（1 1）数字）数字1 1不排在个位和千位不排在个位和千位; ;（2 2）数字）数字1 1不在个位，数字不在个位，数字6 6不在千位。不在千位。分析：（分析：（1 1）个位和千位有）个位和千位有5 5个数字可供选择个数字可供选择 ，其余，其余2 2位有四个可供选择位有四个可供选择 ，由乘法原理：，由乘法原理： =240=240 25A24A25A24A特殊元素，优先处理；特殊位置，优先考虑 。2.2.特殊位置法特殊位置法 （2 2）当）当1 1在千位时余下三位有在千位时余下三位有 =60=60

58、，1 1不在千位时，千位不在千位时，千位有有 种选法，个位有种选法，个位有 种，余下的有种，余下的有 ，共有，共有 =192,=192,所以总共有所以总共有192+60=252192+60=25235A14A14A24A间接法间接法当直接法求解类别比较大时，应采用间接法。如上例中当直接法求解类别比较大时，应采用间接法。如上例中（2 2）可用间接法）可用间接法 有五张卡片，它的正反面分别写有五张卡片，它的正反面分别写0 0与与1 1，2 2与与3 3，4 4与与5 5，6 6与与7 7，8 8与与9 9，将它们任意三张并排放在一起组成三位数，将它们任意三张并排放在一起组成三位数，共可组成多少个不

59、同的三位数？共可组成多少个不同的三位数？ 分析：此例正面求解需考虑分析：此例正面求解需考虑0 0与与1 1卡片用与不用，且用此卡片卡片用与不用，且用此卡片 又分使用又分使用0 0与使用与使用1 1，类别较复杂，因而可使用间接计算：任，类别较复杂，因而可使用间接计算：任 取三张卡片可以组成不同的三位数取三张卡片可以组成不同的三位数 个，其中个，其中0 0在在 百位的有百位的有 个，这是不合题意的。故共可组成不个，这是不合题意的。故共可组成不 同的三位数同的三位数 =432=432（个）（个）. .333352AC 8位同学排成一行，要求某两位同学互不相位同学排成一行，要求某两位同学互不相邻，有多

60、少种排法？邻，有多少种排法？8位同学排成一行的总数是位同学排成一行的总数是8！把排在一起的的两个同学看成一个人的排列总数是把排在一起的的两个同学看成一个人的排列总数是7！因为排在一起的两个同学的位置可以互换，所以两位因为排在一起的两个同学的位置可以互换，所以两位同学排在一起的排列数是同学排在一起的排列数是27！所以符合题意的个数为所以符合题意的个数为8！27！30240 正方体8个顶点中取出4个，可组成多少个四面体? 所求问题的方法数=任意选四点的组合数-共面四点的方法数， -12=70-12=58个。 48C插空法插空法 在一个含有在一个含有8个节目的节目单中，临时插入两个歌唱个节目的节目单