离散数学 ：组合数学.pptVIP

组合分析初步;§10.1 加法法则和乘法法则;;例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;例设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.2 排列与组合;*;例 在5天内安排3门课程的考试 (1)若每天只允许考1门，有多少种方法？ (2)若不限制每天考试的门数，有多少种方法？ 解： （1） 从5天中有序选取3天，不允许重复，其选法数是 N= = 5 ? 4 ?3 =60 （2）每门考试都有5种独立的选法.由乘法法则总选法数为： N= 5? 5? 5=125;例 排列26个字母，使得在a和b之间正好有7个字母，问有多少种排法？ 解：以a排头、b排尾、中间恰含7个字母的排列有P(24,7)种.同理以b排头、a排尾、中间恰含7个字母的排列也有P(24,7)种.剩余18个字母为全排列. N=2 ? ?18！=36 ?24！;定理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个女生，为 ，则;*;*; 例（1）：有10种画册，每种数量不限，现在要取3本送给3位朋友，问有多少种方法？ 解：此题为求多重集 的3排列数问题，根据定义得，N=103=1000 例（2）：有2面红旗、3面黄旗一次悬挂在一根旗杆上，问可以组成多少种不同的标志？ 解：此题为求多重集 的全排列数问题，根据定义得:;多重集的组合（无序，可重复）;性质：设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小时中至少选择一小时，则根据推论得：; 例：求x1+x2+…+xk=m的正整数解的个数？ 解：将xi(i=1,2,…,k)可以理解为若干个1的和，则2为两个1的和，3为3个1的和，因xi为正整数，因此xi至少为1个1的和，则问题转化为求多重集 ，且每个元素至少去一个的m组合问题。根据推论得： ;小结与学习要求：