《排列组合专题》PPT课件

加法原理和乘法原理加法原理和乘法原理是排列组合的基础和核心，既可用来推导排列数、组合数公式，也可用来直接解题。它们的共同点都是把一个事件分成若干个分事件来进行计算。利用加法原理，重在分“类”，类与类之间具有独立性和并列性；利用乘法原理，重在分步；步与步之间具有相依性和连续性。比较复杂的问题，常先分类再分步。1.加法原理:如果完成一项工作有两类相互独立的方式A和B,在方式A中有m种完成任务的途径,在方式B中有n种完成任务的途径,则完成这项工作的总的途径有m+n种.2.乘法原理:如果完成一项工作有两个连续的步骤A和B,在步骤A中有m种不同的方式,在步骤B中有n种不同的方式,则完成这项工作的总的方法有m*n种.例1、从1到4这4个数码中不重复地任取3个构成一个三位数,求这样的三位数一共有多少个?分析:构成三位数的过程可以看成是由连续的三步完成:第一步:取百位上的数字,共有4种方法第二步:取十位上的数字,共有3种方法(即不能取百位上已经取走的数码)第三步:取个位上的数字,共有2种方法(即不能取百位和十位上已经取走的数码)因此由乘法原理,这样的三位数一共有:4*3*2=24种.例2、一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它“吃掉”后一个三位数，例如543吃掉432，543吃掉543，但是543不能吃掉534。那么能吃掉587的三位数共有多少个？百位上有5、6、7、8、9五种选择，十位上有8、9两种选择，个位上有7，8，9三种选择，所以共有5×2×3=30（个）三位数。例3、如图，一方形花坛分成编号为①，②，③，④四块，现有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色的花，且相邻的两块种不同颜色的花。如果编号为①的已经种上红色花，那么其余三块不同的种法有种。21编号为②的有三种选择，对于编号为③的，可以分成以下二类：1、若编号为④的与编号为②的同色，则编号为③的有三种选择。这种情况下共有3×3种方案。2、若编号为④的与编号为②的不同色，则编号为③的有二种选择，编号为④的有二种选择。这种情况下共有3×2×2种方案。例4、用红、黄、绿、蓝、黑五种颜色涂在如下图所示的ABCDE五区域，颜色可重复使用，但同色不相邻，涂法有几种？AC同色:5*4*4*1*4AC不同色:5*4*4*3*31040例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＝13＞10，所以10人中必有3人既会英语又会日语。（5+2+3）所以可分三类：5×2+5×3+2×3=31例7、在所有的三位数中，有且只有两个数字相同的三位数共有多少个?（1）△△□，（2）△□△，（3）□△□，（1），（2），（3）类中每类都是9×9种，共有9×9+9×9+9×9＝3×9×9＝243个只有两个数字相同的三位数。例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．例9、从1到300的自然数中，完全不含有数字3的有多少个？将0到299的整数都看成三位数，其中数字3不出现的，百位数字可以是0，1或2三种情况。十位数字与个位数字均有九种，因此除去0共有3×9×9－1=242(个)．例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个．排列的定义数学上，把若干元素，按照任何一种顺序排成一列，叫做排列。如果两个排列满足下列条件之一，它们就被认为是不同的排列：1.所含元素不全相同2.所含元素相同，但顺序不同。相异元素不重复的排列从n个不同的元素中，取出r个不重复的元素，按次序排成一列，当rn时，称为从n个中取r个的一种选排列。如：从a,b,c这三个字母中，每次取出2个，有多少种排列方法?第一步：确定左边的字母，在三个字母中任取一个，有３种方法；第二步：确定右边的字母，从剩下的２个字母中选取一个，有２种方法；根据乘法原理，共有３×２＝６种不同的排法.abacbabccacb一般地，从n个不同的元素中取出r个元素的选排列数用表示，则＝n!/(n-r)!rnPrnP例１．全国足球甲级（Ａ组）联赛共有１４队参加，每队都要与其它各队在主、客场分别比赛一次，共进行多少场比赛？任何二个队进行一次主场比赛和一场客场比赛，相当于从14个元素中任取2个元素的一个排列，共需进行的比赛场次是=14!/12!=14*13=182214P当n=r时,叫做n个不同元素的全排列．n个不同元素的全排列数Pnn＝n!例２．３个人站成一排照相，共有多少种不同的排列方法？＝３!＝６33P例3、求有多少个没有重复数字且能被5整除的四位奇数。要能被5整除又是奇数，所以个位上数字只能是5,有1种选法，由于5已用过，又不可能是0,所以千位上数有P18种选法,已用过2个数，所以百位、十位上的数有P28种选法。所以符合题意的个数为：1×P18×P28＝448例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例5、8位同学排成相等的两行，要求某两位同学必须排在前排，有多少种排法？这两个同学排在前排4个位置的排列数是P24，其它同学在余下的6个位置排的排列数是6！，所以符合题意的个数为P24×6！＝12×720＝8640。例6、某车站有编号为1到6的6个入口处，每个入口处每次只能进一人，问一个小组4人进站的方案有几种？第一个人有6种方案，第二个人有7种方案，因为他选择和第一个人相同入口处时，还有前后之分……9*8*7*6=3024o︱︱o︱︱o︱o在两个入口之间加一个标志︱，共5个无区别的标志，问题归结为9个元素中有5个无区别的元素，4个不同元素的排列数。所以4个人进站的方案数有：9！/5！＝9*8*7*6=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．有男女各五个人，其中有３对是夫妻，沿圆桌就座，若每对夫妻都坐在相邻的位置，问有多少种坐法？设３对夫妻分别为Ａ和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时有种不同排法?7!/(4!*3!)=35NOIP2002例11、把两个红球、一个蓝球和一个白球放到十个编号不同的盒子中去，有多少种方法？排列数为p410/(2!*1!*1!)＝2520生成排列的算法下面程序的功能是利用递归方法生成从1到n(n10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）：123132213231321312求全排列(06年初赛题)vari,n,k:integer;a:array[1..10]ofinteger;count:longint;procedureperm(k:integer);varj,p,t:integer;beginif()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;123132213231321312算法过程:用数组：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年提高组}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:=__________dobeginj:=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