组合数学 第一章

清华课件

组

合

数

学

清华课件

前言组合数学是一个古老而又年轻的 数学分支。 据传说，大禹在4000多年前就观 察到神龟背上的幻方…...

清华课件

前言幻方可以看 作是一个3阶方 阵，其元素是1 到9的正整数， 每行、每列以 及两条对角线 的和都是15。

4

9

2

38

51

76

清华课件

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

清华课件

前言组合数学是一个迷人的数学分支, 它 起源于古代的游戏和美学鉴赏. 在现代科学技术的发展中, 人们会面 临各种各样的组合数学问题. 组合数学在计算机科学中发挥着出极 为重要的作用.

清华课件

前言组合数学的蓬勃发展则是在计算机 问世和普遍应用之后。由于组合数学涉 及面广，内容庞杂，并且仍在很快地发 展着，因而还没有一个统一而有效的理 论体系。这与数学分析形成了对照。

清华课件

前言组合数学的基本内容 组合数学关心的事情是要按照一定方式 “配置”一组事物，主要考虑以下几方面 的问题.

(1) 存在性： (2) 计数与分类：主要内容 (3) 构造算法：部分内容 (4) 算法优化：

清华课件

前言组合数学经常使用的方法并不高深 复杂。最主要的方法是计数时的合理分 类和组合模型的转换。 但是，要学好组合数学并非易事， 既需要一定的数学修养，也要进行相当 的训练。

清华课件

前言数学内容:高等数学(微积分,高等代数) 计算机数学(离散数学,组合数学) 意义:方法(用于编程), 素质(全面,细致) 难点:方法的应用, 例题的题型和思路 教材:4版为主 讲课:听课为主, 课件较完整, 板书和说明 多种思路的分析，实例的直观理解 作业:平时30%, 不交没分, 迟交扣分, 错误有分

清华课件

第一章

排列组合

1.1 加法法则与乘法法则

清华课件

1.1 加法法则与乘法法则假设：A和B是性质无关的两类事件。 [ 加法法则 ] 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。集合论语言： 若 |A| = m , |B| = n , A B = , 则 |A B| = m + n 。

清华课件

1.1 加法法则与乘法法则[ 例 ] 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 [ 例 ] 北京每天直达上海的客车有 5 次，客 机有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 = 8 种。 [ 例 ] 某班选音乐的有 5人，选美术的有 7 人，则至少选其中之一的 有7到12 人。

清华课件

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 加法法则与乘法法则[例] 某种字符串由两个字符组成，第一个 字符可选自{a

,b,c,d,e},第二个字符 可选自{1,2,3},则这种字符串共有5 3 = 15 个。 [例] 从A到B有三条道路，从B到C有两 条道路，则从A经B到C有3 2=6 条道路。 [ 例 ] 某班选音乐的有 5人，选美术的有 7 人，则同时选二者的 有0到5人。

清华课件

1.1 加法法则与乘法法则[例] 从三个字符{a,b,c}中，不重复地 取两个的排列有多少? 3×2个排列

ab ax ac ba bx bc cb cx ca

清华课件

1.1 加法法则与乘法法则 例 某种样式的运动服的着色由底色和装 饰条纹的颜色配成。底色可选红、蓝、 橙、黄，条纹色可选黑、白，则共有4 2 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、 黄四种颜色的话，则，方案数就不是4 4 = 16, 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的 相互独立性。

清华课件

1.1 加法法则与乘法法则例1-2 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 1)小于10000的不含1的正整数可看做4位数, 0000到9999,但0000除外. 每位9种选择0,2,3,…,9 不含1的有9×9×9×9-1=6560个. [乘法规则] 总数(0001到9999)有：9999 含1的有：9999-6560=3439个 [要点：含1的=总数-不含1的, 加法规则]

清华课件

1.1 加法法则与乘法法则1)小于100的不含1的正整数可看做2位数, 但00除外. 不含1的有9×9-1=80个. (00,02,…,09, 20,22,…,29, 30,…,99) 含1的有：99-80=19个 (01,11,21,…,91, 10,12,13,…,19)[最小的实例:可以列举]

清华课件

2)“含0”和“含1”不可直接套用。0019含1但不含0。 直接套用, 含0的(??)有：99-80=19个 (00,10,20,…,90, 01,02,03,…,09) 其中:黄色的10个不是含0的. 因此,修改计算方法为: 不含0的1位数有9个，(1,2,…,9) 2位数有 9 2 81个，(11,12,…,19, 21,…,99) 不含0小于100的正整数有81+9=90 含0小于100的正整数有99-90=9个 (10,20,…,90)

清华课件

2)“含0”和“含1”不可直接套用。0019含1但不含0。 在组合的习题中有许多类似的隐含规定 ，要特别留神。 2 不含0的1位数有9个，2位数有 9 个， 3位数有 93 个，4位数有 9 4 个 不含0小于10000的正整数有

9 9 9 9 (9 1) /( 9 1) 73802 3 4 5

含0小于10000的正整数有 9999-7380=2619个

清华课件

1.1 加法法则与乘法法则例1-3 设 长度为n的0,1符号串的数目为

2

n

a a1a 2 a n , ai {0,1}, i 1,2, , n. 2 2 2 =2n n个

由乘法规则

例如：n=3,有8个 000,001,010,011,100,101,110,111

本文来源：https://www.bwwdw.com/article/mzm1.html