分类计数原理和分步计数原理的理解与简单应用

《分类计数原理和分步计数原理的理解与简单应用》发表在《学周刊》2007年12月15日第12期 CN13-1379/G4 分类计数原理和分步计数原理的理解与简单应用（833200）新疆奎屯市第一高级中学特级教师 王新敞分类计数原理与分步计数原理是计数问题的基本原理，体现了解决问题时将其分解的两种常用方法，即把问题分类解决和分步解决.分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有种不同的方法，在第二类办法中有种不同的方法，……，在第n类办法中有种不同的方法那么完成这件事共有种不同的方法分步计数原理：做一件事情，完成它需要分成n个步骤，做第一步有种不同的方法，做第二步有种不同的方法，……，做第n步有种不同的方法，那么完成这件事有 种不同的方法两个基本原理的作用：计算做一件事完成它的所有不同的方法种数两个基本原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成” 原理浅释：①分类计数原理(加法原理)中，“完成一件事，有n类办法”，是说每种办法“互斥”，即每种方法都可以独立地完成这件事，同时他们之间没有重复也没有遗漏．进行分类时，要求各类办法彼此之间是相互排斥的，不论那一类办法中的哪一种方法，都能独立完成这件事.只有满足这个条件，才能直接用加法原理，否则不可以.②分步计数原理(乘法原理)中，“完成一件事，需要分成n个步骤”，是说每个步骤都不足以完成这件事，这些步骤，彼此间也不能有重复和遗漏．如果完成一件事需要分成几个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么完成这件事的方法数就可以直接用乘法原理.可以看出“分”是它们共同的特征，但是，分法却大不相同．两个原理的公式是: , 这种变形还提醒人们，分类和分步，常是在一定的限制之下人为的，因此，在这里我们大有用武之地：可以根据解题需要灵活而巧妙地分类或分步．强调知识的综合是近年的一种可取的现象．两个原理，可以与物理中电路的串联、并联类比．例1 电视台在“欢乐今宵”节目中拿出两个信箱，其中存放着先后两次竞猜中成绩优秀的观众来信，甲信箱中有30封，乙信箱中有20封.现由主持人抽奖确定幸运观众，若先确定一名幸运之星，再从两信箱中各确定一名幸运伙伴，有多少种不同的结果？解：分两类：（1）幸运之星在甲箱中抽，再在两箱中各定一名幸运伙伴，有30×29×20=17400种结果；（2）幸运之星在乙箱中抽，同理有20×19×30=11400种结果.因此共有17400+11400=28800种不同结果.点评：在综合运用两个原理时，既要合理分类，又要合理分步，一般情况是先分类再分步.例2 从集合{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组数，然后再用分步计数原理求解. 例2中选出5个数组成子集改为选出4个数呢? （答案：C·24=80个）.例3 某城市在中心广场建造一个花圃，花圃分为6个部分（如下图）.现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_____________种.（以数字作答）解法一：从题意来看6部分种4种颜色的花，又从图形看知必有2组同颜色的花，从同颜色的花入手分类求.（1）②与⑤同色，则③⑥也同色或④⑥也同色，所以共有N1=4×3×2×2×1=48种；（2）③与⑤同色，则②④或⑥④同色，所以共有N2=4×3×2×2×1=48种；（3）②与④且③与⑥同色，则共有N3=4×3×2×1=24种.所以，共有N=N1+N2+N3=48+48+24=120种.解法二：记颜色为A、B、C、D四色，先安排1、2、3有A种不同的栽法，不妨设1、2、3已分别栽种A、B、C，则4、5、6栽种方法共5种，由以下树状图清晰可见. 根据分步计数原理，不同栽种方法有N=A×5=120.答案：120点评：①解法一是常规解法，解法二安排4、5、6时又用了分类和列举的方法. ②较复杂的应用题，需确定或设计出完成事件的程序，依需要分类或分步（“类”与“类”之间独立且并列，“步”与“步”相依且连续）而每个程序都是简单的排列组合问题.例4 (1)有红、黄、白色旗子各n面（n＞3），取其中一面、二面、三面组成纵列信号，可以有多少不同的信号？(2) 有1元、5元、10元的钞票各一张，取其中一张或几张，能组成多少种不同的币值？ (1) 解 因为纵列信号有上、下顺序关系，所以是一个排列问题，信号分一面、二面、三面三种情况（三类），各类之间是互斥的，所以用加法原理：①升一面旗，共有3种信号；②升二面旗，要分两步，连续完成每一步，信号方告完成，而每步又是独立的事件，故用乘法原理，因同色旗子可重复使用，故共有3×3＝9种信号；③升三面旗，有3×3×3＝27种信号．所以共有3+9+27＝39种信号．(2) 解：计算币值与顺序无关，所以是一个组合问题，有取一张、二张、三张、四张四种情况，它们彼此是互斥的，用加法原理．因此，不同币值有 ＝15(种)点评 (1) 排列、组合的区别在于顺序性，前者“有序”而后者“无序”；加法原理与乘法原理的区别在于联斥性，前者“斥”——互斥独立事件，后者“联”——相依事件．因而有“顺序”决“问题”，“联斥”定“原理”的说法．(2)加、乘原理是排列、组合问题的理论依据，在分析问题和指导解题中起着关键作用，运用加法原理的关键在于恰当地分类（分情况），要使所分类别既不遗漏，也不重复；运用乘法原理的关键在于分步，要正确设计分步的程序，使每步之间既互相联系，又彼此独立．例5 排成一行，其中不排第一，b不排第二，c不排第三，d不排第四的不同排法共有多少种？ 解：依题意，符合要求的排法可分为第一个排b,c,d中的某一个，共3类，每一类中不同排法可采用画“树图”的方式逐一排出：符合题意的不同排法共有9种点评：按照分“类”的思路，本题应用了分类计数原理，为把握不同排列的规律，“树图”是一种具有直观现象的有效做法.分类计数和分步计数两个原理是排列组合计数的理论依据，类与类之间独立且并列，步与步相依且连续；计算关键：审题、判断分类还是分步？（分类相加，分步相乘）、判断排列还是组合？（有序排列、无序组合）.。