离散数学组合数学

离散数学组合数学第1页，课件共19页，创作于2023年2月§10.1加法法则和乘法法则加法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有

m+n

种产生方式.使用条件：事件A与B产生方式不重叠适用问题：分类选取推广：事件A1有p1种产生方式，事件A2有p2

种产生方式，…,事件Ak

有pk

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

种产生的方式.

第2页，课件共19页，创作于2023年2月乘法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有

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

种产生方式，…,事件Ak

有pk

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

种产生的方式.

乘法法则第3页，课件共19页，创作于2023年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：第4页，课件共19页，创作于2023年2月例设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

223=36

例10.1.2：甲->乙->丙->甲3

22=12

甲->丙->乙->甲2

23=12

甲->丙->甲2

2

=4

由加法法则，总分法数是36+12+12+4=64其中经过乙城的有64-4=60种第5页，课件共19页，创作于2023年2月§10.2排列与组合设n元集合S，从S中选取

r个元素.根据是否有序，是否允许重复可以将该问题分为四个子类型.不重复选取重复选取有序选取集合的排列多重集的排列无序选取集合的组合多重集的组合第6页，课件共19页，创作于2023年2月7定义

从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r

排列的数目记作

P(n,r)，或

,当n=r时，叫做S的全排列，简称S的一个排列。定理10.1证明使用乘法法则当n=r时，P(n,r)=n!集合的排列第7页，课件共19页，创作于2023年2月例

在5天内安排3门课程的考试(1)若每天只允许考1门，有多少种方法？(2)若不限制每天考试的门数，有多少种方法？

解：

（1）

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

（2）每门考试都有5种独立的选法.由乘法法则总选法数为：

N=

5

55=125例10.2.1：第8页，课件共19页，创作于2023年2月例

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

18！=3624！例10.2.2：捆绑法第9页，课件共19页，创作于2023年2月定理10.2一个n元素S的环形r排列数是=n!/(r(n-r)!)

当n=r时，S的环排列数是(n-1)!第10页，课件共19页，创作于2023年2月(1):10个男孩与5个女孩站成一排，如果没有两个女孩相邻，问有多少种方法？(2):10个男孩与5个女孩站成一个圆圈，如果没有两个女孩相邻，问有多少种方法？解（1）：男孩子为全排列，剩余11个空可以插5个女生，即11个空位有序地选5个，则（2）：男孩围成一圈的方法为，剩余10个空插5个女生，为，则例10.2.3：插空法第11页，课件共19页，创作于2023年2月12集合的组合定义

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

的一个r

组合，S的所有r组合的数目记作C(n,r)或定理12.2推论设n,r为正整数，则(1)(2)(3)第12页，课件共19页，创作于2023年2月13多重集的排列（有序，可重复）证明：

对与n个元素的全排列为n!种其中同类元素之间是无序的，且有n1个a1,n2个a2,…,nk个ak，则最终的全排列为：多重集S={n1a1,n2a2,…,nkak}，0<ni

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

(2)若rni

时，每个位置都有k种选法，得kr.(3)若r>n,N=0.第13页，课件共19页，创作于2023年2月

例（1）：有10种画册，每种数量不限，现在要取3本送给3位朋友，问有多少种方法？解：此题为求多重集的3排列数问题，根据定义得，N=103=1000例（2）：有2面红旗、3面黄旗一次悬挂在一根旗杆上，问可以组成多少种不同的标志？解：此题为求多重集的全排列数问题，根据定义得:例10.2.4：第14页，课件共19页，创作于2023年2月多重集的组合（无序，可重复）当r

ni

，

多重集S={n1a1,n2a2,…,nkak}的r组合数为

证明一个

r组合为{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

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

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

x1个

x2个

x3个

xk个r个1，k-1个0的全排列数为第15页，课件共19页，创作于2023年2月性质：设n,r为正整数，则(1)当r>n时,N=0(2)当r=n时,N=1(3)当r

ni

时,(4)当r=1时,N=k推论：若r

ni

，则每个元素至少取一个的r组合数为证明：若每个元素至少取一个，则去掉k个元素，还需选取r-k个元素，即求多重集的r-k组合问题。则第16页，课件共19页，创作于2023年2月

例：一个学生要在相继的5天内安排15个小时的学习时间，问有多少种方法？如果要求每天至少学习1小时，又有多少种方法？解：将这相继的5天记为a1、a2、a3、a4、a5,则第一种安排相当于求多重集的15集合问题，则根据定义得：当每天至少选择1小时时，即每天24小时中至少选择一小时，则根据推论得：例10.2.5：第17页，课件共19页，创作于2023年2月

例：求x1+x2+…+xk=m的正整数解的个数？解：将xi(i=1,2,…,k)可以理解为若干个1的和，则2为两个1的和，3为3个1的和，因xi为正整数，因此xi至少为1个1的和，则问题转化为求多重集