分类加法计数原理和分步乘法计数原理3.ppt

1.1分类加法计数原理 和分步乘法计数原理（3）,分类加法计数原理的推广,完成一件事有 n 类不同的方案，,在第1类方案中有 m1 种不同的方法，,在第2类方案中有 m2 种不同的方法，,那么完成这件事共有 种不同的方法。, ,在第n类方案中有mn种不同的方法，,分步乘法计数原理的推广,完成一件事有 n 类不同的方案，,在第1步有 m1 种不同的方法，,在第2步有 m2 种不同的方法，,那么完成这件事共有 种不同的方法。, ,在第n步有mn种不同的方法，,两个计数原理,用来计算“完成一件事”的方法种数,每类方案中的每一种方法都能_ 完成这件事,每步_才算完成这件事情 （每步中的每一种方法不能独立完成这件事）,类类相加,步步相乘,类类独立,步步相依,独立,依次完成,不重不漏,步骤完整,分类完成,分步完成,典型例题,类型一：分类加法计数原理问题,例1 已知两条异面直线a,b上分别有5个点和8个点，则经过这13个点可以确定几个不同的平面？,分两类：第一类，直线a和直线b上的8个点中每一个点确定一个平面，有8个不同的平面；第二类，直线b与直线a上的5个点中每一个点确定一个平面，有5个不同的平面。根据分类加法计数原理，共有8+5=13个不同的平面。,巩固练习,三边长均为正数，且最大边长为11的三角形个数是多少？,所以，不同三角形个数为：1+2+3+4+5+6+5+4+3+2+1= 36,类型二：分步乘法计数原理,第一步，x在集合2，3，7中选一个值，有3种方法 第二步，y在集合-31，-24,4中选一个值，有3种方法 所以有3*3=9种不同的值。,练习2,A=-1,0,1，B=2,3,4,5,7，若f表示从集合A到B的映射，那么满足x+f(x)+xf(x)的奇数的映射有 个,解: 当x=-1时，x+f(x)+xf(x)=-1，为奇数，即f(x)可以为B中任意值，有5种选择 当x=0时， x+f(x)+xf(x)=f(x)，要使f(x)为奇数，则f(x)=3,5,7，有三种选择 当x=1时， x+f(x)+xf(x)=1+2f(x)，一定为奇数，所以f(x)可以为B中任意值，有5种选择,类型三：排数字问题,例3 由数字0,1,2,3,4,5组成的没有重复数字的六位数，其中个位数小于十位数的共有（ ） A.210种 B.300种 C.464种 D.600种,B,分5类 第一类：个位数为0时，分5不排前5位数字，共有54 3 2 1=120种排法 第二类：个位数为1时，先排0，只能排在百、千、万位，有三种排法，其余4个数字排在4个位置上，分四步，共有3 4 3 2 1=72种排法 第三类：个位数为2时，先排0，只能排在百、千、万位，有三种排法，再排十位数字，有3种排法，其余3个数排在三个位置上，分三步，共有3 3 3 2 1=54种排法 第四类：个位数为3时，先排0，只能排在百、千、万位，有3种排法，再排十位数字，有2种排法，其余3位数字排在3个位子上，分3步，共有3 2 3 2 1=36种排法 第五类：个位数为4时，先排0，只能排在百、千、万位，有3种排法，再排十位数字，有1种排法，其余3个数字排在3个位置上，分3步，共有3 1 3 2 1=18种排法 根据分类加法计数原理，共有120+72+54+36+18=300种不同的排法,类型四：染色问题,将一个四棱锥的没一个顶点染上一种颜色，并使同一条棱上的两端点异色，如果有5种颜色可供选择，求不同的染色方法总数。,第一类，C与A同色，共有54313=180种方法 第二类，C与A不同色，共有54322=240种方法 有分类加法计