组合数学(第3章3.2).ppt

《组合数学(第3章3.2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章排列与组合集合的排列和组合多重集排列主要内容集合循环排列集合的组合多重集的排列应用例子回顾加法原理：设集合S划分为S1,S2,…,Sm。则：

2、S

3、=

4、S1

5、+

6、S2

7、+…+

8、Sm

9、乘法原理设S是P和Q的乘积（即S＝P×Q），则

10、S

11、＝

12、P

13、×

14、Q

15、集合的线性排列循环排列定义：把元素排成首尾相连的一个圈，只考虑元素间的相对顺序的排列称循环排列。123465循环排列计数定理3.2.2n个元素集合的循环r排列个数为：特别地，n元素的循环排列个数=(n1)!应用例3：10个人围坐一个圆桌，其中2个人不愿彼此挨着就座，问有多少种座位摆放方法？解1：总的排列数除去不满足条

16、件的排列数。总的排列数为(101)！2个连续情况的排列数：2×（9－1）！即：9！－2×8！＝7×8！解2：设P1，P2不挨着坐，固定其中一个P1的位置，那么，P2可选位子是7，然后，余下8人可任意坐，按线性排列方法计数：7×8！P1P2P23.3集合的组合定义：从n个元素中无序地取出r个元素，称n元素集合的r-组合。用表示n元素集合的全部r-组合数。约定：（1）=1（2）当r>n时，=0定理3.3.1：对于整数n和r,rn,有：P(n,r)=r!即证明：对P(n,r)计数可分为两步：1）从集合中无序选取r个元素：2）对选取的元素排序计数：r!由乘法原理得到：P

17、(n,r)=r!推论3.3.1：对于整数r，0rn，＝应用例：平面上25个点，假设不存在3点共线情况，问这些点可以组成多少条直线？多少个三角形？解：1）每两个点确定一条直线：2）每三个点确定一个三角形：例：如果每个词都包含3，4或5个元音，那么字母表中26个字母可以构造多少个8字母词？（假设每个词中的字母使用次数没有限制）解：1）3元音词：，元音位置方式，元音选择方式，辅音的方式。2）4元音词：3）5元音词：定理3.3.2：下述公式成立：证明：对n元集合S的所有组合用不同方法计数。1）对所有r-组合运用加法原理得：2）对于S的每一个元素编号，那么对任何一个组合C，S

18、的一个元素x有2种可能，由乘法原理，n个元素共有2n。即完成定理证明。n21无限重复数多重集的排列定理3.4.1：令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为kr注：若S的每种元素的重数都大于或等于r，结论同样成立。证明：S的一个r-排列的第一项可选择k种元素中任何一种，其他r1项同样有k种选择，由乘法原理共有kr种。注：问题等价于k个数字r-排列(允许重复)个数。r21kkk例1：具有4位数字的三进制数的个数是多少？问题等价于：多重集{0,1,2}的4-排列个数。有34个。4321多重集排列定理3.4.2：

19、令S是多重集，它有k个不同的元素，每个元素的重复数分别为n1，n2，…，nk，那么，S的排列数等于其中n=n1+n2+…+nk证明设S＝{n1a1,n2a2,…,nkak}，S的n-排列。问题相当于将所有这些元素放到n个有序位置的方法。n1个a1的放置方法有种，n2个a2的放置位置剩下nn1个，因此，有种。继续下去，运用乘法原理。n321S的排列总数为：＝＝应用例：求字母多重集{1M,4I,4S,2P}的排列数。n=1+4+4+2=11，排列总数为：作业3.6习题8，10,11