计数问题竞赛讲义一

1、计数问题竞赛讲义一一分类加法计数原理与分步乘法计数原理1.分类加法计数原理 完成一件事情，有类不同方案，在第1类方案中有种不同的方法，在第2类方案中有种不同的方法在第类方案中有种不同的方法.那么完成这件事共有种不同的方法.说明：分类加法计数原理针对的是“分类”问题，完成一件事要分为若干类，各类的方法相互独立，各类中的各种方法也相对独立，用任何一类中的任何一种方法都可以单独完成这件事.2.分步乘法计数原理 完成一件事情，需要个步骤，做第1步有种不同的方法，做第2步有种不同的方法做第步有种不同的方法.那么完成这件事共有种不同的方法.说明：分步计数原理针对的是“分步”问题，完成一件事要分为若干步，各

2、个步骤相互依存，完成任何其中的一步都不能完成该件事，只有当各个步骤都完成后，才算完成这件事.3.理解分类加法计数原理与分步乘法计数原理异同点相同点：都是完成一件事的不同方法种数的问题不同点：分类加法计数原理针对的是“分类”问题，完成一件事要分为若干类，各类的方法相互独立，各类中的各种方法也相对独立，用任何一类中的任何一种方法都可以单独完成这件事，是独立完成；而分步乘法计数原理针对的是“分步”问题，完成一件事要分为若干步，各个步骤相互依存，完成任何其中的一步都不能完成该件事，只有当各个步骤都完成后，才算完成这件事，是合作完成.4.运用分类加法计数原理与分步乘法计数原理的注意点：首先要确定“完成一

3、件什么事”，然后确定怎样去完成？（即需要“分类”还是“分步”）分类加法计数原理：首先确定分类标准，其次要保证分类时做到“不重不漏”。分步乘法计数原理：首先确定分步标准，其次要保证“步骤完整”，即必须并且只需连续完成这个步骤，这件事才算完成.【例题选讲】例1 .在120共20个整数中取两个数相加,使其和为偶数的不同取法共有多少种? 使其和大于20的不同取法又共有多少种?解:（1）取与取是同一种取法.分类标准为两加数的奇偶性,第一类,偶偶相加,由分步计数原理得(10×9)/2=45种取法,第二类,奇奇相加,也有(10×9)/2=45种取法.根据分类计数原理共有45+45=90种

4、不同取法.（2）分类标准一,固定小加数.小加数为1时,大加数只有20这1种取法;小加数为2时,大加数有19或20两种取法;小加数为3时,大加数为18,19或20共3种取法小加数为10时,大加数为11,12,20共10种取法;小加数为11时,大加数有9种取法小加数取19时,大加数有1种取法.由分类计数原理,得不同取法共有1+2+9+10+9+2+1=100种.分类标准二:固定和的值.有和为21,22,39这几类,依次有取法10,9,9,8,8, ,2,2,1,1种.由分类计数原理得不同取法共有10+9+9+2+2+1+1=100种.例2. 如图,共有多少个不同的三角形?解:所有不同的三角形可分为

5、三类”第一类:其中有两条边是原五边形的边,这样的三角形共有5个第二类:其中有且只有一条边是原五边形的边,这样的三角形共有5×4=20个第三类:没有一条边是原五边形的边,即由五条对角线围成的三角形,共有5+5=10个由分类计数原理得,不同的三角形共有5+20+10=35个.二排列与组合1.排列：从个不同元素中取出个元素，按照一定的顺序排成一列，叫做从个不同元素中取出个元素的一个排列。2.排列数：从个不同元素中取出个元素的所有不同排列的个数叫做从个不同元素中取出个元素的排列数，用符号表示。3. 排列数公式：，4.组合：从个不同元素中取出个元素合成一组，叫做从个不同元素中取出个元素的一个组

6、合。5.组合数：从个不同元素中取出个元素的所有不同组合的个数，叫做从个不同元素中取出个元素组合数。6. 组合数公式：，7解排列、组合题的基本策略与方法（1）合理分类与准确分步 （2）有序排列，无序组合 （3）排列、组合混合问题先选后排 （4）特殊元素、特殊位置优先 （5）正难则反，等价转化 （6）相邻问题捆绑处理（7）不相邻问题插空处理策略（8）定序问题除法处理（9）分排问题直排处理（10）构造模型的策略【基础题型选讲】例1用数字0、1、2、3、4、5组成无重复数字。（1）可以组成多少个六位数？ （2）可以组成多少个四位奇数？（3）可以组成至少有一个偶数数字的三位数多少个？（4）可以组成多少个

7、能被3整除的四位数？ （5）可以组成多少个大于324105的六位数？解：（1）从特殊元素0入手，0不能排在十万位，0有种排法，剩下的5个数字可排在5个数位下，有种，故可组成个六位数。从特殊位置十万位入手，有种排法，剩下的五个位置有种，故可组成个六位数。六个数字可组成个“六位数”（其中包括0在十万位的情形），而0在最高位上的“六位数”应扣除，有个，故共有个六位数。（2）从特殊位置入手，个位上有种排法，首位上有种排法，中间两位上有种排法，故共有个；从特殊元素入手，可分为两类，含数字0的有个，不含有数字0的有个，故共有四位奇数个。采用去杂法， 个位是奇数的数共有个，其中不合条件的（0在首位）有个，故

8、符合条件的四位奇数共有个。（3）分类：如果有0，则0可排在个位或十位有2种，其余5个数字可排在二个数位上有种，所以有个三位数；如果无0，则2、4中可选出1个有2种，再从其余3个奇数中选出2个有种，然后将3个数字全排列有种，所以有个二位数，如果无0，则2、4中可选出2个有1种，再从其余3个奇数中选出1个有3种，然后将3个数字全排列有种，所以有个三位数，共有个。三位数共有个，但其中三个数字都不是偶数即均为奇数的有个，故至少含有一个偶数的三位数有个。注：（3）中解法一（选化法）显然比第二种解法（去杂法）烦。（4）一个整数能被3整除的充要条件是它的各位数字之和是3的倍数，符合条件的有5组数：0、1、2

9、、3；0、2、3、4；0、3、4、5；0、1、3、5；1、2、4、5；前4组每组组成的四位数各有个，后一组组成的四位数有个，故可组成能被3整除的四位数有个。（5）采用去杂法，六位数共有个，不大于324105的数列如3240××有2个；321×××与320×××有个；31××××与30××××有个；324105 1个；2×××××与1××××

10、5;有个，所以满足条件的六位数共有个。采用选化法，符合条件的是形如5×××××和4×××××的数有个；35××××和34××××的数有个；325×××的数有个；3245××的数有个，还有1个324150，故符合条件的六位数共有个。例2七个人排成一排，按下列要求的有多少种排法？（1）其中甲不站排头； （2）其中甲不站排头，乙不站排尾；（3）其中甲、乙两人必须相邻； （4

11、）其中甲、乙两人必须不相邻；（5）甲乙相邻，丙丁不相邻； （6）甲乙不相邻，丙丁不相邻；（7）其中甲、乙中间有且只有1人； （8）其中甲必须排在乙的右边；（9）前排3人，后排4人； （10）甲站前排，乙站后排变式：（1）要排一个有5个独唱节目和3个舞蹈节目的节目单，如果舞蹈节目不排在开头，并且任意两个舞蹈节目不排在一起，则不同的排法种数有（ ）A B C D（2）从6名运动员中选出4个参加接力赛，如果甲不跑第一棒，乙不跑第四棒，共有 种不同的参赛方法。（3）现安排甲、乙、丙、丁、戌5名同学参加上海世博会志愿者服务活动，每人从事翻译、导游、礼仪、司机四项工作之一，每项工作至少有一人参加。甲、乙不

12、会开车但能从事其他三项工作，丙丁戌都能胜任四项工作，则不同安排方案的种数是（ ）A152 B.126 C.90 D.54（4）某单位安排7位员工在10月1日至7日值班，每天1人，每人值班1天，若7位员工中的甲、乙排在相邻两天，丙不排在10月1日，丁不排在10月7日，则不同的安排方案共有A. 504种 B. 960种 C. 1008种 D. 1108种 【答案】C解析：分两类：甲乙排1、2号或6、7号 共有种方法甲乙排中间,丙排7号或不排7号，共有种方法故共有1008种不同的排法（5） 用1，2，3，4，5，6组成六位数（没有重复数字），要求任何相邻两个数字的奇偶性不同，且1和2相邻，这样的六位

13、数的个数是_（用数字作答)。（6） 用1，2，3，4，5，6,7,8组成没有重复数字的八位数，要求1与2相邻， 3与4相邻，5与6相邻，而7与8不相邻，这样的八位数共有 个（用数字作答）例3从6男4女中，选出5人，按下列要求的有多少种不同的选法？（1）甲必须当选； （2）乙不能当选；（3）甲当选一不当选；（4）至少1名女生至少2名男生，变式：（1）某班级有20名男生和18名女生，从这38名学生中任选4名参加一个“Party”。（1）其中恰有2名女生的选法有多少种？ （2）其中至少有2名女生的选法有多少种？解：（1）（2）分3类：4人中无女生：；4人中恰有1女生；4人中恰有2女生，故共有种（2）

14、某餐厅供应客饭，每位顾客可以在餐厅提供的菜肴中任选2荤2素共4种不同的品种，现在餐厅准备了5种不同的荤菜，若要保证每位顾客有200种以上的不同选择，则餐厅至少还需准备不同的素菜品种 种（3）5个身高不等的学生站成一排合影，从中间到两边一个比一个矮的排法有（ ）种 A. 6 B. 8 C. 10 D.12（4）如果一条直线与一个平面平行，那么称此直线与平面构成一个“平行线面组”，在一个长方体中，由两个顶点确定的直线与含有四个顶点的平面构成的“平行线面组”的个数是（ ） A. 60 B.48 C. 36 D.24例4从0 到9这10个数字中选出3个偶数和2个奇数（1）可组成多少个没有重复数字的5位

15、数？（2）可组成多少个没有重复数字的被5整除的5位数？变式：（1）25人排成5×5方阵，从中选出3人分别担任三种不同的职务，要求这3人既不同行也不同列，则不同的任职方法有多少种？（3600）（2）某地奥运火炬接力传递路线共分6段，传递活动分别由6名火炬手完成如果第一棒火炬手只能从甲、乙、丙三人中产生，最后一棒火炬手只能从甲、乙两人中产生，则不同的传递方案共有 种（用数字作答）（3）四棱锥的8条棱代表8种不同的化工产品,有公共点的两条棱代表的化工产品放在同一仓库是危险的,没有公共顶点的两条棱代表的化工产品放在同一仓库是安全的,现打算用编号为、的4个仓库存放这8种化工产品,那么安全存放的

16、不同方法种数为( ) A.96 B.48 C.24 D.0（4）以集合的子集中选出4个不同的子集，需同时满足以下两个条件：（1）都要选出；（2）对选出的任意两个子集和，必有或，那么共有 种不同的选法。例5.（从集合角度） 10人组成的篮球队中，有5人只适于打锋，3人只适于打卫，2人打锋打卫即可，现选5人参加比赛3锋2卫，问共有多少种不同的选择？ 例6.（1） 以正方体的顶点为顶点的四面体共有 个。（2）四面体的顶点和各棱中点共10点，在其中取4个不共面的点，不同的取法共有 种（141）（3）变式：四面体的一个顶点为，从其他顶点与棱的中点中取3个点，使它们和点在同一个平面上，则不同的取法有 种（

17、33）例变式：（1）如图2-1,共有 个不同的矩形? 如图2-2,共有 个不同的直角三角形? 如图2-3,从A到B有 种不同的走法？（2）在正方体的8个顶点中，能构成一个直角三角形的3个顶点的直角三角形的个数为 .*（3）一个圆周上共有10个不同的点，试问：这10个点可构成 弦；这些弦可以构成 个不同的交点；这些弦又可以构成 个不同的直角三角形？ 个不同的锐角角三角形？ 个不同的钝角角三角形？（4）在xOy平面上，顶点坐标（x,y）满足且x,y取整数的三角形有多少个？ 例3 .75600有多少个正约数?有多少个奇约数?解:75600的约数就是能整除75600的整数,所以本题就是分别求能整除75

18、600的整数和奇约数的个数. 由于 75600=24×33×52×7。(1) 75600的每个约数都可以写成的形式,其中,。于是,要确定75600的一个约数,可分四步完成,即分别在各自的范围内任取一个值,这样有5种取法,有4种取法,有3种取法,有2种取法,根据分步计数原理得约数的个数为5×4×3×2=120个.(2)奇约数中步不含有2的因数,因此75600的每个奇约数都可以写成的形式,同上奇约数的个数为4×3×2=24个.例4.（排数问题）用0，1，2，3，4，5这六个数字，（1） 可以组成多少个数字不重复的三位数

19、？（2） 可以组成多少个数字允许重复的三位数？（3） 可以组成多少个数字不允许重复的三位数的奇数？（4） 可以组成多少个数字不重复的小于1000的自然数？（5） 可以组成多少个大于3000，小于5421的数字不重复的四位数？解（1）分三步：先选百位数字由于0不能作百位数，因此有5种选法；十位数字有5种选法； 个位数字有4种选法由乘法原理知所求不同三位数共有5×5×4=100个（2）分三步：(1)百位数字有5种选法；(ii)十位数字有6位选法；(iii)个位数字有6种选法。 所求三位数共有5×6×6=180个（1） 分三步：先选个位数字，有3种选法；再选百位数字，有4种选法；选十位数字也是4种选法，所求三位奇数共有3×4×4=48个（2） 分三类：一位数，共有6个；两位数，共有5×5=25个；三位数共有5×5×4=100个因此，比1000小的自然数共有6+25+100=131个（3） 分4类：千位数字为3，4之一时，共有2×