计数问题竞赛讲义一.docVIP

计数问题竞赛讲义一 一．分类加法计数原理与分步乘法计数原理 1.分类加法计数原理 完成一件事情有类在第类有种不同的方法在第类有种不同的方法……在第类有种不同的方法完成这件事共有种不同的方法完成一件事情个步骤，做第1步有种不同的方法第有种不同的方法……第有种不同的方法完成这件事共有种不同的方法分类首先确定分类标准其次不重不漏分步首先确定分步标准其次必须并且只需连续完成这个步骤这件事才算完成.与取是同一种取法.分类标准为两加数的奇偶性,第一类,偶偶相加,由分步计数原理得(10×9)/2=45种取法,第二类,奇奇相加,也有(10×9)/2=45种取法.根据分类计数原理共有45+45=90种不同取法. （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×4=20个 第三类:没有一条边是原五边形的边,即由五条对角线围成的三角形,共有5+5=10个 由分类计数原理得,不同的三角形共有5+20+10=35个. 二．排列与组合 1.排列：从个不同元素中取出个元素，按照一定的顺序排成一列，叫做从个不同元素中取出个元素的一个排列。 2.排列数：从个不同元素中取出个元素的所有不同排列的个数叫做从个不同元素中取出个元素的排列数，用符号表示。 3. 排列数公式：， 4.组合：从个不同元素中取出个元素合成一组，叫做从个不同元素中取出个元素的一个组合。 5.组合数：从个不同元素中取出个元素的所有不同组合的个数，叫做从个不同元素中取出个元素组合数。 6. 组合数公式：， 7．解排列、组合题的基本策略与方法 （1）合理分类与准确分步 （2）有序排列，无序组合 （3）排列、组合混合问题先选后排 （4）特殊元素、特殊位置优先（5）正难则反，等价转化 （6）相邻问题捆绑处理 （7）不相邻问题插空处理策略（8）定序问题除法处理（9）分排问题直排处理（10）构造模型的策略种排法，剩下的5个数字可排在5个数位下，有种，故可组成个六位数。 从特殊位置十万位入手，有种排法，剩下的五个位置有种，故可组成个六位数。 六个数字可组成个“六位数”（其中包括0在十万位的情形），而0在最高位上的“六位数”应扣除，有个，故共有个六位数。 （2）从特殊位置入手，个位上有种排法，首位上有种排法，中间两位上有种排法，故共有个； 从特殊元素入手，可分为两类，含数字0的有个，不含有数字0的有个，故共有四位奇数个。 采用去杂法， 个位是奇数的数共有个，其中不合条件的（0在首位）有个，故符合条件的四位奇数共有个。 （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、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×××××有个，所以满足条件的六位数共有个。 采用选化法，符合条件的是形如①5×××××和4×××××的数有个；②35××××和34××××的数有个；③325×××的数有个；④3245××的数有个，还有1个324150，故符合条件的六位数共有 个。 例2．七个人排成一排，按下列要求