离散数学Discrete Mathematics.ppt

Discrete Math. , Huang liujia 离散数学 Discrete Mathematics §12.1 加法法则和乘法法则 乘法法则 分类处理与分步处理 分类处理：对产生方式的集合进行划分，分别计数，然 后使用加法法则 分步处理：一种产生方式分解为若干独立步骤，对每步 分别进行计数，然后使用乘法法则 分类与分步结合使用： 先分类，每类内部分步 先分步，每步又分类 二、实例 例12.1 设 A 为 n 元集，问 (1) A上的自反关系有多少个？ (2) A上的反自反关系有多少个？ (3) A上的对称关系有多少个？ (4) A上的反对称关系有多少个？ (5) A 上的函数有多少个？ 实例 例12.1 设 A 为 n 元集，问 (1) A上的自反关系有多少个？ (2) A上的反自反关系有多少个？ (3) A上的对称关系有多少个？ (4) A上的反对称关系有多少个？ (5) A 上的函数有多少个？ 实例 实例 选取问题 --组合计数模型1 集合的排列与组合 集合的排列与组合 证明方法 (3)C(n, r)=C(n?1,r?1)+C(n?1,r) 称为 Pascal公式，也对应了杨辉三角形， 两种证明方法都适用. 多重集的排列与组合 多重集的排列与组合 多重集的组合 实例 实例(续) 组合恒等式——递推式 组合恒等式——变下项求和 恒等式——变上项求和 恒等式——乘积转换式 恒等式——积之和 组合恒等式解题方法小结 恒等式求和——变系数和 证明 (1)二项式定理+求导 (2)已知恒等式代入 二项式定理的应用 非降路径问题 基本计数模型 限制条件下的非降路径数 非降路径模型的应用 证明恒等式 单调函数计数 栈的输出 基本计数模型 限制条件的非降路径数 一一对应 应用——单调函数计数 应用——栈输出的计数 应用——栈输出的计数(续) 推论 推论1 多项式展开式中不同的项数为方程的非负整数解的个数 C(n+ t ?1,n) . 推论2 多项式系数 多项式系数(续) 证明方法： 二项式定理、级数求导 其他组合恒等式代入 解 由二项式定理 令i =13 得到展开式中x12y13的系数，即 例 求在(2x－3y)25的展开式中x12y13的系数. (0,0) 到 (m,n) 的非降路径数： (a,b) 到 (m,n)的非降路径数： 等于 (0,0) 到 (m?a,n?b) 的非降路径数 (a,b) 经过 (c,d) 到 (m,n) 的非降路径数： C(m+n, m) 乘法法则 从(0,0)到(n,n)不接触对角线的非降路径数 N N1：从(0,0) 到 (n,n) 下不接触对角 线非降路径数 N2：从(1,0)到(n,n?1) 下不接触对角 线非降路径数 N0: 从(1,0)到(n,n?1) 的非降路径数 N3: 从(1,0)到(n,n?1) 接触对角线的 非降路径数 关系: N=2N1=2N2=2[N0 ? N3] N3: 从(1,0)到(n,n?1) 接触对角线的 非降路径数 N4: 从(0,1)到(n,n?1) 无限制条件的 非降路径数 关系: N3=N4 例12.8 A={1,2,…,m}, B={1,2,…,n}， N1:B上单调递增函数个 数是(1,1)到 (n+1,n) 的非降路径数 N: B上单调函数个数 N=2N1 N2: A到B单调递增函数个 数是从(1,1)到 (m+1,n) 的非降路径数 N?: A到B的单调函数个数，N? =2N2 严格单调递增函数、递减函数个数都是C(n,m) 例12.9 将1,2,…,n按照顺序输入栈,有多少个不同的输出序列？ 解：将进栈、出栈分别记作 x, y, 出栈序列是n个x，n个y的排列，排列中任何前缀的 x 个数不少于y 的个数. 等于从 (0,0) 到 (n,n) 的不穿过对角线的非降路径数. 实例：n=5 x, x, x ,y, y, x, y, y, x, y ? 进,进,进,出,出,进,出,出,进,出 ? 3, 2, 4, 1, 5 N: 堆栈输出个数 N?:(0,0)到(n,n)不 穿过对角线的 非降路径数 N0:(0,0)到(n,n)的 非降路径总数 N1:(0,0)到(n,n)