shttp://vcampus.fudan.edu.cn 用户名为学号,登录密码为本学期 〓选课密码。注意:选课密码要大写!
• http://vcampus.fudan.edu.cn • 用户名为学号，登录密码为本学期 选课密码。注意：选课密码要大写!
123递推关系 递推关系是离散变量之间变化规律中常 见的一种方式,与生成函数一样是解决 计数问题的有力工具。 数列u}如从某项后,u前项可推出un 的普遍规律,就称为递推关系。 g利用递推关系和初值在某些情况下可以 二求出序列的通项表达式un,称为该递推 关系的解。 不是所有的递推关系都可求出其解,只 是某些特殊类型有成熟解法
12.3 递推关系 • 递推关系是离散变量之间变化规律中常 见的一种方式，与生成函数一样是解决 计数问题的有力工具。 • 数列{un },如从某项后，un前k项可推出un 的普遍规律，就称为递推关系。 • 利用递推关系和初值在某些情况下可以 求出序列的通项表达式un，称为该递推 关系的解。 • 不是所有的递推关系都可求出其解，只 是某些特殊类型有成熟解法
-126:13世纪初意大利数学家 fibonacci研究过著名 的兔子繁殖数目问题设一对一雌一雄小兔刚满2个月 时,便可繁殖出一雌一雄一对小兔。以后每隔1个月生 对一雌一雄小兔。由一对刚出生的小兔开始饲养到 第n个月,有多少对兔子? 解:设第n个月有F对兔子,它由两部分组成 1)新生出的小兔,其数目等于能生小兔的大兔对数目 小兔满两个月才繁殖,数目为第(n2个月时的兔对数 目,即为Fn20 32原有小兔,其数目等于上月即第n-1个月)的兔对数 咱,即为Fn10 建立如下递推关系: n=Fn2+Fn1,并有初始条件:F=F2=1 这是一个带有初值的递推关系。 满足这种递推关系的数列称为 Fibonac数列
• 例12.6：13 世纪初意大利数学家 Fibonacci 研究过著名 的兔子繁殖数目问题:设一对一雌一雄小兔刚满2个月 时，便可繁殖出一雌一雄一对小兔。以后每隔1个月生 一对一雌一雄小兔。由一对刚出生的小兔开始饲养到 第n个月，有多少对兔子? • 解：设第n个月有Fn对兔子，它由两部分组成: • (1)新生出的小兔，其数目等于能生小兔的大兔对数目 • 小兔满两个月才繁殖，数目为第(n-2)个月时的兔对数 目，即为Fn-2。 • (2)原有小兔，其数目等于上月(即第 n-1个月)的兔对数 目，即为Fn-1。 • 建立如下递推关系: • Fn=Fn-2+Fn-1，并有初始条件：F1=F2 =1。 • 这是一个带有初值的递推关系。 • 满足这种递推关系的数列称为Fibonacci数列
例:设多重集S=(o·a,b,∞c},求a不相邻的m排 列数 解设不相邻的n排列数为an,则a1=3,a2=32-1=8 (减1是为了减去a这种情况), 当n3时 ,a不相 邻的所有n排列可分为互不相容 彐的两类: 1)第一个位置排b或c,剩下的n-个位置a不相邻, =(2)第一个位置排a,则第二个位置只能排b或c,而 剩下的n2个位置a不相邻, °·由加法原则,a不相邻的n排列数为: an=2an1+2an2,并有初始条件a1=3,a2=8, 这是一个带有初值的递推关系
• 例：设多重集S={·a,·b,·c}，求a不相邻的n-排 列数 • 解:设a不相邻的n-排列数为an，则a1=3, a2=3 2 -1=8 • (减1是为了减去aa这种情况)， • 当n≥3时，a 不相邻的所有n-排列可分为互不相容 的两类: • (1)第一个位置排b或c，剩下的n-1个位置a不相邻， • (2)第一个位置排a，则第二个位置只能排b或c，而 剩下的n-2 个位置a不相邻， • 由加法原则，a 不相邻的n-排列数为: • an =2an-1+2an-2，并有初始条件:a1=3,a2=8, • 这是一个带有初值的递推关系
·n个圆盘按半径大小依次套在圆柱A上现 另有圆柱B和C现要将圆盘全部移到柱子 B上,要求每次只能移动一个圆盘到另 个柱子上,且不允许大圆盘套在小圆盘之 上,求所需移动次数
• n个圆盘按半径大小依次套在圆柱A上,现 另有圆柱B和C.现要将圆盘全部移到柱子 B上,要求每次只能移动一个圆盘到另一 个柱子上,且不允许大圆盘套在小圆盘之 上,求所需移动次数