离散数学之集合论(3)

A B (A B) (B A) {x(x A)(x B)} {x((x A) (}

A B 对称差运算的性质

定理2-1-2.6 设A , B , C为任意三集合，则

（1） A B B A；

（2） A A；

（3） A A ；

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

（4） A B (A ) ( B)；

（5） (A B) C＝A (B C)；

（6）交关于对称差的分配律 A (B C) (A B) (A C)；

（7） 若A B A C，则 B = C 。

证明：

由对称差的定义立即可得（1），（2），（3），（4）的证明。

（5）的证明

(A B) C ((A ) ( B)) C

((A ) ( B) C) (((A ) ( B)) )

(( B) (A ) C) (A ) ( B )

(A B C) ( B ) (A ) ( C)

A (B C) A ((B ) ( C))

(A ((B ) ( C))) ( ((B ) ( C)))

(A ( C) (B )) (( B ) ( C))

(A B C) (A ) ( B ) ( C)

所以 (A B) C＝A (B C)。

（6）的证明

(A B) (A C) ((A B) (A C)) ((A B) (A C))

((A B) ( )) (( ) (A C))

(A B ) (A C)

A ((B ) ( C))

A (B C)

（7）的证明

(A B) (A C) A (A B) A (A C) (A A) B (A A) C B C B C

从对称差定义或文图容易看出

A B (A ) ( B) (A B) (A B) (A B)，

A B (A B) (A B)。

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

§2-1-3 集合中元素的计数

一、两个基本原理

加法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件完成一件即能达到目的（构成集合A∪B），则达到目的的方式数为m+n。

例2-1-3.1 假设从城市A到城市B有铁路两条，公路三条，航线一条，那么按加法原理，从城市A到城市B有2＋3＋1＝6种走法。

乘法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件同时完成才能达到目的（构成集合A∩B），则达到目的的方式数为m n。

例2-1-3.2 一位学生想从图书馆借离散数学和C# 语言书各一本，书架上有三种不同作者的离散数学书，有两种不同作者的C# 语言书，那么这位学生共有3×2＝6种不同的选法。

二、排列、组合

中学里已学过的计数公式是排列组合公式。从n个元素的集合中每次取m个的排列和组合的公式分别为：

Pnmn!n!m ，Cn P n(n 1) (n m 1) (n m)!m!m!(n m)!m

n

对排列Pnm：若m = n时称为全排列，m < n时称为选排列。排列和组合的最基本恒等式有：

mPnm m!Cnmn m,Cn Cnmmm 1,Cn Cn 1 Cn 1

例2-1-3.3 将computer的字母全部取出进行全排列，其中c不在第一位，r不在末位，问共有多少种排法？

解：computer字母的全排列数为P88 8!，其中c排在第一位的排法共有7！种，r排在末位的排法共有7！，除去这些不合要求的排法，还有8！-（7！＋7！）= 30240种，然而这还不是答案，因为c在第一位的7！种排法中r可能排至末位的7！中c可能排在第一位，即c在第一位，r在末位的排法被减去了两次，实际上应该只减一次，故把不应该减的加回去才能得到正确的答案。所求的答案为：

。 P88 2P77 P66 30960（种）

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

这种分析问题的方法称为“多退少补法”，这种思想在“包含排斥原理”中还要用到。

例2-1-3.4 将1 , 2 , 3三个数字排成2行3列的矩阵，要求同行和同列上都没有相同的数字，问这样的数字矩阵有多少？（实际上这就是集合{1 , 2 , 3 }到自身上的一些双射或置换，这些双射不允许一个元素以自身为像）

解： 先排矩阵的第一行共有P33 3! 6种排法，如果不管题目的要求，第二行也有6种排法，由乘法原理，知共有6×6＝36种矩阵。这些矩阵包含了有一列数字相同的情况，有两列因而就有三列数字相同的情况，按题目要求这些矩阵都应该除去，这些矩阵

112的个数可如下计算：一列数字相同其余两列数字不同的矩阵数有C3C3P2种；有两列数

字相同从而就有三列数字相同的矩阵数有3！＝6个，因此所求的矩阵个数为

112P33 P33 C3C3P2 P33 12。

m是从n个元素中任意取m个元素（不重复抽取）的排列与组合，但是有些Pnm与Cn

实际问题需要在n个元素中重复抽取若干个元素来排列，如用0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9这十个数字来编制代码，，每个号码就可以重复使用某个数字。一般地，从n个元素的集合中抽取m个元素，允许重复的排列数为：nm。实际上可以设想有m个位子，每个位子都可以放上n个元素中的任一个，允许

m

重复，由乘法原理即知有×n× = n m 种排法。

例2-1-3.5 求电子计算机中的6位二进制数。

解：电子计算机中的数码第一位数不能为0，故首位必须为1，后面五位每位都可选0或1，固有25 32种排法，因而6位二进制数有32个。

例2-1-3.6 考试时有25个正确或错误的问题，学生也可能不作答，问有多少种不同的考试结果？

解：对每一问题的回答有三种情况：正确、错误和不作答，因而考试结果共有325个。

m关于重复组合数Hn的计算问题。先从一个实例来研究它的计算公式，从{1 , 2 , 3}

中每次取出两个（允许重复抽取）的组合按自然数顺序写出来（即枚举）为：

11 , 12 , 13 , 22 , 23 , 33 (a)

现将各种组合分别加上01，就得到

12 , 13 , 14 , 23 , 24 , 34 (b)

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

(b)中的6个组合恰好是从{1 , 2 , 3 , 4}中任取两个元素不重复的组合情况。反之从(b)中的组合中分别减去01即得(a)，说明(a) 与(b)存在1—1对应关系（双射），因而从三个相异元素中任取两个的重复组合数可化为从四个相异元素中任取两个不重复的组合数

222m来计算，即H3一般地计算Hn仿上面的讨论，即从{1 , 2 , , C3 (2 1) C4 6得到。

n}中任取m个允许重复的每一个组合，将其元素分别加上0 , 1 , 2 , , m-1即变成从{1 ,

mm2 , , n , n +1 , , n + (m-1) }中任取m个不重复的组合，故Hn Cn m 1。

例2-1-3.7 求成自然序的四位数码个数。

解：四位数码是从{0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9}中选四个数字组成，数字可以重复使用，由于规定自然顺序，故只有一种排法，因而变为10个相异元素中任取四个允许

444重复的组合问题，所求个数为 H10 C10 (4 1) C13 715。

关于环状排列问题，由于环状排列旋转后仍是同一种排列，故可以令其中任一个元素固定位置，不让它移动，其余n-1个元素任意排列，因而n个相异元素的环状排列数为（n-1）!，它恰好为n个相异元素的全排列数n!被n除的结果，这种想法可以推广到不尽相异元素的排列情形。

例2-1-3.8 8为朋友围圆桌而坐，若座位不编号有多少种坐法？座位编号又有多少种坐法？

座位不编号为环状排列问题，有

7！= 5040种坐法。

座位编号为非环状排列问题，故有

8！= 40320 种坐法。

例2-1-3.9 5颗红珠，3颗白珠穿在一个项链上，有多少种方法？

解：如果只穿在一条线上就是不尽相异元素的全排列问题。排列数为

现 …… 此处隐藏：3429字，全部文档内容请下载后查看。喜欢就下载吧 ……