当前位置：文档之家 › [工学]离散数学-第02章-计数问题

[工学]离散数学-第02章-计数问题

  • 格式：ppt
  • 大小：342.50 KB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

离散数学-第2章 习题课

离散数学-第2章 习题课
5
谓词的概念与表示
解：a) a:小张 W(x): x是工人。 W(a)
b)S(x):x是田径运动员, B(x):x是球类运动员, h:他 S(h)B(h) c) C(x):x是聪明的，B(x):x是美丽的，a:小莉 C(a) B(a) d) O(x):x是奇数。 O(m) O(2m)
28
变元的约束
例15 如果论域是集合{a,b,c}，试消去下面公式 中的量词。 a) (x) P( x) P(a) P(b) P(c) b) (x) R( x) (x) S ( x)
R(a) R(b) R(c)S (a)S (b)S (c)
c) (x)( P( x) Q( x))
(x)( I ( x) ( R( x) N ( x)))
13
命题函数与量词
例5 令P(x)，L(x)，R(x,y,z)和E(x,y)分别表示 “x是一个点”，“x是一条直线”，“z通过x和 ”和“x=y”。符号化下面得句子。 对每两个点有且仅有一条直线通过该两点。 解：
(x)(y)(( P( x) P( y ) E ( x, y)) (! z )( L( z ) R( x, y, z )))
9
命题函数与量词
e) J(x): x是教练员, L(x): x是运动员。
(x)(L(x) J(x)) f) L(x): x是运动员, S(x): x是大学生,C(x):x是国家 选手。 (x)(S(x)L(x)C(x)) g) C(x):x是国家选手,V(x)：x是健壮的。 ( x)(C(x) V(x)) h) (x)(O(x) C(x) L(x))
14
谓词公式与翻译
例6 利用谓词公式翻译下列命题 a)如果有限个数的乘积等于零，那么至少有一个因 子等于零。 b)对于每一个实数x,存在一个更大的实数y。 c)存在实数x,y和z,使得x与y之和大于x与z之积。

[工学]离散数学-第02章-计数问题

[工学]离散数学-第02章-计数问题
答: 24=16 种。 4. 某人有8件衬衫、4条裤子、5双鞋，
全套衣服用有多少种可能的选择？ 答：8×4×5＝160 种。 6. P(4,4)= 4×3×2 ×1= 24
P(6,5)= 6×5×4 ×3×2= 720， P(7,2)= 7×6= 42。
环形 r-排列
例2.3.3 6个人围坐在圆桌上，有多少种不同的坐
福建农林大学离散数学课程组272014112242设abc分别表示选修数学课程计算机课程和商贸课程的人构成的集合则三种课程都不选的学生集合为u260a64b94c58ac28ab26bc22abc14福建农林大学离散数学课程组2820141122421利用容斥原理得9426221460福建农林大学离散数学课程组292014112容斥原理的推广定理245是任意n个有限集合则推论246设u为全集a是任意n个有限集合则福建农林大学离散数学课程组302014112242定理247若有n1只鸽子住进n个鸽笼则有一个有一个鸽笼至少住进至少住进2只鸽子
法？通过转圈得到的坐法视为同一种坐法。
解: 6个人围坐在圆桌上，有
F
E
6!/6=120 种不同的坐法。
B
A
D
C
图2.3.2
n个人围坐圆桌上，有 (n-1)！种不同的坐法，我们 称这种排列为环排列; 从 n 个人中选出 r 个人围圆 桌而坐，称为 环形r -排列。
定理2.3.3
含 n 个不同元素的集合的环形 r-排列数 Pc(n,r) 是
离散数学
2021年8月7日星期六
第一篇 预备知识
第2章 计数问题
2.0 内容提要
1 乘法原理和加法原理
2
排列与组合
3 容斥原理与鸽笼原理
2.1 本章学习要求

离散数学ppt课件

离散数学ppt课件

02
集合论基础
集合的基本概念
总结词
集合是离散数学中的基本概念， 是研究离散对象的重要工具。
详细描述
集合是由一组确定的、互不相同 的、可区分的对象组成的整体。 这些对象称为集合的元素。例如 ，自然数集、平面上的点集等。
集合的运算和性质
总结词
集合的运算和性质是离散数学中的重要内容，包括集合的交、并、差、补等基本运算，以及集合的确定性、互异 性、无序性等性质。
生，1表示事件一定会发生。
离散概率论的运算和性质
概率的加法性质
如果两个事件A和B是互斥的，那么P(A或B)等于P(A)加上 P(B)。
概率的乘法性质
如果事件A和B是独立的，那么P(A和B)等于P(A)乘以P(B) 。
全概率公式
对于任意的事件A，存在一个完备事件组{E1, E2, ..., En}， 使得P(Ai)>0 (i=1,2,...,n)，且E1∪E2∪...∪En=S，那么 P(A)=∑[i=1 to n] P(Ai)P(A|Ei)。
工程学科
离散数学在工程学科中也有着重要的 应用，如计算机通信网络、控制系统 、电子工程等领域。
离散数学的重要性
基础性
离散数学是数学的一个重要分支 ，是学习其他数学课程的基础。
应用性
离散数学在各个领域都有着广泛的 应用，掌握离散数学的知识和方法 对于解决实际问题具有重要的意义 。
培养逻辑思维
学习离散数学可以培养人的逻辑思 维能力和问题解决能力，对于个人 的思维发展和职业发展都有很大的 帮助。
详细描述
邻接矩阵是一种常用的表示图的方法，它是 一个二维矩阵，其中行和列对应于图中的节 点，如果两个节点之间存在一条边，则矩阵 中相应的元素为1，否则为0。邻接表是一 种更有效的表示图的方法，它使用链表来存 储与每个节点相邻的节点。

离散数学(微课版) 第2章习题答案

离散数学(微课版) 第2章习题答案

离散数学（微课版）第2章习题答案习题 2.11. 给出以下相关数集的定义：•人类：所有人类的集合。

•学生：具有在某所学校注册学籍的人的集合。

•男学生：具有在某所学校注册学籍且性别为男性的学生的集合。

2. 判断以下命题是否为真：•男学生集合是人类集合的子集。

•学生集合是男学生集合的子集。

答案：1.人类集合和学生集合的关系可以表示为：学生集合是人类集合的子集。

因为学生是人类的一个子集，但并不是全部人类都是学生。

2.男学生集合是人类集合的子集，因为男学生是学生的一个子集，而学生又是人类的一个子集。

所以男学生集合也是人类集合的一个子集。

3.学生集合是男学生集合的超集，因为男学生是学生的一个子集，但并不是所有学生都是男学生。

所以学生集合包含了男学生集合。

习题 2.21. 给出以下关系的定义：•R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}。

2. 判断以下命题是否为真：•R 是对称关系。

•R 是自反关系。

答案：1.该关系 R 中的元素可以表示为有序对的形式，如 (1, 1) 表示元素 1 和元素 1 之间存在关系。

根据 R 的定义，可以发现所有的对称元素都存在于 R 中。

所以 R 是一个对称关系。

2.该关系 R 中包括了所有元素对 (x, x)，表示每个元素和它自己之间都存在关系。

所以 R 是一个自反关系。

习题 2.31. 给出以下集合的定义：• A = {1, 2, 3, 4}• B = {2, 4, 6, 8}• C = {1, 3, 5, 7}2. 判断以下命题是否为真：• A ∩ B = {2, 4}• A ∪ C = {1, 2, 3, 4, 5, 7}答案：1. A ∩ B表示 A 和 B 的交集，即包含了同时属于 A 和B 的元素。

根据 A 和 B 的定义，可以发现共同元素为 {2, 4}。

所以命题A ∩ B = {2, 4} 是真的。

2. A ∪ C 表示 A 和 C 的并集，即包含了属于 A 或 C 的所有元素。

离散数学计数定律

离散数学计数定律

离散数学计数定律离散数学是指研究离散化对象及其性质的数学分支。

计数是离散数学的一个重要领域，涉及了各种计算和统计问题。

在离散数学计数定律中，有一些重要的原理和定理被广泛应用于计算和统计的各个领域。

1. 乘法规则：若一个计算过程分为k个相互独立的部分，且第一部分有n1种不同的方式，第二部分有n2种不同的方式，以此类推，第k部分有nk种不同的方式，则整个计算过程有n1*n2*...*nk种不同的方式。

2. 加法规则：若一个计算过程分为k个不相交的部分，且第一部分有n1种不同的方式，第二部分有n2种不同的方式，以此类推，第k部分有nk种不同的方式，则整个计算过程有n1+n2+...+nk种不同的方式。

3. 排列：从n个元素中选取r个元素进行排列，有P(n,r) = n! / (n-r)! 种不同的排列方式。

4. 组合：从n个元素中选取r个元素进行组合，有C(n,r) = n! / (r! * (n-r)!) 种不同的组合方式。

5. 二项式定理：对于任意实数a和b，以及任意非负整数n，有(a+b)^n =C(n,0)*a^n*b^0 + C(n,1)*a^(n-1)*b^1 + ... + C(n,n)*a^0*b^n。

6. 完全排列原理：对于一个元素集合S，若n个元素有ni种不同的排列方式（i从1到k），则这些元素的完全排列方式共有n1! * n2! * ... * nk! 种。

7. 抽屉原理：若n+1个物体放入n个抽屉中，至少有一个抽屉中会放有两个或更多物体。

8. 鸽笼原理：若将n+1只鸽子放入n个鸽笼中，那么至少会有一个鸽笼中放有两只或更多的鸽子。

这些离散数学计数定律在不同领域的计算和统计问题中起着重要的作用，能够帮助解决各种复杂的计数和排列组合问题。

离散数学第2章习题解答

离散数学第2章习题解答
当然非闭式也可以是逻辑有效式(如F(x) F(x))，也可能为矛盾式(如
F(x) F(x))，也可能不存在其值不确定的解释。
2．10(1)
xA(x)
(A(a)
A(b)
A(c))
(消去量词等值式)
A(a)
A(b)
A(c)
(德·摩根律)
x A(x)
(消去量词等值式)
2)
xA(x)
(A(a)
A(b)
A(c))
( H (b,a) H (b,b) H (b, c)
(H(c,a) H(c,b) H (c,c)
分析 在有穷个体域内消去量词时， 应将量词的辖域尽量缩小， 例如，在(2) 中，首先将量词辖域缩小了(因为yG(y)中不含x，所以，可以缩小)。否则，演算是相当麻烦的。见下面的演算：
x(F(x) yG(y)
x(F(x) (G(x) H (x))
(2)令F(x):x是人，G(y):y是化，H (x) : x喜欢，命题符号化为x(F(x) y(G(y) H ( x, y)))
(3)令F(x):x是人，G(x) : x犯错误，命题符号化为
x(F(x) G(x)),
或另一种等值的形式为
x(F(x) G(x)
(4)令F(x): x在北京工作，G( x) : x是北京人，命题符号化为
在一阶逻辑中，将命题符号化时，当引入特性谓词(如题中的F(x))之后，
全称量词后往往使用联结词→而不使用，而存在量词 后往往使用 ，而不使用→，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。
2．6在解释R下各式分别化为
(1)x( x 0);
(2)x y(x y x);
(3)x y z(x y) (x z y z));

离散数学 第2章 计数问题.

数学课程组——国家精品课程 双语示范课程
例2.2.2
Melissa病毒
1990年，一种名叫Melissa的病毒利用侵吞系统资源的 方法来破坏计算机系统，通过以含恶意宏的字处理文 档为附件的电子邮件传播。当字处理文档被打开时， 宏从用户的地址本中找出前 50 个地址，并将病毒转发 给他们。用户接收到这些被转发的附件并将字处理文 档打开后，病毒会自动继续转发，不断往复扩散。病 毒非常快速地转发邮件，将被转发的邮件临时存储在 解 根据Melissa病毒的扩散原理，经过四次转发， 某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。 共有 问经过四次转发，共有多少个接收者？ 50×50×50×50+50×50×50+50×50+ 50 +1 = 6377551个接收者。
（ 4 ）若田伯光和东方不败都有职位，共有多少种 选法？
2019/2/22 78-10
电子科技大学离散数学课程组——国家精品课程 双语示范课程
例2.2.4 解
（ 1 ）根据乘法原理，可能的选法种数为 6×5×4= 120；
（2） [法一 ] 根据题意，确定职位可分为 3个步骤： 确定主席有2种选择；主席选定后，秘书有5个人选； 主席和秘书都选定后，出纳有 4 个人选。根据乘法 原理，可能的选法种数为2×5×4 = 40；
2019/2/22 78-7
电子科技大学离散数学课程组——国家精品课程 双语示范课程
例2.2.3
在一幅数字图像中，若每个像素点用 8 位进行编码， 问每个点有多少种不同的取值。 分析 用8位进行编码可分为8个步骤：选择第一位， 选择第二位， … ，选择第八位。每一个位有两种 选择，故根据乘法原理，8位编码共有 2×2×2×2×2×2×2×2 = 28 = 256种取值。

离散数学课件第2章

4
序,而集合中的元素是不讲顺序的。但是 为了将所有的 概念都统一于集合概念， 可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义 (a, b)={{a},{a, b}} 将二元组定义为比其元素高二层的集合； (4) 也可用二元组来递归的定义n元组如下： (a,b,c)=((a,b),c)
例9 .设 A={1,2,3} R1 ={(1,1),(2,2)} ， R2 ={(1,2),(2,1)} 。
16
元素aA和集合A1A在关系R A×B下的关联集 (1)a的R-关联集(R-relative set of a)： R(a)={b : bBaRb }B ； (2) A1的R-关联集(R-relative set of A1)： R(A1)={b : bB (aA1)(aRb) }B 。 定理.设R A×B是一个二元关系， A1 ,A2 A 。则 (1)保序性：A1 A2 R(A1) R(A2) ； (2)R(A1∪A2) = R(A1)∪R(A2) ； (3)R(A1∩A2) R(A1)∩R(A2) 。
例.设A={a,b,c,d}， A1 = {c,d} ， R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。
17
§3 .关系的表示
关系的性质
一.关系表示法 1°关系的矩阵表示法 设关系RA×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 。 则 用一个m×n阶0—1矩阵MR来表示关系R， 称此矩 阵MR为关系R的关系矩阵(relation matrix)。 MR=(xij)m×n ，其中 1 当（ai,bj) R时 xij = ( i=1,…,m ； j=1,…,n) 0 当（ai,bj) R时

离散数学及其应用第三版第二章计数问题课后答案

离散数学及其应用第三版第二章计数问题课后答案1、从3点到6点，分针旋转了多少度？[单选题] *90°960°-1080°(正确答案)-90°2、由数字1、2、3、4、5可以组成多少个不允许有重复数字的三位数?（）[单选题]*A、125B、126C、60(正确答案)D、1203、已知5m－2n－3＝0，则2??÷22?的值为( ) [单选题] *A. 2B. 0C. 4D. 8(正确答案)4、7．已知点A(－2，y1)，B(3，y2)在一次函数y＝－x＋b的图象上，则( ) [单选题]* A．y1 > y2(正确答案)B．y1 < y2C．y1 ≤y2D．y1 ≥y25、若3x＋4y－5＝0，则8?·16?的值是( ) [单选题] *A. 64B. 8C. 16D. 32(正确答案)6、16．若过多边形的每一个顶点只有6条对角线，则这个多边形是（）[单选题] * A．六边形B．八边形C．九边形(正确答案)D．十边形7、计算－(a－b)3(b－a)2的结果为( ) [单选题] *A. －(b－a)?B. －(b＋a)?C. (a－b)?D. (b－a)?(正确答案)8、函数式?的化简结果是（）[单选题] *A.sinα-cosαB.±（sinα-cosα）(正确答案)C.sinα·cosαD.cosα-sinα9、8．一个面积为120的矩形苗圃，它的长比宽多2米，苗圃长是（）[单选题] *A 10B 12(正确答案)C 13D 1410、函数y=kx（k是不为0的常数）是（）。

[单选题] *正比例函数(正确答案)一次函数反比例函数二次函数函数11、4、已知直角三角形的直角边边长分别是方程x2-14x+48=0的两个根，则此三角形的第三边是（）[单选题] *A、6B、10(正确答案)C、8D、212、4．已知第二象限的点P(－4，1)，那么点P到x轴的距离为( ) [单选题] *A．1(正确答案)B．4C．－3D．313、27.下列各函数中，奇函数的是（）[单选题] *A. y=x^(-4)B. y=x^(-3)(正确答案)C .y=x^4D. y=x^(2/3)14、-120°用弧度制表示为（）[单选题] *-2π/3(正确答案)2π/3-π/3-2π/515、函数y= 的最小正周期是（）[单选题] *A、B、(正确答案)C、2D、416、下列说法中，正确的是（）[单选题] *A、第一象限角是锐角B、第一象限角是锐角(正确答案)C、小于90°的角是锐角D、第一象限的角不可能是钝角17、1．(必修1P5B1改编)若集合P={x∈N|x≤2 022}，a=45，则( ) [单选题] * A．a∈PB．{a}∈PC．{a}?PD．a?P(正确答案)18、9．已知关于x，y的二元一次方程组的解满足x＋y＝8，则k的值为( ) [单选题] * A．4B．5C．－6D．－8(正确答案)19、8.如果直角三角形的三条边为2，4，a，那么a的取值可以有（）[单选题] *A. 0个B. 1个C. 2个D. 3个(正确答案)20、7．把点平移到点，平移方式正确的为（）[单选题] *A．先向左平移3个单位长度，再向下平移2个单位长度B．先向左平移3个单位长度，再向上平移2个单位长度C．先向右平移3个单位长度，再向下平移2个单位长度D．先向右平移3个单位长度，再向上平移2个单位长度(正确答案)21、35、下列判断错误的是（）[单选题] *A在第三象限，那么点A关于原点O对称的点在第一象限.B在第二象限，那么它关于直线y=0对称的点在第一象限.(正确答案)C在第四象限，那么它关于x轴对称的点在第一象限.D在第一象限，那么它关于直线x=0的对称点在第二象限.22、22、在平面直角坐标系中，已知点P，在轴上有点Q，它到点P的距离等于3，那么点Q的坐标是（）[单选题] *(0,3)(0,5)(0,-1)(0,5)或(0,-1) (正确答案)23、5．下列说法中正确的是（）[单选题] *A．没有最大的正数，但有最大的负数B．没有最小的负数，但有最小的正数C．没有最小的有理数，也没有最大的有理数(正确答案)D．有最小的自然数，也有最小的整数24、4.小亮用天平称得牛奶和玻璃杯的总质量为0.3546㎏，用四舍五入法将0.3546精确到0.01的近似值为（）[单选题] *A.0.35(正确答案)B.0.36C.0.354D.0.35525、下列表示正确的是（）[单选题] *A、0={0}B、0={1}C、{x|x2 =1}={1,-1}(正确答案)D、0∈φ26、22．如图棋盘上有黑、白两色棋子若干，找出所有使三颗颜色相同的棋在同一直线上的直线，满足这种条件的直线共有（）[单选题] *A．5条(正确答案)B．4条C．3条D．2条27、已知2x=8,2y=4,则2x+y=（）[单选题] *A 、32(正确答案)B 、33C、16D、428、28.已知点A（2,3）、B（1,5），直线AB的斜率是（）[单选题] *A.2B.-2C.1/2D.-1/2(正确答案)29、x3??(m为正整数)可写成( ) [单选题] *A. x3＋x?B. x3－x?C. x3·x?(正确答案)D. x3?30、已知x-y=3,x2-y2=12,那么x+y的值是( ??) [单选题] *A. 3B. 4(正确答案)C. 6D. 12。

离散数学第二章讲解

2018/12/20 18
练习
1. 设A={0,1}, B={1,2}, 则AB ={(0,1),(0,2), (1,1),(1,2)} BB ={(1,1),(1,2), (2,1),(2,2)}
2. #A=2, #B=3 则#(AB)= 6
#(2AB)= 26 由A到B的不同的关系的个数是 26
2018/12/20 16
普遍关系 因为AB AB，AA AA 所以AB是一个由A到B的关系 AA是A上的一个关系
常将AA记作UA={(ai,aj)|ai,ajA}
恒等关系 定义集合A上的恒等关系IA={(a,a)|aA}
例:设A={a,b,c},则 UA=AA={(a,a),(a,b),(a,c), (b,a),(b,b),(b,c), (c,a),(c,b),(c,c)}是A上的普遍 关系 IA={(a,a),(b,b),(c,c)}是A上的恒等关系
2018/12/20 14
对于B={2,5,8}
则B×B ={(2,2),(2,5),(2,8),(5,2),(5,5),(5,8) ,(8,2),(8,5),(8,8)} 令6={(2,2),(5,2),(8,2)}
7={(8,5), (5,2),(2,8),(2,5)}
因为6 BB, 7 BB, 所以，6, 7均是集合B上的关系
其中第i个元素ai称为该有序n元组的第i个坐标。
例 {a,b,c,d}={b,a,d,c},但(a,b,c,d)(b,a,d,c) {4,4,3,2}={4,3,2} ,但(4,4,3,2)(4,3,2) 当n=2时，有序二元组(a,b)又称为序偶。
2018/12/20 2
定义：设(a1,a2,…,an) 和(b1,b2,…,bn)是两个有序n元组， 若a1= b1, a2=b2,…,an=bn,则称这两个有序n元组相等，并 记作(a1,a2,…,an)=(b1,b2,…,bn)。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

B = (A∩B)∪(B-A)。
|B-A|= |B|－|A∩B|
推论2.4.2 设U为全集，A和B是任意有限集合，则
ABU (A B )AB
2020/10/10
24
福建农林大学离散数学课程组
三个集合的情形
定理2.4.3 设 A, B 和 C 是任意三个有限集合, 有
ABC A B C AB AC BC ABC
n1n2 nt
2020/10/10
5
福建农林大学离散数学课程组
2.2.2 加法原理
假定 X1, X2, …, Xt 均为集合，第 I 个集合 Xi 有 ni 个元素。如 {X1, X2, …, Xt} 为两两不相交的集合， 则可以从 X1, X2, …, Xt 中选出的元素总数为：
n1 + n2 + … + nt。
2020/10/10
23
福建农林大学离散数学课程组
定理2.4.1
设A和B是任意有限集合，有 |A∪B| = |A|＋|B|－|A∩B|。
A-B
U A
分析 由图2.4.1容易看出， A∪B = (A-B)∪(A∩B)∪(B-A)，
B
图2.4.1 B-A
A = (A-B)∪(A∩B)，
|A∪B| = |A-B|+|A∩B|+|B-A| |A| = |A-B|+|A∩B|
U A
B C
2020/10/10
图2.4.2
27
福建农林大学离散数学课程组
例2.4.2 解（续）
（1）利用容斥原理得 ABC
UABCABACBC ABC = 106
（2） A B C
BA BB CA B C 9426221460
2020/10/10
28
福建农林大学离散数学课程组
容斥原理的推广
定理2.4.5 设A1, A2, …, An是任意n个有限集合，则
2020/10/10
13
福建农林大学离散数学课程组
定理2.3.3
含 n 个不同元素的集合的环形 r-排列数 Pc(n,r) 是
P(n,r) n!
Pc(n, r)=
r
= r(n-r)!
(2.3.3)
2020/10/10
14
福建农林大学离散数学课程组
例2.3.4
求满足下列条件的排列数。 (1)10个男孩和5个女孩站成一排，无两个女孩相邻。 (2)10个男孩和5个女孩站成一圆圈, 无两个女孩相邻. 解 (1) 10个男孩的全排列为10!，5个女孩插入到10个 男孩形成的11个空格中的插入方法数为 P(11,5)。
答: 24=16 种。 4. 某人有8件衬衫、4条裤子、5双鞋，
全套衣服用有多少种可能的选择？ 答：8×4×5＝160 种。 6. P(4,4)= 4×3×2 ×1= 24
P(6,5)= 6×5×4 ×3×2= 720， P(7,2)= 7×6= 42。
2020/10/10
12
福建农林大学离散数学课程组
福建农林大学离散数学课程组
离散数学
2020年10月10日星期六
1
福建农林大学离散数学课程组
第一篇 预备知识
第2章 计数问题
2020/10/10
2
福建农林大学离散数学课程组
2.0 内容提要
1 乘法原理和加法原理
2
排列与组合
3 容斥原理与鸽笼原理
2020/10/10
3
福建农林大学离散数学课程组
2.1 本章学习要求
即集合 X1∪X2∪…∪Xt 含有 n1 + n2 + … + nt 个元素。
2020/10/10
6
福建农林大学离散数学课程组
2.3 排列与组合
从某个集合中有序的选取若干个元素的问题， 称为排列问题。
2020/10/10
7
福建农林大学离散数学课程组
2.3.1 排列问题
定义2.3.1 从含 n 个不同元素的集合S中有序选 取的 r 个元素叫做 S 的一个 r -排列，不同的r 排列总数记为 P(n, r)。
2020/10/10
26
福建农林大学离散数学课程组
例2.4.2 解
设A、B、C分别表示选修数学课程，计算机课程 和商贸课程的人构成的集合，
则三种课程都不选的学生集合为 A B C , 只选修计算机科学课程学生的集合为 A B C 。
|U|=260, |A|=64, |B|=94, |C|=58, |A∩C|=28, |A∩B|=26, |B∩C|=22, |A∩B∩C|=14
2020/10/10
32
福建农林大学离散数学课程组
定理2.4.5
若有n只鸽子住进 m (n>m) 个鸽笼，则存在一
个鸽笼至少住进
n
m
1
+1只鸽子。这里， x
表示
小于等于 x 的最大整数。
2020/10/10
33
福建农林大学离散数学课程组
2.7 计数问题的应用
例2.7.2 某一制造铁盘的工厂，由于设备和技术的 原因只能将生产盘子的重量控制在100克到100.1克 之间。现需要制成重量相差不超过0.005克的两铁 盘来配制一架天平，问该工厂至少要生产多少铁盘 才能确保得到一对符合要求的铁盘。
解：该组合问题需四步完成：
一选第一个点数， 有 C(13,1) 种；
二选第二个点数， 有 C(12,1) 种：
三选第一点数的3张牌，有 C(4,3) 种；
四选第二点数的2张牌，有 C(4,2) 种。
根据乘法原理，共有
C(13,1)×C(12,1)×C(4,3)×C(4,2)
= 13×12×4×6 = 3744 种选法。
注意：（1）鸽笼原理仅提供了存在性证明； （2）使用鸽笼原理，必须能够正确识别鸽子和鸽 笼，并且能够计算出鸽子数和鸽巢数。
2020/10/10
30
福建农林大学离散数学课程组
例2.4.4
抽屉里有3双手套，问从中至少取多少只， 才能保证配成一双？ 答：4只。
2020/10/10
31
福建农林大学离散数学课程组
2020/10/10
21
福建农林大学离散数学课程组
2.4 容斥原理与鸽笼原理
容斥原理是研究若干有限集合交与并的计数问题。 鸽笼原理则是研究某些特定对象的存在性问题。
2020/10/10
22
福建农林大学离散数学课程组
2.4.1 容斥原理
定义2.4.1 所谓容斥，是指我们计算某类物体的 数目时，要排斥那些不应包含在这个计数中的数 目，但同时要包容那些被错误地排斥了的数目， 以此补偿。这种原理称为容斥原理，又称为包含 排斥原理。
如果r = n，则称这个排列为 S 的一个全排列， 简称为 S 的排列。
显然，当 r>n 时，P(n, r) = 0。
2020/10/10
8
福建农林大学离散数学课程组
例2.3.1
从含3个不同元素的集合S中有序选取2个元素的排 列总数。
解 从含3个元素的不同集合S中有序选取2个元素的 排列总数为6种。
例2.3.5
一副52张的扑克牌含有4种花色：梅花、方片、红 桃和黑桃；各有13种点数，分别为A, 2—10, J, Q, K。试求满足下列条件的组合数。 （1）手中持有5张牌称为一手牌，一手牌共有多少 种可能的组合？ 解: 有 C(52,5) 种可能的组合。
2020/10/10
19
福建农林大学离散数学课程组
重点掌握
1
1 计算排列组合 2 利用容斥原理
计算集合基数
一般掌握
2
鸽笼原理的简单 应用
了解
3
计数问题的应用
2020/10/10
4
福建农林大学离散数学课程组
2.2.1 乘法原理
如果一些工作需要 t 步完成，第一步有 n1 种不 同的选择，第二步有 n2 种不同的选择，… ，第 t 步有 nt 种不同的选择，那么完成这项工作所有可 能的选择种数为：
(2.4.3)
推论2.4.4 设 U 为全集, A, B 和 C 是任意有限集 合，则
ABC U A B C AB AC
BC ABC
(2.4.4)
2020/10/10
25
福建农林大学离散数学课程组
例2.4.2
调查260个大学生，获得如下数据：64人选修数学 课程，94人选修计算机课程，58人选修商贸课程， 28人同时选修数学课程和商贸课程，26人同时选修 数学课程和计算机课程，22人同时选修计算机课程 和商贸课程，14人对三种课程都选修。问 （1）调查中三种课程都不选的学生有多少？ （2）调查中只选修计算机科学课程的学生有多少？
当 n≥r = 0 时，规定 C(n,r) = 1。 显然，当 r>n 时，C(n,r) = 0。
2020/10/10
17
福建农林大学离散数学课程组
定理2.3.4
对满足 0< r ≤n 的正整数 n 和 r 有， C(n,r)= n! r!(n-r)!
2020/10/10
18
福建农林大学离散数学课程组
（2）一手牌中的5张都是同一花色，共有多 少种可能的组合？
解： 分两步进行： 一选花色，有 C(4,1) 种， 二在选定的花色中选5张牌，有 C(13,5) 种。
据乘法原理，有 C(4,1)×C(13,5) 种。
2020/10/10
20
福建农林大学离散数学课程组
（3）一手牌中有3张牌点数相同，另外两张 牌点数相同，共有多少种可能的组合？
i j k
( 1 )nA 1 A 2 A n
2020/10/10
29