加法原理,乘法原理(Addition Principle a

来源  :   商务推荐     2020-06-19 10:43:53

2020-06-19


计数问题千奇百怪,各式各样。数学的任何一个学门,都可以跟计数沾上一点边。也因此,很难对计数问题作归类。但是,处理这样形形色色的问题,根本的基础原理却就只有五个:

加法原理,乘法原理,对应原理,Fubini原理,排容原理

这五个其貌不扬的原理是计数组合学理论的基石,善用这些原理,可以解决非常複杂的问题,这也是计数组合迷人之处。本文介绍加法原理和乘法原理。

加法原理

高中数学课本是这样讲加法原理的:台北到高雄走陆路有 \(4\) 条路线,走水路有 \(2\) 条路线,走空运有 \(3\) 条路线。请问台北到高雄一共有几条路线?答案是 \(4+2+3=9\)

一般来说,有如下的加法原理

如果要完成一件事有 \(k\) 类方式,第一类方式有 \(n_1\) 个方法,第二类方式有 \(n_2\) 个方法,…,第 \(k\) 类方式有 \(n_k\) 个方法。
则完成这件事有 \(n_1+n_2+\mbox{…}+n_k\) 个方法。

多半学生对这个例题根本嗤之以鼻-这太瞧不起人了;而老师也鲜少阐释加法原理所要传达的重要讯息:

加法原理的精神在于“分类”

也就是说,如果要计数的集合可以分类成互不相交的若干部分,则分别把每个部分算出后相加即可。用数学的语言来说,

加法原理:设 \(S={\bigcup}^t_{i=1}S_i\),其中 \(Si\bigcap{Sj}=\phi\),则 \(|S|={\sum}^t_{i=1}|Si|\)

加法原理也是导出递迴关係式的基础。例如二项式係数:令 \(a_{n,k}\) 表示从 \(n\) 个数中(不妨假设是 \(1,2,\mbox{…},n\))选出 \(k\) 个数的组合数。则所有的方法可以分成两类:\(1\) 被选到,以及 \(1\) 没被选到,这两类互不相交。

如果 \(1\) 被选到,剩下 \(n-1\) 个数还要选 \(k-1\) 个数,有 \(a_{n-1,k-1}\) 个方法。如果 \(1\) 没被选到,剩下 \(n-1\) 个数还要选 \(k\) 个数,有 \(a_{n-1,k}\) 个方法。因此得到递迴式

\(a_{n,k}=a_{n-1,k-1}+a_{n-1,k}\)

再由初始值 \(a_{n,0}=1\) 及 \(a_{n,n}=1\),马上就可以把整个巴斯卡三角形画出来了。

“分类”的思想不只是排列组合,在数学的任何领域都是重要的。试图将某个抽象结构完整分类,是许多领域重要的目标。

乘法原理

高中数学课本是这样讲乘法原理的:台北到台中有 \(4\) 条路线,台中到高雄有 \(3\) 条路线。请问台北到高雄一共有几条路线?答案是 \(4\times{3}=12\)

一般来说,有如下的乘法原理

如果要完成一件事,依次要进行 \(k\) 个步骤;做完第一个步骤有 \(n_1\) 个方法,做完第二个步骤有 \(n_2\) 个方法,\(\mbox{…}\),做第 \(k\) 个步骤有 \(n_k\) 种方法。
则完成这件事有 \(n_1\cdot{n_2}\cdot\mbox{…}\cdot{n_k}\) 种方法。

同样地,乘法原理所要传达的重要讯息是:

乘法原理的精神在于“各个击破”

也就是说,如果要计数的集合可以分类成一连串的单线进行的步骤,则分别把每个步骤方法数算出后相乘即可。用数学的语言来说,

乘法原理:设 \(S={\prod}^t_{i=1}S_i\),则 \(|S|={\prod}^t_{i=1}|S_i|\)

这里 \(S:={\prod}^t_{i=1}S_i=S_1\times{S_2}\times\mbox{…}\times{S_t}=\{(a_1,\mbox{…},a_t):a_i\in{S_i},1\leq{i}\leq{t}\}\) 为集合的乘积(Cartesian product).

一个简单而重要的例子来自资讯科学里的“形式语言(formal language)”领域。在这个研究抽象语言的领域里,一开始有一些可用的字母,字母所成的集合 \(S\) 称为这个语言的字母集(alphabet),一些字母可以形成一个单字的单字有多少?显然,第一个位置有 \(a\) 种方法,第二个为置有 \(a\) 种方法,….,因此由乘法原理一共有 \(a\times{a}\mbox{…}\times{a}= a^n\) 个字。

当然有些单字也许在这个语言中没意义,但这是另外一个层面的问题了。为什幺资讯学家要研究抽象语言?注意到 \(S={0,1}\) 时,这个语言只有 \(0\) 与 \(1\),这正是电脑的世界。\(S=\{A,T,G,C\}\) 时,这个语言就是 \(DNA\) 解码,全世界生物学家都想知道的生命秘密。在这里,组合学与生物学和资讯科学有了交集。

配合加法原理与乘法原理,可以解决高中数学排列组合中绝大部分的问题。给一个有意义的例子:令 \(n={p}^{a_1}_1{p}^{a_2}_2\mbox{…}{p}^{a_t}_t\) 是标準质因数分解,问 \(n\) 有多少正因数?这是高一学生人人会背的公式,但是要用到加法原理与乘法原理才能解释:

因为 \(n\) 的正因数必形如 \(n={p}^{b_1}_1\mbox{…}{p}^{b_t}_t\),其中 \(0\leq{b_i}\leq{a_i}\)。因此 \(b_i\) 有 \((a_i+1)\) 个选法(这用到加法原理)。故 \(n\) 一共有 \((a_1+1)(a_2+1)\mbox{…}(a_t+1)\) 个正因数(这个用到乘法原理)。

在下一篇文章中,我们谈另外几个原理。

相关推荐

不用上床就能看出来他(她)大与小

不用上床就能看出来他(她)大与小

不能从男人外表就一眼看出他性器官的大小,以及性能力的强弱?如果可以的话,如何「相面」呢?如何从面相看
不用买联名就像联名,TNF Nuptse 羽绒外套是「街头」

不用买联名就像联名,TNF Nuptse 羽绒外套是「街头」

Nuptse 羽绒外套以珠穆朗玛峰以西的努子峰命名,也是 The North Face 最具代表性的
不用交通费也能玩台中?小资族、公车族11个首选秘辛

不用交通费也能玩台中?小资族、公车族11个首选秘辛

想去台中玩却不会骑车?想要开车又怕难找车位?不管有没有交通工具都不用怕。这次打卡编就教你超简单的方式