分类计数原理与分步计数原理

分类计数原理与分步计数原理一、知识精讲分类计数原理与分步计数原理分类计数原理：做一件事，完成它可以有n类办法，在第一类办法中有1m种不同的方法，在第二类办法中有2m种不同的方法，……，在第n类办法中有nm种不同的方法，那么完成这件事共有nmmmN21种不同的办法。分步计数原理：做一件事，完成它需要分成n个步骤，做第一步有1m种不同的方法，做第二步有2m种不同的方法，……，做第n步有nm种不同方法，那么完成这件事共有nmmmN21种不同的方法。特别注意:两个原理的共同点是把一个原始事件分解成若干个分事件来完成。不同点在于，一个与分类有关，一个与分步有关，如果完成一件事情共有n类办法，这n类办法彼此之间相互独立的，无论哪一类办法中的哪一种方法都能单独完成这件事情，求完成这件事情的方法种数，就用分类计数原理；如果完成一件事情需要分成n个步骤，各个步骤都是不可缺少的，需要依次完成所有的步骤，才能完成这件事，而完成每一个步骤各有若干种不同的方法，求完成这件事情的方法种数就用分步计数原理。二、例题例1、把一个圆分成3块扇形，现在用5种不同的颜色给3块扇形涂色，要求相邻扇形的颜色互不相同，问有多少钟不同的涂法？若分割成4块扇形呢？解：（1）不同涂色方法数是：60345（种）（2）如右图所示,分别用a,b,c,d记这四块,a与c可同色,也可不同色,先考虑给a,c两块涂色,分两类(1)给a,c涂同种颜色共15C种涂法,再给b涂色有4种涂法,最后给d涂色也有4种涂法,由乘法原理知,此时共有4415C种涂法(2)给a,c涂不同颜色共有25A种涂法,再给b涂色有3种方法,最后给d涂色也有3种，此时共有3325A种涂法故由分类计数原理知，共有4415C+3325A=260种涂法。例2、甲、乙、丙、丁四个公司承包8项工程，甲公司承包3项工程，乙公司承包1项，丙、丁各承包2项，问共有_____________种承包方式？解：由分步计数原理有：168022241538CCCC种。思维点拔【思维点拔】解决这类题首先要明确：“完成一件事”指什么？如何完成这件事（即分步还是分类）？进而确定应用分类计数原理还是分步计数原理。dcab分步计数原理中的“分步”程序要正确。“步”与“步”之间是连续的,不间断的,缺一不可。分类计数原理中的“分类”要全面,不能遗漏。“类”与“类之间是并列的、互斥的、独立的,也就是说,完成一件事情,每次只能选择其中的一类办法中的某一种方法。例3电视台在”欢乐今宵”节目中拿出两个信箱,其中存放着先后两次竞猜中成绩优秀的观众来信,甲信箱中有30封,乙信箱中有20封.现有主持人抽奖确定幸运观众,若先确定一名幸运之星,再从两信箱中各确定一名幸运伙伴,有多少种不同的结果?解:(1)幸运之星在甲箱中抽,再在两箱中各定一名幸运伙伴,有30×29×20=1740种结果;(3)幸运之星在乙箱中抽,同理有20×19×30=11400种结果。由分类计数原理,共有17400+11400=28800种不同结果。【评述】在综合运用两个原理时，一般先分类再分步。例4从集合{1，2，3，，10中，选出由5个数组成的子集，使得这5个数中的任何两个数的和不等于11，这样的子集共有多少个？解：和为11的数共有5组：1与10，2与9，3与8，4与7，5与6，子集中的元素不能取自同一组的两数，，即子集中的元素取自5个组中的一个数，而每个数的取法有2种，所以子集个数为22222=25=32【评述】本题的关键是先找出和为11的5组数，然后利用分步计数原理求出结果。练习题：在一个正六边形的六个区域栽种观赏植物（如图），要求同一块中种同一种植物，相邻的两块种不同的植物，现有4种不同的植物可供选择，则有多少种栽种方案？解：考虑A、C、E种同一种植物，此时共有1083334种方法。考虑A、C、E种二种植物，此时共有432223324A种方法。考虑A、C、E种同三种植物，此时共有19222234A种方法。故总计有108+432+192=732种方法。三、小结：1．分类计数原理和分步计数原理是解决排列、组合问题的理论基础。这两个原理的本质区别在于分类与分步，分类用分类计数原理，分步用分步计数原理。2．元素能重复的问题往往用计数原理。3．注意：“类”间相互独立，“步”间相互联系。排列一、内容归纳1知识精讲：（1）排列:从n个不同的元素中取出m个(m≤n)元素并按一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.（2）排列数:从n个不同的元素中取出m个(m≤n)元素的所有排列的个数.（3）排列数公式:)1()2)(1(mnnnnAmn)!(!mnn.nnA)!1(!nnn规定0！=12重点难点:正确区分排列与组合,熟练应用公式计算排列数3思维方式:分类讨论的思想.4特别注意：排列数公式的连乘形式常用于计算，公式的阶乘形式常用于化简与证明.二、例题：例1、有7名学生站成一排,下列情况各有多少种不同的排法。（1）甲、乙必须排在一起;（2）若甲不在排头，乙不在排尾;（3）甲、乙、丙互不相邻;（4）甲、乙之间须隔一个人;（5）若甲必须在乙的右边（可以相邻，也可以不相邻），有多少种站法？（6）若将7人分成两排，前四后三，有多少种站法？解：（1）(捆绑法)14406622AA；(2)37202556677AAA；(3)(插空法)14403544AA;(4)1200552215AAC;(5)25202177A;(6)504077A【思维点拨】对于相邻问题，常用“捆绑法”；对于不相邻问题，常用“插空法”（特殊元素后考虑）；对于“在”与“不在”的问题，常常使用“直接法”或“排除法”，（特殊元素先考虑）。例2、用0~9这十个数字组成没有重复数字的正整数（1）共有几个三位数?（2）末位数字是4的三位数有多少？（3）求所有三位数的和;（4）四位偶数有多少？（5）比5231大的四位数有多少？解：(1)百位不能为“0”,因此共有6482919AA个;（2）末位为4,百位不能为“0”,因此共有18A×18A=64个（3）考虑各数位上的数字之和,可得所有三位数的和为:)921(1818AA10)921(1818AA100)921(29A355680（4）分末位数字是否为0两种情况考虑。229628181439AAAA种；（5）①千位上为9,8,7,6的四位数各有39A个;②千位上是5,百位上为3,4,6,7,8,9的四位数各有28A个;③千位上是5,百位上为2,十位上为4,6,7,8,9的四位数各有17A个;④千位上是5,百位上为2,十位上为3且满足要求的共有5个,因此共有5564172839AAAN2392种。【思维点拨】注意区分分类计数原理与分步计数原理的运用。练习:由0,1,2,3,4,5共六个数字组成没有重复数字的六位数,问其中小于50万又不是5的倍数的数共有几个?解:先将0和5放到中间4个数位上,然后再排其他数字,故共有2884424AA个数符合要求.例3：一天要排语文、数学、英语、生物、体育、班会六节课（上午四节，下午二节），要求上午第一节不排体育，数学课排在上午，班会课排在下午，问共有几种不同的排课方法？解法一:（从数学课入手）（第一类）数学排在第一节，班会课排在下午，其余四科任排，得4844121AAN（第二类）数学排在上午另三节中的一节，班会排在下午，体育排在余下（不会第一节）三节中的一节，其余三科任排，得10833131213AAAA共有排法1561084821NNN（种）解法二（从体育课入手）（第一类）体育课在上午108331213131AAAAN（第二类）体育课在下午4844222AAN共有排法1564810821NNN（种）【思维点拨】注意特殊的位置和特殊的元素先考虑。三、小结1．对有约束条件的排列问题，应注意如下类型：⑴某些元素不能在或必须排列在某一位置；⑵某些元素要求连排（即必须相邻）；⑶某些元素要求分离（即不能相邻）；2．基本的解题方法：⑴有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；⑵某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为“捆绑法”；⑶某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为“插空法”；⑷在处理排列问题时，一般可采用直接和间接两种思维形式，从而寻求有效的解题途径。组合一、内容归纳1、知识精讲(1)组合从n个不同元素中，任取m(m≤n)个元素并组成一组，叫做从n个不同元素中取出m个元素的一个组合。(2)组合数从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符合Cmn表示。组合数公式为Cmn=mmmnAA=!)1()2)(1(mmnnnn这里，m，n∈N*，并且m≤n，组合数公式还可以写成Cmn=)!(!!mnmn规定C0n=1(3)组合数的性质①Cmn=Cmnn②Cmn1=Cmn+C1mn2、重点难点：组合概念的理解及应用3、思维方式：与排列问题进行类比思考4、特别注意：分类时标准应统一，否则易出现遗漏和重复二、例题例1、某外语组有9人,每人至少会英语和日语中的一门,其中7人会英语,3人会日语,从中选出会英语与日语的各1人,有多少种不同的选法？解：由于7＋3=10＞9，所以9人中必有1人既会英语又会日语．①从只会英语的6人中选1人，只会日语的2人中选1人，有N1=6×2=12②既会英语又会日语的那位选定，其余8人中选1人，有N2=1×8=8由分类记数原理得N=N1+N2=20例2、从1，2，…，30这前30个自然数中，每次取不同的三个数，使这三个数的和是3的倍数的取法有多少种？解：令A＝{1，4，7，10，…，28}，B＝{2，5，8，11，…29}，C＝{3，6，9，…，30}组成四位数的方式有以下四类符合题意：①A，B，C中各取一个数，有110110110CCC种；②仅在A中取3个数，有310C种；③仅在B中取3个数，有310C种；④仅在C中取3个数，有310C种，故由加法原理得：3101101101103CCCC＝1360种．【评述】按元素的性质分类是处理带限制条件的组合问题的常用方法，对于某几个数的和能被某数整除一类的问题，通常是将整数分类，凡余数相同者归同一类．例3、马路上有编号为1，2，3，…，10的十只路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法有多少种？解：问题等价于在七只亮着的路灯产生的六个空档中放入三只熄掉的路灯，因此，所求的方法种数为C36=20【思维点拔】注意插空法的应用。解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决。三、小结：1、组合数公式有两种形式，(1)乘积形式；(2)阶乘形式。前者多用于数字计算，后者多用于证明恒等式，注意公式的倒用。即由)!(!!mnmn写出Cmn。2、解受条件限制的组合问题，通常有分组法和排除法。3、排列问题类似，除注意两个计数原理的运用外，还要恰当地选择直接法或间接法。排列组合综合题：对某种产品的6件不同正品和4件不同次品一一进行测试，至区分出所有次品为止，若所有次品恰好在第5次测试时被全部发现，则这样的测试方法有多少种可能?解：第5次必测出一次品，余下3件次品在前4次被测出，从4件中确定最后一件次品有14C种方法，前4次中应有1件正品、3件次品，有3316CC种，前4次测试中的顺序有44A种，由分步计数原理即得：14C（3316CC）44A＝576。