10-2 组合分析 离散数学 教学课件.pptVIP

作业 23 P226：15, 18 P227：25, 27 (下次上课交作业) * T(2)=3, T(3)=7, T(4)=15 * T(2)=3, T(3)=7, T(4)=15 * 如A=[1, 4, 7, 10], B=[2, 6, 8, 20]， 则此情况下比较次数达到最大，为4×2-1=7次 第10章 组合分析初步 10.1 加法法则和乘法法则 10.2 基本排列组合的计数方法 10.3 递推方程的求解与应用 多重集的组合 定理10.7 设S ={∞?a1, ∞?a2, …, ∞?ak } ，则S的r 组合数为 S的 r 组合形式为 { x1?a1, x2?a2, …, xk?ak }，其中 x1 + x2+ … + xk = r , xi 为非负整数. 这个不定方程的非负整数解的个数即为S的r 组合数。 相当于分别求 x + y + z = 0 x + y + z = 1 x + y + z = 2 的非负数解的个数之和。 多重集的组合问题 k=3,r =0,1,2 x y z x+y+z 1 0 0 0 0 2 0 0 1 1 3 0 1 0 1 4 1 0 0 1 5 0 1 1 2 6 1 0 1 2 7 1 1 0 2 8 0 0 2 2 9 0 2 0 2 10 2 0 0 2 《基本计数公式的应用》解题注意 选择适当的组合计数模型 把问题分解处理，方法有: 分步处理 要考虑选取的顺序，不同的次序可能会影响到计算的复杂程度 分类处理 在每一步或每一类的计数时，特别要区分选取是否有序，从而采用合适的组合计数公式。 实例11 把2n个人分成n组，每组2人，求不同的分法数 解： 因分组是无序的，且每组2人，故无直接的计数模型可用 采用分步处理的方法 先求出有序地把2人分到一组的计数： 再求出无序分组的个数： 此题得出了利用有序与无序计数之间的关系求解计数问题是一种常用技巧。 实例12 设S是具有3个元素的集合，求 在S中可定义不同的对称且反对称的二元关系的个数 解：设S={1, 2, 3}, 在S定义的对称且反对称二元关系中，意味着其关系矩阵中除主对角线外均为0， 而主对角线上有3个元素，每一位均可为0或1， 所以共23=8种不同的对称且反对称关系。 实例13 设S是具有3个元素的集合，求 在S上可定义不同的等价关系的个数 解：设S={1, 2, 3}, 由等价关系与划分的关系得：三元集上定义的不同等价关系的个数等于三元集上的不同划分的个数。 而三元集的不同划分为下面5个，所以有5个不同的等价关系 基本计数公式的应用实例 设A为n元集，求A上定义的二元关系中有多少个自反关系？ 解： 自反关系矩阵的主对角线元素全为1， 其他元素可以是0或1， 除主对角线外，共有n2-n个元素， 它们共有2n2-n个不同取值情况， 即A上有2n2-n个自反关系 实例 设A为n元集，求A上定义的二元关系中有多少个对称关系？ 解：对称关系矩阵的对称矩阵， 所以只需要考虑上三角或下三角矩阵的不同取值个数即可，它们均可以是0或1， 而上三角或下三角矩阵元素的 个数为(n2+n)/2，它们共有 2(n2+n)/2个不同取值情况， 即A上有2(n2+n)/2 个对称关. 设A为n元集，求A上定义的二元关系中有多少个反对称关系？ 解：反对称关系矩阵的主对角线上n个元素均可取0或1，共有2n种取值 其他非主对角线上元素以主对角线为其位置成对称分布，位置对称的元素rij和rji可有三种取值： rij = rji = 0 rij =1，rji = 0 rij =0，rji = 1 非主对角线上元素共有(n2-n)/2对， 它们共有3(n2-n)/2个不同取值情况， 根据乘法法则，不同的反对称关系 个数为2n ×3(n2-n)/2 个。 × rij = rji = 1 实例 设A、B分别为m元集和n元集，m、n为正整数，则从A到B有多少个函数？其中， (1)多少个单射的函数？ (2)多少个双射的函数？ 解：从A到B的函数构成 集合BA，|BA|=nm 意味mn, 单射的函数的个数为从 n个元素中选取m个不同 元素的方式，为Pnm. (2) 意味m=n, 双射的函数的个数=n!=m! … … n m n 10.3 递推方程的求解与应用 递推方程的求解与组合计数有着密切的关系，在计算机科学技术的领域有着重要的应用。 递归算法是计