应用两个计数原理解决问题的方法和策略

■河南省郑州市教育局教学研究室 冯瑞先

■河南省郑州市第二高级中学 冯丽娟

当我们面对一个复杂问题时,一般通过分类或分步将它分解成一些简单的问题,先解决简单问题,然后再将它们整合起来使整个问题得到解答,达到以简驭繁的效果,这是一种重要而基本的思想方法。两个计数原理就是这种思想方法的体现,分类加法计数原理对应着“分类”活动,而且每一类方法都能完成相应的事情;分步乘法计数原理对应着“分步”活动,而且只有完成每一个步骤才能完成相应的事情。排列、组合是两类特殊的计数问题,排列的特殊性在于排列中元素的“互异性”和“有序性”,组合的特殊性在于它只有元素的“互异性”而不需要考虑顺序。排列与组合之间有紧密的联系,从n个不同元素中取出m(m

下面从三个角度介绍应用计数原理解决问题的方法和策略。

一、用“五步自问法”构建计数问题的应用路径

在初学阶段应用计数原理解决问题时,一定要构建五步自问路径:(1)要完成的这件事情是什么? (2)完成这件事情分几类(步)?(3)每步能否独立完成这件事情? (4)每步中分别有几种不同的方法? (5)完成这件事情共有几种不同的方法? 同学们的五步自问实质上是树立仔细审题的意识,有助于认识计数原理中“分类”“分步”的本质,避免计数时重复与遗漏。

二、将“列举法”作为分析和解决计数问题的基本方法

求解计数问题时,我们需要先列举出一些结果进行分析,从而找到一般思路。如果遇到情况较为复杂,即分类较多,标准也较多,同时所求计数的结果不太大时,就利用表格、树状图将其所有可能一一列举出来,会达到出奇制胜的效果。

例 1[2020年全国Ⅱ卷(文数)]如图1,将钢琴上的12 个键依次记为a1,a2,…,a12。设1≤i

图1

A.5 B.8 C.10 D.15

解析:本题是计数原理在音乐中的应用,我们先要理解原位大三和弦、原位小三和弦的数学定义,实质是在1 到12 这12 个整数中选取三个不同的整数k、j、i,其 中k最 大,i最小。原位大三和弦满足k-j=3,j-i=4,即k-i=7,可以列举出所有k、j、i的取值,我们可以从最小数i分析,i的取值可以为1、2、3、4、5,所以这12个数构成的原位大三和弦的情况有:

i=1,j=5,k=8;i=2,j=6,k=9;i=3,j=7,k=10;i=4,j=8,k=11;i=5,j=9,k=12。共5种。

同理,原位小三和弦满足k-j=4,j-i=3,即k-i=7,这12个数构成的原位小三和弦的情况有:

i=1,j=4,k=8;i=2,j=5,k=9;i=3,j=6,k=10;i=4,j=7,k=11;i=5,j=8,k=12。共5种。

所以原位大三和弦与原位小三和弦的个数之和为10,故选C。

三、用模型化思想思考问题,掌握典型问题的技巧解法

常见计数问题,都可以化归为元素和位置的对应关系问题,对于一些复杂的计数问题,同学们要掌握思考问题和解决问题的方法策略,从实际背景中抽象出数学问题,从元素和位置的角度模型化理解问题。

模型1:有限制条件的排列问题——特殊优先法。

限制条件一般指题中的特殊元素或者特殊位置,所以可以从优先安排特殊元素或特殊位置两种角度解题。

例2从6名运动员中选出4名队员参加4×100 米接力赛,如果甲、乙两人都不跑第一棒,那么不同的参赛方案有( )。

A.180种 B.240种

C.300种 D.360种

解析:本例元素多位置少,利用先选后排的解题思路,可以从特殊元素或特殊位置两种角度思考问题。

方法一(元素分析法):可根据甲、乙均不参加;或甲、乙中至少有1人参加分成三类。

由分类计数原理,可得共有24+144+72=240(种)方法,选B。

方法二(位置分析法):本题中的特殊位置是第一棒,所以可以先排第一棒这个位置,再排其他位置。

第二步:排其他三棒,在剩余的5个元素中选取3个元素排3个位置,有种排法。

模型2:相邻问题——捆绑法。

例3用1,2,3,4,5这5个数字组成没有重复数字的五位数,其中2和3相邻的五位偶数有多少个?

解析:由于偶数的个位可以排2或4,所以根据个位数字分成两类。

表1

①若2在个位,此时3在十位,只需用1,4,5这3个数排其他3个位置,这样的五位数有=6(个)。

②若4在个位,此时2,3相邻,需要分两步完成,第一步把2,3捆绑,有种排法,第二步就相当于3个元素排3个位置,有种排法,所以这样的五位数有(个)。

表2

由分类计数原理知,共有6+12=18(个)满足条件的五位数。

模型3:不相邻问题——插空法。

例4现有4名男同学,3名女同学站成一排,任何2名女同学彼此不相邻,有多少种不同的排法?

解析:用插空法处理问题时,需要插空的元素一般都是最后一步排,体现分步原理。

模型4:定序问题——消序法。

例5书架上原来摆放着6本书,现要再插入3本书,则不同插法的种数为( )。

解析:(方法一)9本书排成一排有种排法,包含原来的6本书产生的种排法,由于原来的6 本书已经摆放好,故可以从9本书的全排列结果中消去原来6本书的排法数,即符合题意的插法种数为选C。

此种解法是定序问题的一般处理思路,此题还可以从以下两种角度解决。

(方法二)9 本书排成一排,相当于9 个位置,原来6本书顺序不变,故此题相当于在9个位置中选3个位置排3本书,有种排法,而原来的6 本书只有一种排法,故共有方法。

(方法三)因为要插入3 本书,故分三步完成:第一步,插第一本书有7 种方法;第二步,插第二本书,有8种方法;第三步,插第三本书,有9种方法。由分步计数原理知,共有7×8×9种方法。

模型5:至多至少问题——间接法。

例63个女生和5个男生排成一排,如果两端不能都排女生,那么有多少种不同的排法?

解析:本例中“两端不能都排女生”的意思是“两端至少有一个男生”,我们可以根据两端所排人员是男生还是女生进行分类,因此就有了第一种解法——直接法。也可以先不考虑限制条件,把所有的排列数算出,再从中排除全部不符合条件的排列数,即减去“两端都排女生的排列数”,这种方法实际是对所求解问题的等价转化,我们称为“间接法”,也称为“去杂法”。一般直接法分类比较麻烦时,可以考虑间接法,但必须注意去杂时要不重复,不遗漏。

方法一(直接法):①如果首位排了男生,则末位就不再受条件限制了,这样可有种不同的排法;

模型6:分配问题——先组后排法。

命题角度①不同元素的分组、分配问题

例7有6本不同的书,分为3组,问:在下列条件下各有多少种不同的分组方法?

(1)每组2本;

(2)一组1本,一组2本,一组3本;

(3)一组4本,另外两组各1本。

解析:本题属于分组问题,其中第一问是平均分组,第二问是不平均分组,第三问是局部平均分组。

(1)有同学这样想,6 本书分成3 组,每组2本就是从6个不同元素中依次选出2个元素,需要分三步完成:第一步,从6 本中选出2本;第二步,从剩余4本中选出2 本;第三步,把剩余2 本拿出来。由分步计数原理知,有种方法。是不是6 本书平 均 分 成3 组的结果数呢? 我们列举出所表示的分组中的部分结果,进行分析。

设6本不同的书为a,b,c,d,e,f,将它们平均分成3 组中有一种分组结果为:ab,cd,ef。在进行分组的过程中,我们发现包含了ab,cd,ef;cd,ab,ef;ef,cd,ab;ab,ef,cd;cd,ef,ab;ef,ab,cd六种结果。这六种结果实际是一种分组结果,它们是由ab,cd,ef这三个组合结果因选取出的顺序不同而产生,所以中包含了一种分组结果的种排列数,应该从的选取结果中消去同一分组中3组元素的顺序不同产生的结果,故将6 本书平均分成3组的方法有

以上解题过程可以归纳为将几个不同元素的平均分组过程,平均分为m组需要在分步选取的基础上除以。

(2)一组1 本,一组2 本,一组3 本 的分组就是分三步选取,共有60(种)方法。

(3)方法一:一组4 本,另外两组各1 本的分组仍然理解为分三步完成,由于其中有两组的数目是相同的,我们称这类问题为局部平均分组,需要在的选取结果上除以,消去平均分的2 组的不同顺序结果,所以分组方法有

方法二:本题由于其中两组都是1本,即元素自然成组,所以我们只需要分出4 本书组成的一组,其他2本书自然成2组,即用=15表示结果。

例8有6本不同的书,分给甲、乙、丙3人,问“在下列条件下各有多少种不同的分配方法?

(1)甲2本,乙2本,丙2本;

(2)甲1本,乙2本,丙3本;

(3)甲4本,乙、丙每人1本;

(4)每人2本;

(5)一人1本,一人2本,一人3本;

(6)一人4本,其余两人每人1本。

解析:本题属于分配问题,其中第一问、第二问、第三问由于每人分的本数固定,属于定向分配问题,由分步乘法计数原理直接分配。

第四问、第五问、第六问属于不定向分配问题,分配给3人,同一本书给不同的人是不同的分法,可看作两个步骤:先分为3 组,再把这3组分给甲、乙、丙3人。

命题角度② 相同元素的分配问题

例9将6个相同的小球放入4个编号为1,2,3,4的盒子,求下列方法的种数:

(1)每个盒子都不空;

(2)恰有1个空盒子;

(3)恰有2个空盒子。

解析:(1)6 个相同小球放入4 个盒子,即把6个小球分成了4份,每个盒子都不空相当于把6 个相同的小球排成一行(由于元素相同,排法只有1种),然后在6个小球之间的5个空隙中任选3个空隙各插一块隔板,每隔开的一份对应一个盒子,有(种)方法。

(2)恰有1 个空盒子,隔板分两步进行:首先在首尾两球外侧放置一块隔板,并在5个空隙中任选2 个空隙各插一块隔板,如|0|000|00|,有种插法;然后将剩下的一块隔板与前面任意一块并放形成空盒,如|0|000||00|,有种插法。

(3)恰有2 个空盒子,隔板分两步进行:首先在首尾两球外侧放置一块隔板,并在5个空隙中任选1个空隙各插一块隔板,有种插法,如|00|0000|;然后将剩下的两块隔板插入形成空盒。

①这2块板与前面3块板形成不相邻的两个盒子,如||00||0000|,有种插法。

②将2块板与前面3块板之一并排形成相邻的2个盒子,如|00|||0000|,有种插法。

归纳小结:解决相同元素分配问题的常见处理策略为隔板法。

(1)如果将放有小球的盒子紧挨着排成一行,便可看作在排成一行的小球的空隙中插入了若干块隔板,相邻两块隔板形成一个“盒”。每一种插入隔板的方法对应着小球放入盒子的一种方法,此法称之为隔板法。隔板法专门解决相同元素的分配问题。

(2)隔板法的解题步骤:

①定个数,确定名额的个数、分成的组数以及各组名额的数量;

②定空位,将元素排成一列,确定可插隔板的空位数;

③插隔板,确定需要的隔板个数,根据组数要求,插入隔板,利用组合数求解不同的分法种数。