- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
3
7
6
2
1
5
4
可得序列: 3,1,5,5,1。反之从序列3,1,5,5,1也可以构 造出上述树。
2019/5/24
11
1.3 排列
定义：从n个不同的元素中，取出r个按次序排成 一列，称为从这n个元素中取r个的一个排列，其 排列数记为 P(n, r).
由定义显然有 (1) P(n, r) 0, (r n) (2) P(n,1) n, (n 1)
3
1.1基本计数法则
乘法法则：设事件A有m种产生方式，事件B有 n种产生方式，则“事件A与事件B”有mn种产 生方式。
例1.1 设一个符号由两个字符组成，第1个字符 由a,b,c,d,e组成，第2个字符由1,2,3组成，则由 乘法法则，该符号有5 3 15 种产生方式。
2019/5/24
2019/5/24
5
1.1 基本计数法则
例1.4 求长度为n的二元码的数目。 解 长度为n的二元码的形式为 a1a2 an , ai {0,1}, i 1,2,, n
由乘法法则，长度为n的二元码的数目为 2 2 22 2n
2019/5/24
6
1.1 基本计数法则
例1.6 求布尔函数 f ( x1, x2 ,, xn )的数目。
4 3 5 60
2019/5/24
8
1.1 基本计数法则
例1.9 求从a,b,c,d,e这5个字母中取6个所组成的字符 串个数。要求(1)第1个和第6个字符必为子音字符； (2)每一字符串必有两个母音字符，且两个母音字母 不相邻；(3) 相邻的两个子音字符必不相同。 解 符合要求的字符串有以下几种模式：
2019/5/24
13
1.3 排列
例1.14 A单位有7位代表，B单位有3位代表，排在 一列合影，要求B单位的人排在一起，问有多少 种不同的排列方案？
解 B单位的某一排列作为一个元素参加单位A进 行排列，可得 8! 种排列。 B单位的3人共有 3!个排列， 故共有 8!3! 排列方案。
2019/5/24
4
1.1 基本计数法则
例1.3 求比10000小的正整数中含有数字1的数的 个数。 解 比10000小的正整数可以写为
a1a2a3a4 , 0 ai 9
的形式。 共有104-1=9999个 其中不含1的正整数有 94-1=6560个 所求正整数的个数为 9999-6560=3439个。
14
1.3 排列
例1.15 若例1.14中A单位的两人排在两端，B单位 的3人不能相邻，问有多少种不同的排列方案？
解 共有 7!(6 5 4) 604800 种方案。
2019/5/24
15
1.3 排列
例1.16 求20000到70000之间的偶数中由不同的数 字所组成的5位数的个数。 解 设所求的数的形式为 abcde 其中 2 a 6, e {0,2,4,6,8} (1)若 a {2, 4, 6 } ，这时e有4种选择，有
解 自变量 ( x1 , x2 ,, xn ) 可能取值的个数为 2n
设取值为 a1，, a2n
则n个变元的布尔函数有
个。
a1 a2n f 2 2 22n
2019/5/24
7
1.1 基本计数法则
例 1.8 n 73 112 134 ，求能整除n的正整数
的个数。 解 能整除n的正整数可以写为如下形式： 7a1 11a2 13a3 , 0 a1 3, 0 a2 2, 0 a1 4 故能整除n的正整数的个数为
3 4 P(8,3) 4032 (2)若 a {3,5} ，这时e有5种选择，有
2 5 P(8,3) 3360 共有 4032 3360 7392 个。
2019/5/24
16
1.4 圆周排列
从n个对象中取r个沿一圆周排列的排列数用 Q(n, r)
表示，则有
Q(n, r) P(n, r) r
第1章 排列与组合
组合数学
组合数学是研究离散结构的存在、计数、分析和 优化的一门学科。
应用领域: 计算机科学、概率论、社会科学、生 物科学、信息论等。
参考书：
1. R.A.Rrualdi. Introductory Combinatorics
组合数学 机械工业出版社
2. 孙淑玲 许胤龙. 组合数学引论 中国科学技术大 学出版社
所求的字符串个数为：3 23 33 648 个。
2019/5/24
9
1.2 一一对应
例 设某地的街道把城市分割成矩形方格，每个
方格叫做它的块。某甲从家中出发上班，向东要 走过m块，向北要走过n块，问某甲上班的路径有
多少条？
y
解 问题可划为求右图从点
2019/5/24
2
1.1基本计数法则
1.1 基本计数法则
加法法则：设事件A有m种产生方式，事件B有 n种产生方式，则“事件A或事件B”有m+n种产 生方式。
例. 一位学生想选修一门数学课程或一门生物 课程。若有4门数学课程和3门生物课程，则该 学生有4+3=7种不同的选课方式。
2019/5/24
P(n, r) n(n 1)(n r 1) n! , 0! 1 (n r)!
当r=n时有, P(n, n) n (n 1)21 n!
2019/5/24
12
1.3 排列
例1.13 由5种颜色的星状物，20种不同的花排成 如下的图案：两边是星状物，中间是3朵花，问 共有多少种这样的图案？ 解 图案的形状为 ★〇〇〇★ 共有 (5 4) (20 19 18) P(5,2) P(20,3) 136800 种图案。
(0,0)到(m,n)的路径数:
(m,n)
每一条从点(0,0)到(m,n)的路径与
一个由m个x和n个y的排列相对应
所求路径数为：C(m n, m) (0,0)
x
2019/5/24
10
1.2 一一对应
定理（Cayley）n个有标号的顶点的树的数目等 于 nn2 。
例1.12 给定下列树
