(优选)离散数学组合数学.pptx

（优选）离散数学组合数学(优选)离散数学组合数学全文共17页，当前为第1页。

乘法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.使用条件：事件A与B产生方式彼此独立适用问题：分步选取推广：事件A1有p1种产生方式，事件A2有p2种产生方式，…,事件Ak有pk种产生的方式，则“事件A1或A2或…Ak”有p1+p2+…+pk种产生的方式.乘法法则(优选)离散数学组合数学全文共17页，当前为第2页。

例1由数字1、2、3、4、5构成3位数.(1)如果3位数的各位数字都不相同，那么有多少种方法？(2)如果这些3位数必须是偶数，则有多少种方法？(3)这些3位数中可以被5整除的有多少个？(4)这些3位数中比300大的有多少个？解:(1)N=5?4?3=60(2)N=2?5?5=50(3)N=1?5?5=25(4)N=3?5?5=75例10.1.1：(优选)离散数学组合数学全文共17页，当前为第3页。

例设A,B,C是3个城市，从A到B有3条道路，从B到C有2条道路，从A直接到C有2条道路，问:(1)从A到C有多少种不同的方式？(2)从A到C最后又回到A有多少种不同的方式？其中经过B的有多少种？解：（1）N=3?2+2=8（2）甲-乙-丙-乙-甲3?2?2?3=36例10.1.2：甲-乙-丙-甲3?2?2=12甲-丙-乙-甲2?2?3=12甲-丙-甲2?2=4由加法法则，总分法数是36+12+12+4=64其中经过乙城的有64-4=60种(优选)离散数学组合数学全文共17页，当前为第4页。

§10.2排列与组合设n元集合S，从S中选取r个元素.根据是否有序，是否允许重复可以将该问题分为四个子类型.不重复选取重复选取有序选取集合的排列多重集的排列无序选取集合的组合多重集的组合(优选)离散数学组合数学全文共17页，当前为第5页。

6定义从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作P(n,r)，或,当n=r时，叫做S的全排列，简称S的一个排列。定理10.1证明使用乘法法则当n=r时，P(n,r)=n!集合的排列(优选)离散数学组合数学全文共17页，当前为第6页。

例在5天内安排3门课程的考试(1)若每天只允许考1门，有多少种方法？(2)若不限制每天考试的门数，有多少种方法？解：（1）从5天中有序选取3天，不允许重复，其选法数是N==5?4?3=60（2）每门考试都有5种独立的选法.由乘法法则总选法数为：N=5?5?5=125例10.2.1：(优选)离散数学组合数学全文共17页，当前为第7页。

例排列26个字母，使得在a和b之间正好有7个字母，问有多少种排法？解：以a排头、b排尾、中间恰含7个字母的排列有P(24,7)种.同理以b排头、a排尾、中间恰含7个字母的排列也有P(24,7)种.剩余18个字母为全排列.N=2??18！=36?24！例10.2.2：捆绑法(优选)离散数学组合数学全文共17页，当前为第8页。

定理10.2一个n元素S的环形r排列数是=n!/(r?(n-r)!)当n=r时，S的环排列数是(n-1)!(优选)离散数学组合数学全文共17页，当前为第9页。

(1):10个男孩与5个女孩站成一排，如果没有两个女孩相邻，问有多少种方法？(2):10个男孩与5个女孩站成一个圆圈，如果没有两个女孩相邻，问有多少种方法？解（1）：男孩子为全排列，剩余11个空可以插5个女生，即11个空位有序地选5个，则（2）：男孩围成一圈的方法为，剩余10个空插5个女生，为，则例10.2.3：插空法(优选)离散数学组合数学全文共17页，当前为第10页。

11集合的