组合计数原理入门,加法原理与乘法原理

橘子网 3,233 0

古希腊数学家毕达哥拉斯曾说:万物皆数。在我们的日常生活中,大到宇宙天体,小到物质微粒,无一不与数字有关。同时,我们每天还会遇到各种各样的“事件”(events)。在不同的情况或条件下,对事件可能发生的种类进行计数也就成了一件习以为常的事情。

比如说:应老师一家暑假去海南游玩,可以坐高铁、飞机、邮轮、客运巴士和自驾私家车,请问应老师到海南游玩有几种出行方式?

又比如说:小豆包同学要参加学校的运动会,她有红色、白色、蓝色三套不同颜色的运动服,还有NK、AD、NB和LN四双不同品牌的运动鞋,请问小豆包同学有多少种运动服和运动鞋的搭配?

显然,对于第一个例子而言,应老师一家有5种不同的出行方式,即1+1+1+1+1=5种。如下图所示:

组合计数原理入门,加法原理与乘法原理

而对于第二个例子而言,小豆包有3×4=12种不同的衣服和鞋子的搭配组合。如下图所示:

组合计数原理入门,加法原理与乘法原理

再举个例子:有两个盒子,其中一个盒子里有5个小球,另一个盒子里有9个小球,所有的这些小球颜色各不相同。请问:(1)从两个盒子内任取一个小球,有多少种不同的取法?(2)从两个盒子内各取一个小球,有多少种不同的取法?

组合计数原理入门,加法原理与乘法原理

对于第1个小问题来说,要求的是“任取”一个小球,于是两个盒子里的小球都是我选择的对象,因此有5+9=14种取法;对于第2个小问题来说,要求的是“各取”一个小球,于是我要先从第一个盒子的5个小球中取出一个,然后再从第二个盒子里的9个小球中取出一个,因此有5×9=45种取法。

那么,这两种取法在本质上有什么区别呢?前者要求“任取”,意思是任何一个小球都能满足题目的要求,因此只要把两个盒子里所有的小球数简单加总即可;而后者要求“各取”,意思是题目要求从两个盒子里分别取出一个小球,一共要取出两个小球,任何一个盒子里的单独一个小球都是无法满足要求的,因此要将两个盒子里的小球数相乘得到最后的结果。

我们综上可知:如果完成一件事情有几类方法,无论哪类中的哪种方法都可以完成这件事情,就用加法;如果完成一件事情需要分成几个步骤,要依次完成每个步骤后才能完成这件工作,就用乘法。于是,我们就有了最基本的计数原理:加法原理(Addition Principle)和乘法原理(MultiplicationPrinciple)。

加法原理:如果完成一件任务有n类方法,在第一类方法中有m1种不同的方法,在第二类方法中有m2种不同的方法,……,在第n类方法中有mn种不同的方法,那么完成这件任务共有N=m1+m2+…+mn种不同的方法。加法原理体现的是一种分类计数的思想。

乘法原理:如果完成一件任务需要分成n个步骤进行,做第一步有m1种不同的方法,做第二步有m2种不同的方法,……,做第n步有mn种不同的方法,那么按照这样的步骤,完成这件任务共有N=m1×m2×…×mn种不同的方法。乘法原理体现的是一种分步计数的思想。

加法原理和乘法原理是组合计数或者组合数学最基本的计数原理。下面我们来看几个例题。

例1:小明高考填报志愿,他对浙江大学的数学、物理、工程、化工、计算机这五个专业有兴趣,同时他也对中山大学的经济学、法学、生物这三个专业有兴趣。请问:假如最终只能选一个专业,小明最后有多少种专业可以选择?

由于小明最终只能在两所大学中选一所,而且只能选择其中一个专业,这里两所大学的专业没有重叠的,所以我们根据加法原理,小明的专业选择种类数为5+3=8种。

例2:金拱门大饭店里有3款牛肉汉堡、4款鸡肉汉堡和2款猪肉汉堡,假如你只能选择其中一款汉堡作为午餐,请问有几种选择?

组合计数原理入门,加法原理与乘法原理

这里,无论哪一款汉堡都可以作为午餐,任选一款汉堡都可以满足我们的要求,因此只要把牛肉汉堡、鸡肉汉堡和猪肉汉堡的数量简单加总就可以,即3+4+2=9种选择。

例3:金拱门大饭店里有3款牛肉汉堡、4款鸡肉汉堡和2款猪肉汉堡,同时还有可乐、橙汁、雪碧、红茶、咖啡等5种饮料,要求选一款汉堡并搭配一种饮料作为套餐组合,请问可以搭配出多少种套餐组合?

组合计数原理入门,加法原理与乘法原理

作为套餐组合,汉堡和饮料两者缺一不可,因此要分为两个步骤进行,首先是从3+4+2=9款汉堡里选出一款,然后再从5种饮料里选出一种,这样才能搭配出完整的套餐组合。因此可以搭配出9×5=45种套餐组合。

例4:有1、2、3、4、5这五个数字,用来组成三位数。请问:(1)假如允许每个数位上的数字可以重复,有多少个不同的三位数可以组成?(2)假如每个数位上的数字不可以重复,又有多少个不同的三位数可以组成?

第1个小问题:由于三位数由百位、十位和个位组成,因此我要将这个任务分为三个步骤进行考虑。首先确定百位上的数字,可以从五个数字里任选一个;然后确定十位上的数字,同样可以从五个数字里任选一个;最后确定个位数字,依旧可以从五个数字里任选一个。所以,根据乘法原理,一共有5×5×5=125种不同的三位数可以组成。

第2个小问题:由于各个数位上的数字不可以重复,因此有一些变化。首先确定百位上的数字,可以从五个数字里任选一个;然后确定十位上的数字,由于五个数字中已经有一个数字被用在了百位上,所以只能从剩下的四个数字里选一个放在十位上;最后确定个位数字,由于五个数字中已经有两个数字分别被用在了百位和十位上,所以只能从剩下的三个数字里选一个放在个位上。最后,根据乘法原理,一共有5×4×3=60种不同的三位数可以组成。

例5:数字360有多少个正约数?

我们先将360这个数进行质因数分解,可以得到360=23×32×51。由于每一个约数最后都是由若干个2或3或5相乘所得到的,于是我们可以将这个问题分为三个步骤去考虑。首先考虑数字2,2最多就是3个都用上,也可以不用,因此有3+1=4种可能性;其次考虑数字3,3最多是2个都用上,也可以不用,因此有2+1=3种可能性;最后考虑数字5,5最多只能用1个,也可以不用,因此有1+1=2种可能性。所以,根据乘法原理,一共有4×3×2=24个不同的约数。

最后,还有两点需要进一步强调的是:

(1)加法原理是把完成一件事情的方法分成几类,每一类中的任何一种方法都能完成任务,每一种方法对于完成这件事情来说都是“或者”的关系,所以完成任务的不同方法数就等于各类方法数加总之和;

(2)乘法原理是把一件事情分成几个步骤去完成,这几个步骤缺一不可,每一个步骤对于完成这件事情来说都是“并列”的关系,所以完成任务的不同方法数等于各个步骤方法数的乘积。

上一篇:

下一篇:

相关阅读

分享