离散数学组合数学

离散数学组合数学乘法法则:事件A有m种产生方式,事件B有n种产生方式,则“事件A与B”有

mn种产生方式、使用条件:事件A与B产生方式彼此独立适用问题:分步选取推广:事件A1有p1种产生方式,事件A2有p2

种产生方式,…,事件Ak

有pk

种产生得方式,则“事件A1或A2或…Ak”有p1+p2+…+pk

种产生得方式、

乘法法则例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:例设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

23=36

例10、1、2:甲->乙->丙->甲3

2

2=12

甲->丙->乙->甲2

2

3=12

甲->丙->甲2

2

=4

由加法法则,总分法数就是36+12+12+4=64其中经过乙城得有64-4=60种§10、2排列与组合设n元集合S,从S中选取

r个元素、根据就是否有序,就是否允许重复可以将该问题分为四个子类型、不重复选取重复选取有序选取集合得排列多重集得排列无序选取集合得组合多重集得组合6定义从n元集S中有序、不重复选取得r个元素称为S得一个r排列,S得所有r

排列得数目记作

P(n,r),或

,当n=r时,叫做S得全排列,简称S得一个排列。定理10、1证明使用乘法法则当n=r时,

P(n,r)=n!集合得排列例

在5天内安排3门课程得考试

(1)若每天只允许考1门,有多少种方法？

(2)若不限制每天考试得门数,有多少种方法？

解:

(1)

从5天中有序选取3天,不允许重复,其选法数就是N==5

43=60

(2)每门考试都有5种独立得选法、由乘法法则总选法数为:

N=

5

5

5=125例10、2、1:例

排列26个字母,使得在a与b之间正好有7个字母,问有多少种排法？解:以a排头、b排尾、中间恰含7个字母得排列有P(24,7)种、同理以b排头、a排尾、中间恰含7个字母得排列也有P(24,7)种、剩余18个字母为全排列、

N=2

18！=3624！例10、2、2:捆绑法定理10、2一个n元素S得环形r排列数就是

=n!/(r

(n-r)!)

当n=r时,S得环排列数就是(n-1)!(1):10个男孩与5个女孩站成一排,如果没有两个女孩相邻,问有多少种方法？(2):10个男孩与5个女孩站成一个圆圈,如果没有两个女孩相邻,问有多少种方法？解(1):男孩子为全排列,剩余11个空可以插5个女生,即11个空位有序地选5个,则(2):男孩围成一圈得方法为,剩余10个空插5个女生,为,则例10、2、3:插空法11集合得组合定义

从n元集S中无序、不重复选取的r个元素称为S

的一个r

组合，S的所有r组合的数目记作C(n,r)或定理12.2推论设n,r为正整数,则(1)(2)(3)大家学习辛苦了，还是要坚持继续保持安静13多重集得排列(有序,可重复)证明:

对与n个元素得全排列为n!种其中同类元素之间就是无序得,且有n1个a1,n2个a2,…,nk个ak,则最终得全排列为:多重集S={n1

a1,n2

a2,…,nk

ak},0<ni

+∞(1)全排列r=n,n1+n2+…+nk=n

(2)若r

ni

时,每个位置都有k种选法,得kr、(3)若r>n,N=0、

例(1):有10种画册,每种数量不限,现在要取3本送给3位朋友,问有多少种方法？解:此题为求多重集得3排列数问题,根据定义得,N=103=1000例(2):有2面红旗、3面黄旗一次悬挂在一根旗杆上,问可以组成多少种不同得标志？解:此题为求多重集得全排列数问题,根据定义得:例10、2、4:多重集得组合(无序,可重复)当r

ni

,

多重集S={n1

a1,n2

a2,…,nk

ak}得r组合数为

证明一个

r组合为{x1

a1,x2

a2,…,xk

ak},其中

x1+x2+…+xk

=r,xi为非负整数、这个不定方程得非负整数解对应于下述排列

1…101…101…10……01…1

x1个

x2个

x3个

xk个r个1,k-1个0得全排列数为性质:设n,r为正整数,则(1)当r>n时,N=0(2)当