两个计数原理的应用

陈科

中图分类号：G632 文献标识码：B 文章编号：1002-7661（2016）14-214-02

分类计数原理和分步计数原理是解决排列、组合问题的理论基础.在利用这两个原理解决排列、组合问题时要弄清两个原理的区别与联系，是正确使用这两个原理的前提和条件.这两个原理都是指完成一件事的不同方法数而言的.其区别在于：（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都满足要求，后两位任选都可.

∴符合要求的数有C ·A =4种.

（3）形如 ，第二位选4或5，后三位任选，方法数为C ·A =12种.

（4）形如 ，第二位开始，均可任选，方法数为A =24种.

（5）形如 ，第二位选1或2，后三位任选，方法数为C ·A =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=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

评述：解法一是常规解法，要先弄清什么是区域相邻的概念，如果两个区域至少有一条公共边，那么我们说这两个区域相邻，如图中1、2、3三个区域两两相邻，与不相邻，因此1、2、3三个区域的颜色两两不同，②与⑤、③与⑤、②与④及③与⑥它们可以同色，也可以不同色，由此进行分类即可解决.

解法二安排4、5、6时又用了分类和列举的方法.

总结：在具体分类或分步时，常遇到困难，要多练习，多积累经验，掌握思维方法，逐步做到恰当分类，合理分步.元素能重复的问题往往用计数原理.