两个计数原理的应用.doc

两个计数原理的应用分类计数原理和分步计数原理是解决排列、组合问题的理论基础.在利用这两个原理解决排列、组合问题时要弄清两个原理的区别与联系，是正确使用这两个原理的前提和条件.这两个原理都是指完成一件事的不同方法数而言的.其区别在于：（1）分类计数原理是“分类”，分步计数原理是“分步”；（2）分类计数原理中每类办法中的每一种方法都能独立完成一件事，分步计数原理中每步中每种方法都只能做这件事的一步，不能独立完成这件事.本文谈谈如何用好两个记数原理迅速解决相关问题.一、分类问题例1 在所有的两位数中，个位数字比十位数字大的两位数有多少个？解法（一）：分析个位数字，可分以下几类：个位是9，则十位可以是1，2，3，8中的一个，故有8个；个位是8，则十位可以是1，2，3，7中的一个，故有7个；同理，个位是7的有6个；个位是6的有5个；个位是2的只有1个.由分类加法计数原理知，满足条件的两位数有1+2+3+4+5+6+7+8=（个）解法二：按十位数字是1，2，3，4，5，6，7，8分成8类，在每一类中满足条件的两位数分别是8个，7个，6个，5个，4个，3个，2个，1个.则共有8+7+6+5+4+3+2+1=36（个）.方法归纳：本题是用分类加法计数原理解答的.结合本题可进一步加深对“完成一件事，有n类方案”的理解，所谓“完成一件事，有n类方案”，这里是指对完成这件事情的所有方案的一个分类.分类时，首先要根据问题的特点确定一个适合于它的分类标准，然后在这个标准下进行分类；其次分类时要注意满足一个基本要求：完成这类事情的任何一种方法必须属于某一类，并且分别属于不同两类的两种方法是不同的方法.只有满足这些条件，才可以用分类加法计数原理.二、分步问题例2 在由数字1，2，3，4，5组成的所有没有重复数字的5位数中，大于23145且小于43521的数共有_.解法一：1、2、3、4、5组成无重复五位数，大于23145且小于43521的有（1）形如，后两位只能填5、4，有1种数合要求.（2）形如，第三位选4或5都满足要求，后两位任选都可.符合要求的数有CA=4种.（3）形如，第二位选4或5，后三位任选，方法数为CA=12种.（4）形如，第二位开始，均可任选，方法数为A=24种.（5）形如，第二位选1或2，后三位任选，方法数为CA=12种.同理形如，2A=4种，形如，1种.合要求总数为（1+4+12）2+24=58种.解法二：可用类似方法算出小于43521的5位数个数与小于等于23145的五位数个数.两数之差即为小于43521且大于23145的五位数个数.答案：58种评述：用分步排位的方法计算排列数时，必须注意三个方面：（1）在题设条件制约下，每一步排位，哪些元素可取，哪些元素不可取；（2）在某一步排位后，下一步排位可取元素的个数，应视具体情况而定；（3）若某一步必须分类，则分类后各步都必须按各类分别计算.三、分类、分步综合问题例3 某城市在中心广场建造一个花圃，花圃分为6个部分（如下图）.现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种.（以数字作答）解法一：从题意来看6部分种4种颜色的花，又从图形看知必有2组同颜色的花，从同颜色的花入手分类求.（1）与同色，则也同色或也同色，所以共有N1=43221=48种；（2）与同色，则或同色，所以共有N2=43221=48种；（3）与且与同色，则共有N3=4321=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=A5=120.答案：120评述：解法一是常规解法，要先弄清什么是区域相邻的概念，如果两个区域至少有一条公共边，那么我们说这两个区域相邻，如图中1、2、3三个区域两两相邻，与不相邻，因此1、2、3三个区域的颜色两两不同，与、与、与及与它们可以同色，也可以不同色，由此进行分类即可解决.解法二安排4