1.1-1.2加法乘法法则、一一对应

组合数学郑 德 印杭州师范大学理学院 办公室：D209

手机：13656641859

序11666年莱布尼兹所著《组合学论文》一书 问世，这是组合数学的第一部专著。书中首次 使用了组合论(Combinatorics)一词。

序2组合数学就是按照一定的规则来安排一些离散个体 的有关问题。其内容包括： 1、计数与枚举 2、容斥原理和鸽巢原理 3、组合设计 4、组合算法和组合优化 5、图论

序3组合数学经常使用的方法并不高深复杂。 最主要的方法是计数时的合理分类和组合模型 的转换。 一个技巧是从小规模的问题出发，找到规 律，再推广到一般。

第一章 排列组合1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 加法法则与乘法法则 一一对应 排列与组合 圆周排列 排列的生成算法 允许重复的组合与不相邻的组合 组合意义的解释 应用举例 Stirling公式

1.1

加法法则与乘法法则

加法法则 设事件A有m种产生方式，事件 件B有n种产生方式，则事件A或B之一有 m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , A∩B = , 则

|A∪B| = m + n 。基本假设：事件A和事件B是无关的两类。

1.1

加法法则与乘法法则

例1 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。

例2 北京每天直达上海的客车有 5 次，飞机有 3 次，火车有 5 次， 则每天由北京直达上海的旅行 方式有 5 + 3 + 5 = 13 种。

1.1

加法法则与乘法法则

乘法法则 设事件A有m种产生方式，事件B有n 种产生方式则事件A与B有m · n种产生方式。 集合论语言：若 |A| = m , |B| = n , A B = {(a,b) | a A,b B}, 则 |A B| = m · n。

1.1

加法法则与乘法法则

例3 某种字符串由两个字符组成，第一个字符 可选自{a,b,c,d,e},第二个字符可选自{1 ,2,3},则这种字符串共有5 3 = 15 个。

例4 从A到B有三条道路，从B到C有两条道路，则 从A经B到C有3 2=6 条道路。

加法：得到事件通过两种不同的方法。 乘法：得到事件通过两个步骤。

1.1

加法法则与乘法法则

例5 某种样式的运动服的着色由底色和装饰条纹 的颜色配成。底色可选红、蓝、橙、黄，条纹色可 选黑、白，则共有4 2 = 8种着色方案。

若此例改成底色和条纹都用红、蓝、橙、黄四 种颜色的话，则方案数就不是4 4 = 16, 而 只有 4 3 = 12 种。

1.1例6

加法法则与乘法法则

(1)求小于10000的含1的正整数的个数;(2)求小于10000的含0的正整数的个数.

(1) 小于10000的不含1的正整数可看做4位数,但 0000除外. 故有9×9×9×9-1=6560个. 含1的有：9999-6560=3439个.

另:全部4位数有104个,不含1的四位数有94个, 4 4 含1的4位数为两个的差: 10 -9 = 3439个.

1.1

加法法则与乘法法则

(2)“含0”和

“含1”不可直接套用。0019含1但 不含0。 在组合的习题中有许多类似的隐含的规 定，要特别留神。

不含0的1位数有9个，2位数有9 个，3位数 有93 个，4位数有9 4 个 不含0小于10000的正整数有

2

9+9 +9 +9 =(9 -1)/(9-1)=7380含0小于10000的正整数有 9999-7380=2619.

2

3

4

5

1.1

加法法则与乘法法则

3 2 4 (1) n 7 11 13 ,求除尽n的数的个数. 例7

(2)n 73 142 , 求除尽n的数的个数.(1)4×3×5=60 (2)6×3=18 例8 在1000和9999之间有多少每位上的数字均

不同的奇数？ 个位数有5种取法，千位数有8种取法，百位，

十位各有8,7种取法。5×8×8×7=2240。

1.1

加法法则与乘法法则

例9 由a,b,c,d,e这5个字符，从中取6个构成字 符串，要求：(1)第1,6必为子音字符b,c, d;(2)每个字符串必有两个母音字符a或e, 且两个母音字符不相邻；(3)相邻的两个子音 字符必不相同。求字符串的个数。 由条件(1),两个母音字符的位置不能在1,6,又 由条件(2),位置只能是(2,4),(2,5)和(3,5) 之一。对每种格式，母音2×2,相邻子音3×2,其 他两个子音3×3,因此答案为 3×(2×2×3×2×3×3)=648

1.2 一一对应“一一对应”概念是一个在计数中极为基本的概 念。一一对应既是单射又是满射。如我们说A集合有n个元素 |A|=n,无非是建

立了将A中元与[1,n]元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换. 比如要对A集合计数，但直接计数有困难，于是可 设法构造一易于计数的B,使得A与B一一对应。

1.2 一一对应例1 在64名选手之间进行淘汰赛(即一场的比 赛结果，失败者退出比赛),最后产生一名冠军， 问要举行几场比赛？ 一种常见的思路是按轮计场，费事。 另一种思路是淘汰的选手与比赛(按场计)集一一 对应。63场比赛。