离散数学 10.1-10.2：组合数学.ppt
组合分析初步,第十章,10.1 加法法则和乘法法则,加法法则：事件A 有 m 种产生方式，事件 B 有n 种产生方式，则“事件A或B”有 m+n 种产生方式.使用条件：事件 A 与 B 产生方式不重叠适用问题：分类选取,推广：事件 A1有 p1种产生方式，事件 A2有 p2 种产生方式，,事件 Ak 有 pk 种产生的方式，则“事件A1或 A2或 Ak”有 p1+p2+pk 种产生的方式.,乘法法则：事件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位数.(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 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种,10.2 排列与组合,设 n 元集合 S，从 S 中选取 r 个元素.根据是否有序，是否允许重复可以将该问题分为四个子类型.,7,定义 从 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 4 3=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！=36 24！,例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：,插空法,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，则最终的全排列为：,多重集 S=n1a1,n2a2,nkak，0 ni+(1)全排列 r=n,n1+n2+nk=n,(2)若 r ni 时，每个位置都有 k 种选法，得 kr.(3)若rn,N=0.,例（1）：有10种画册，每种数量不限，现在要取3本送给3位朋友，问有多少种方法？解：此题为求多重集 的3排列数问题，根据定义得，N=103=1000例（2）：有2面红旗、3面黄旗一次悬挂在一根旗杆上，问可以组成多少种不同的标志？解：此题为求多重集 的全排列数问题，根据定义得:,例10.2.4：,多重集的组合（无序，可重复）,当r ni，多重集 S=n1a1,n2a2,nkak 的r组合数为 证明 一个 r 组合为 x1a1,x2a2,xkak，其中 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)当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集合问题，则根据定义得：当每天至少选择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组合问题。根据推论得：,例10.2.6：,如x1+x2+x3=7的正整数解得个数为：,小结与学习要求：,了解二元关系的定义和表示方法；熟练掌握关系的性质和运算；特别是复合和三种闭包运算;理解等价关系和偏序关系，明确它们在描述研究对象的结构和特点时重要作用(即分类和覆盖)。它们在计算机科学中有重要应用。,
