离散数学 第2版 教学课件 作者 王元元 离散第7讲 递归关系-大学课件-.pptxVIP

算 计算 机专业基 础课程 指挥自动化 授课人： 王 单位： 计算 学院计算机系 元 机 元 理 论教 室 研 研 · 回顾 ·定义6.5： 集合{1 ， 2 ， 3 ， … ， n}的全排列 ， 使得每个数i都 不在第i位上 ， 称这样的排列为{1 ， 2 ， 3 ， … ， n}的一个错置 ·定理6. 15： 集合{1 ， 2 ， 3 ， … ， n}的错置的总数(记为 Dn)是 第6讲 重集的排列与组合 2 约定D0 = 1 。 · 回顾 · (1) Dn = (n- 1) (Dn-2+Dn- 1) · (2) Dn = nDn- 1+ (- 1)n ·证. (1) 设 {1 ， 2 ， 3 ， … ， n}的一个错置是a1a2…ak…an ， 因为 ≠1 ， 所以a1有n- 1种取法 。 设a1= i (2≤i≤n) ， 分两种情况讨 · (1 . 1) ai= 1 。这时取决于其余n-2个数的错置 ， 这些错置的 目是Dn-2 。 · (1 .2) ai≠1 。这时取决于其余n- 1个数的错置： “ 1不可放 在第i位 ， 其它各数j不可放置在第j位 ”， 这些错置的数目 是Dn- 1 。 因此 ， 由加法原理和乘法原理Dn= (n- 1) (Dn-2+Dn- 1 第6讲 重集的排列与组合 3 一个重要的递归关系 第6讲 重集的排列与组合 4 递归关系的求解 《离散数学》 第7讲 ·递归关系 Page 96 to 103 · 内容提要 ·递归关系 ·递归关系的定义和实例 ·用递归关系构造模型 ·用递归关系为实际问题建模 ·递归关系的迭代求解 ·常系数线性齐次递归关系的求解 ·什么是常系数线性齐次递归关系 ·常系数线性齐次递归关系的特征根求解方法 第6讲 重集的排列与组合 6 ·前言 ·有多少个n位二进制串不包含两个连续的0？ ·解： 令an表示这样的n位二进制串数， ·a1 =2 (0, 1) a2 =3 (00,01, 10, 11) ·a3=5 (000,001,010,011, 100, 101, 110, 111) · (010, 110, 011, 101, 111) ·an分为以0和以1结尾两种情况 ·这个等式叫做递归关系 ， 和初始条件一起唯一地确定了序列{a 对以0结尾的情况： 是 加上 10组成的 ， 有an-2个 乎在所有的数学分支中都有 ·对以1结尾的情况： 是许多计数问题用上一 章讨论的方法不加上 组成的 ， 有an- 1个 易求解 ， 但可以通过找到序列的项之 · an = an- 1 + an-2 间的关系间接求解. 用用 几几 要要 具具 重重 工工 · 递归关系是求解组合数学问题的重要 第6讲 重集的排列与组合 7 ·递归关系 (recurrence relation) ·定义1： 关于序列{an}的递归关系是一个等式 ， 它 把an用序列中排在an前面的一项或多项来表示， 这里n ≥n0 ， n0是一个非负整数 。如果一个序列的 项满足某个递归关系 ， 这个序列就叫做该递归关 系的解(或通项,通项公式)。 第6讲 重集的排列与组合