《离散数学10.1-10.2：组合数学.ppt》由会员分享，可在线阅读，更多相关《离散数学10.1-10.2：组合数学.ppt（19页珍藏版）》请在金锄头文库上搜索。
1、10.1 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、式. 乘法法则：乘法法则：事件事件A 有有 m 种产生方式，事件种产生方式，事件 B 有有n 种产生方式，则种产生方式，则 “事件事件A与与B” 有有 m n 种种产生方式产生方式.使用条件：使用条件：事件事件 A 与与 B 产生方式彼此独立产生方式彼此独立适用问题：适用问题：分步选取分步选取推广：推广：事件事件 A1有有 p1种产生方式，事件种产生方式，事件 A2有有 p2 种产生方式，种产生方式，, 事件事件 Ak 有有 pk 种产生的方式，种产生的方式，则则 “事件事件A1或或 A2或或 Ak” 有有 p1+p2+pk 种种产生的方式产生的方式. 例例1 由数字由数字1、2、3、4、5构
3、成构成3位数位数.(1)如果如果3位数的各位数字都不相同，那么有多少种方法？位数的各位数字都不相同，那么有多少种方法？(2)如果这些如果这些3位数必须是偶数，则有多少种方法？位数必须是偶数，则有多少种方法？(3)这些这些3位数中可以被位数中可以被5整除的有多少个？整除的有多少个？(4)这些这些3位数中比位数中比300大的有多少个？大的有多少个？解解: (1) N=5 4 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
4、 有有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 其中经过乙城的
5、有其中经过乙城的有 64 -4=60种种 10.2 10.2 排列与组合排列与组合设设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元素.根据是否有序，是否允许重复可以将该问题分为四根据是否有序，是否允许重复可以将该问题分为四个子类型个子类型.不重复不重复选取取重复重复选取取有序有序选取取集合的排列集合的排列多重集的排列多重集的排列无序无序选取取集合的集合的组合合多重集的多重集的组合合7定义 从 n 元集 S 中有序有序、不重复不重复选取的 r 个元素称为 S 的一个 r 排列，S 的所有 r 排列的数目记作 P(n,r)，或 ,当n=r时，叫做S的全排列，简称S的一个排列。定
6、理10.1 证明 使用乘法法则当 n=r时， P(n,r)=n!集合的排列例例 在在5天内安排天内安排3门课程的考试门课程的考试 (1)若每天只允许考若每天只允许考1门，有多少种方法？门，有多少种方法？ (2)若不限制每天考试的门数，有多少种方法？若不限制每天考试的门数，有多少种方法？ 解：解： （1） 从从5天中有序选取天中有序选取3天，不允许重天，不允许重复，其选法数是复，其选法数是 N= = 5 4 3 =60 （2）每门考试都有）每门考试都有5种独立的选法种独立的选法.由乘法由乘法法则总选法数为：法则总选法数为： N= 5 5 5=125例10.2.1：例例 排列排列26个字母，使得在
7、个字母，使得在a和和b之间正好有之间正好有7个个字母，问有多少种排法？字母，问有多少种排法？ 解：以解：以a排头、排头、b排尾、中间恰含排尾、中间恰含7个字母的排列个字母的排列有有P(24,7)种种.同理以同理以b排头、排头、a排尾、中间恰含排尾、中间恰含7个字母的排列也有个字母的排列也有P(24,7)种种.剩余剩余18个字母为全个字母为全排列排列. N=2 18！=36 24！例10.2.2：捆绑法捆绑法例如：例如：10个男孩与个男孩与5个女孩站成一排，如果没有个女孩站成一排，如果没有两个女孩相邻，问有多少种方法？两个女孩相邻，问有多少种方法？ 解：男孩子为全排列，剩余解：男孩子为全排列，剩
8、余11个空可以插个空可以插5个女个女生，即生，即11个空位有序地选个空位有序地选5个，则个，则例10.2.3：插空法插空法定理10.2 一个n元素S的环形r排列数是 = n!/(r (n-r)!) 当n=r时，S的环排列数是(n-1)!12集合的组合定义 从 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 ，则最
9、终的全排列为：多重集多重集 S =n1 a1, n2 a2, , nk ak，0 n, N=0. 例（例（1）：）：有有10种画册，每种数量不限，现在要种画册，每种数量不限，现在要取取3本送给本送给3位朋友，问有多少种方法？位朋友，问有多少种方法？ 解：此题为求多重集解：此题为求多重集 的的3排排列数问题，根据定义得，列数问题，根据定义得，N=103=1000例（例（2）：）：有有2面红旗、面红旗、3面黄旗一次悬挂在一根面黄旗一次悬挂在一根旗杆上，问可以组成多少种不同的标志？旗杆上，问可以组成多少种不同的标志？ 解：此题为求多重集解：此题为求多重集 的全的全排列数问题，根据定义得排列数问题，根
10、据定义得:例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 为非负整数为非负整数. 这个不定方程这个不定方程的非负整数解对应于下述排列的非负整数解对应于下述排列 11 0 11 0 11 0 0 11 x1个个 x2个个 x3个个 xk个个r 个个1，k-1个个 0 的全排列数为的全排列数为性质：设n, r为正整数，则 (1)当rn时, N=0 (2)当
11、r=n时, N=1 (3)当r ni 时, (4)当r=1时, N=k推论：若r ni ，则每个元素至少取一个的r组合数为证明：若每个元素至少取一个，则去掉k个元素，还需选取r-k个元素，即求多重集的r-k组合问题。则 例：例：一个学生要在相继的一个学生要在相继的5天内安排天内安排15个小时的个小时的学习时间，问有多少种方法？如果要求每天至学习时间，问有多少种方法？如果要求每天至少学习少学习1小时，又有多少种方法？小时，又有多少种方法？ 解：将这相继的解：将这相继的5天记为天记为a1、a2、a3、a4、a5,则第一种安排相当于求多重集则第一种安排相当于求多重集 的的15集合问题，则根据定义得：
12、集合问题，则根据定义得： 当每天至少选择当每天至少选择1小时时，即每天小时时，即每天24小时中至小时中至少选择一小时，则根据推论得：少选择一小时，则根据推论得：例10.2.5： 例：例：求求x1+x2+xk=m的正整数解的个数？的正整数解的个数？ 解：将解：将xi(i=1,2,k)可以理解为若干个可以理解为若干个1的和，的和，则则2为两个为两个1的和，的和，3为为3个个1的和，因的和，因xi为正整数，为正整数，因此因此xi至少为至少为1个个1的和，则问题转化为求多重的和，则问题转化为求多重集集 ，且每个元素至少去一，且每个元素至少去一个的个的m组合问题。根据推论得：组合问题。根据推论得： 例1
13、0.2.6：如如x1+x2+x3=7的正整数解得个数为：的正整数解得个数为：了了了了解解解解二二二二元元元元关关关关系系系系的的的的定定定定义义义义和和和和表表表表示示示示方方方方法法法法；熟熟熟熟练练练练掌掌掌掌握握握握关关关关系系系系的的的的性性性性质质质质和和和和运运运运算算算算；特特特特别别别别是是是是复复复复合合合合和和和和三三三三种种种种闭闭闭闭包包包包运运运运算算算算; ;理理理理解解解解等等等等价价价价关关关关系系系系和和和和偏偏偏偏序序序序关关关关系系系系，明明明明确确确确它它它它们们们们在在在在描描描描述述述述研研研研究究究究对对对对象象象象的的的的结结结结构构构构和和和和特特特特点点点点时时时时重重重重要要要要作作作作用用用用 ( (即即即即分分分分类类类类和和和和覆覆覆覆盖盖盖盖) )。它它它它们们们们在在在在计计计计算算算算机机机机科科科科学学学学中中中中有有有有重重重重要应用。要应用。要应用。要应用。
