当前位置：文档之家 › (优选)组合数学课件第六章递推关系

(优选)组合数学课件第六章递推关系

  • 格式：ppt
  • 大小：1.97 MB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

组合数学(第二版)递推关系

组合数学(第二版)递推关系

递推关系
其次,证明an 是通解.若给定一组初始条件
可以仿照齐次方程通解的证明方法,证得相应于条件式 (3.2.11)的解一定可以表示为式 (3.2.10)的形式.
关于 的求法已经解决,这里的主要问题是求式(3.2.2) 的特解an * .遗憾的是寻求特 解还没有一般通用的方法.然而, 当非齐次线性递推关系的自由项f(n)比较简单时,采用 下面的 待定系数法比较方便.
递推关系 【例 3.4.2】 棋盘染色问题:给一个具有1行n 列的1×n
棋盘(见图3.4.1)的每一个 方块涂以红、蓝二色之一,要求相 邻的两块不能都染成红色,设不同的染法共有an 种,试 求an.
图 3.4.1 1×n 棋盘
递推关系
递推关系
【例3.4.3】 交替子集问题:有限整数集合Sn={1,2,…,n} 的一个子集称为交替的, 如果按上升次序列出其元素时,排列 方式为奇、偶、奇、偶、…….例如{1,4,7,8}和 {3,4,11}都是, 而{2,3,4,5}则不是.令gn表示交替子集的数目(其中包括空集), 证明
且有gn=Fn+2.
递推关系
证 显然,g1=2,对应S1 的交替子集为⌀和{1}.g2=3,对应S2 的交替子集为⌀、 {1}、{1,2}.
将Sn 的所有子集分为两部分: (1)Sn-1={1,2,…,n-1}的所有子集; (2)Sn-1的每一个子集加入元素n 后所得子集. 例如,n=4,S4={1,2,3,4}的所有子集划分为两类,即 (1)⌀、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}; (2){4}、{1,4}、{2,4}、{3,4}、{1,2,4}、{1,3,4}、 {2,3,4}、{1,2,3,4}.

递推关系与Fibonacci数列PPT课件

递推关系与Fibonacci数列PPT课件

G( x) x2 x x(G( x) x) x2G(x)
(1 x x2 )G(x) x
x G(x) 1 x x2 .
第16页/共25页
方程1-x-x2=0的两个根设为：
1 5 , 1 5 ,
2
2
则有
x
A
B
G(x)
1
x
x2
1x
1
. x
利用待定系数法易有
因此有
A1 5, B 1 5,
____________________________ 9xB(x) 9b1x 9b2x2 ) xA(x) a1x a2x2
(1 9x)B(x) xA(x) 1
这样就得到了关于A(x)和B(x)的联立方程组：
可以解得：
(1 9x)A(x) xB(x) 8, xA(x) (1 9x)B(x) 1,
第12页/共25页
递的推母关函系数为Gn(xC)，(则n, r ) C(n, r 1)中有C2个(n参数1，,对r )于固定的n， C (n, r )
Gn(x) C(n,0) C(n,1)x C(n, 2)x2
____________________________ xGn(x)
C(n,0)x C(n,1)x2
满足si=0或1，且si si+1=0。
(2) 边长为Fn的正方形可以分解为若干个边长为Fi和Fi+1的长方形。
参见课本图形。
第18页/共25页
(3) F1 F2
Fn Fn2 1;
F1 F3 F2 F2 F4 F3
Fn1 Fn1 Fn
_____)____F_n __Fn_2__F_n_1___________
F1 F2

第06-07讲 组合数学——递推关系

第06-07讲 组合数学——递推关系

定理
r 阶线性常系数非齐次递推关系的通解an是该非齐 次递推关系的一个特解an[p]，加上其相应的齐次 递推关系的通解an[c] [ p] [c ] 即
an an
an
哈尔滨工程大学课件 沈晶 制作
多项式型非齐次递推关系
一般形式 a c a ... c a p( n) n 1 n 1 r nr
哈尔滨工程大学课件 沈晶 制作
定义
如果递推关系式1的每个解an[s]都可以选择一组常 数B1’ , B2’ ,…, Br’ 使得
an B 1 m B 2 m ... Br m
' n 1 ' n 2 '
s
n r
' n n n 成立，则称 B1 m1 B'2 m2 ... B'r mr 是递推关系式1的通解，其中：B1’ , B2’ ,…, Br’是 任意常数。
D1
Dn
Dn1
D2
P

D3
哈尔滨工程大学课件 沈晶 制作
r 阶递推关系的一般形式
an c1 nan1 c2 nan 2 ... cr nan r en 其中：n r , cr 0
若e(n) = 0，称其为齐次递推关系式
若e(n)≠0，称其为非齐次递推关系式
哈尔滨工程大学课件 沈晶 制作
常系数齐次线性递推关系
一般形式：
an c1an1 c2an 2 ... cr an r 0 其中：r 0 c
特征方程：
（式1）
m r c1m r 1 c2 m r 2 ... c r 0
哈尔滨工程大学课件 沈晶 制作
哈尔滨工程大学课件 沈晶 制作

组合数学递推关系

组合数学递推关系

(6.2.4)
如果方程组（6.2.4）有唯一解b'1 , b'2 ,, b'k ，这说明可以找到 这k个常数，使得
解. 考察方程组（6.2.4），它的系数行列式为这是著名的 Vandermonde行列式.因为 q1 , q2 ,, qk 互不相等，所以该行 列式不等于零，这也就是说方程组（6.2.4）有唯一解.
求解递推关系的常用方法 （1）迭代归纳法； （2）特征根法； （3）生成函数法；
例6.1.1（爬楼梯问题）一个小孩要爬上n阶 楼梯，每次可上一阶或两阶，问上n阶有多 少种上法？ 解：
显然登上1阶台阶有1种方法，登上2台阶有2种方法， f(1）=1，f(2)=2 ,称为递推关系的初始条件。 设有f(n) 种方法，要登上这n阶台阶，最后迈上一个台 阶或两个台阶完成. （1）若最后是迈上一个台阶完成的，则前面登上了n1阶台阶，有f(n-1) 种方法； （2）若最后是迈上两个台阶完成的，则前面登上了n2阶台阶，有f(n-2) 种方法，根据加法原理有递推关系： f(n)=f(n-1)+f(n-2) .
n n 1 n 1 n
例6.2.2
f (n) 2 f (n 1) 3 f (n 2) f (0) 1, f (1) 1 先求通解，特征方程是： x 2x 3 0
•
关于微分方程求解的已知结论:
1. 对于4次以及4次以下的方程,目前已有代数解法.(在复数 域内求解) 2. 阿贝尔定理: 5次以及更高次的代数方程没有一般的代数解法.
例6.2.1 求Fibonacci数的递推关系
n2 f (n) f (n 1) f (n 2) f (0) 1, f (1) 1 解：特征方程为x 2 x 1 0, 1 5 1 5 两个特征根分别是：x1 , x2 , 2 2 1 5 n 1 5 n 因此通解f (n) c1 ( ) c2 ( ) 2 2

组合数学第六章递推关系

组合数学第六章递推关系

h(n)＝b’1q1 n＋b’2q2 n＋……＋b’kqk n ＝ ＋ 成立，从而b1q1 n＋b2q2 n＋……＋bkqk n是该递推关系的通 ＋
• 常系数线性齐次递推关系的求解步骤 1. 根据题意求递推关系 2. 利用递推关系得到特征方程 3. 解特征方程，求特征根 解特征方程， 4. 利用特征根写递推关系通解 5. 根据初值确定通解中的系数 6. 给出递推关系的解 • 关于微分方程求解的已知结论: 关于微分方程求解的已知结论 微分方程求解的已知结论
例6.1.2 Fibonacci数列问题是一个古老的数 数列问题是一个古老的数 学问题，是于1202年提出的，问题表述如下: 1202年提出的 学问题，是于1202年提出的，问题表述如下: 把一对兔子（ 雄各一只） 把一对兔子（雌、雄各一只）在某年的 开始放到围栏中， 开始放到围栏中，每个月这对兔子都生出一 对新兔，其中雌、雄各一只。 对新兔，其中雌、雄各一只。由第二个月开 每对新兔每个月也生出一对新兔， 始，每对新兔每个月也生出一对新兔，也是 雄各一只。 雌、雄各一只。问一年后围栏中有多少对兔 这是一个数学模型的形象表示， 子？这是一个数学模型的形象表示，不能真 正用来表示兔子的繁殖规律。 正用来表示兔子的繁殖规律。
方程 xk-c1xk-1-c2xk-2-……-ck=0 • 递推关系的特征根 特征方程的k个根q1 ， q2……qk(可能有重根)，其中qi (i=1,2,……,k)是复数。 • 递推关系的解与特征根的关系？ 递推关系的解与特征根的关系？
引理6.2.1 设q是非零复数.则f(n)=qn是常系数线 引理 性齐次递推关系的解，当且仅当q是它的特征根. 证明 设f(n)=qn是递推关系(6.2.2)的解，即
求解递推关系的常用方法 （1）迭代归纳法； （2）特征根法； （3）生成函数法；

6.2.3-6.2.4组合、组合数-高二数学课件(人教A版2019选择性必修第三册)

6.2.3-6.2.4组合、组合数-高二数学课件(人教A版2019选择性必修第三册)

m !( n m 1)!

( n 1) n !
( n 1)!
C nm 1 .

m !( n m 1)!
m !( n m 1)!
PART.04
组合与组合数的应用
概念讲解
例 3.求值：(1)3C38－2C25；
－
n
3n
(2)C38
＋C
3n
21＋n.
8×7×6
1
6
2
5
3
3
3
3
解：在(1)的基础上再进行全排列，所以一共有 C C C A ＝360(种)方法.
例题剖析
（3）6本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种不
同的方法？
解：可以分为三类情况：①“2,2,2 型”
，有 C26C24C22＝90(种)方法；
②“1,2,3 型”
，有 C16C25C33A33＝360(种)方法；
件次品两种情况，因此根据分类加法计数原理，抽出的3件中至少有1件是次品的
抽法种数为
1
C 21C 982 C 22C 98
9506 98 9604.
(间接法)：抽出的3 件中至少有1件是次品的抽法种数，就是从100件产品中抽出
3件的抽法种数减去3件都是合格品的抽法种数，即
3
100
C
98 97 96
人教A版2019选修第三册
第 六 章 计数原理
6.2.3 组合
6.2.4 组合数
教学目标
1.通过实例理解组合的概念.
2.能利用计数原理推导组合数公式.
3.能解决有限制条件的组合问题.
4.通过研究组合数公式及解决有限制条件的组合问题，提升逻辑推理及数学

组合数学递推关系公开课一等奖优质课大赛微课获奖课件

组合数学递推关系公开课一等奖优质课大赛微课获奖课件
n>1时, 先把A柱最上面n-1张盘通过C柱 移到B上;
然后再将A柱上最下面盘移到C盘上; 最后将B盘上盘通过A盘移到C盘上。
第2页
2
2.1 递推关系
void hanoi(char A,char B,char C,int n) {if (n==1)
printf(“move disk1 from %c to %c” A,C) else
第15页 15
1.母函数在求组合中应用
数列a0,…,a8相应数值是 1,0,28,0,70,0,28,0,1。结构母函数为:
A(x) 1 28x2 70x4 28x6 x8
类似办法可得女同志允许组合数 相应母函数为:
B(x) 10x2 10x3 5x4 x5
第16页 16
1.母函数在求组合中应用
ekx 1 kx (kx)2 (kx)3 ... (kx)n ...
2! 3!
n!
sin x
x
x3
x5
x7
...
(1)n
x 2 n 1
...
3! 5! 7!
( 2n 1)!
cos x 1 x2 x4 x6 ... (1)n x2n ...
2! 4! 6!
( 2n)!
第20页 20
+(r2w+r2y+rwy)+r2wy
把r,w,y都用x来表示，可得: (1+x+x2)(1+x)(1+x) = (1+x+x2)(1+2x+ x2) =1+3x+4x2+3x3+x4
这个函数系数恰好与取不同球数组合数相等, 这就是 母函数方法。

组合数学求解递推关系2

组合数学求解递推关系2

性质3
对线性齐次递推式：
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
设 ak x k , 可以吗？
相应的特征方程为：
x k a1 x k 1 ... ak 1 x ak 0
若 q 是特征方程的解， 则 q n 是齐次递推式的解 .
性质4
对线性齐次递推式
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
若 q1 , q2 , ... qk 是特征方程的 k个不同的
特征根，则 hn c1q1 c2 q2 ... ck qk
n n n
是齐次递推式的通解 .
对初始条件 h0 , h1 , ...， hk -1， 可以唯一确定 hn c1q1 c2 q2 ... ck qk
总结
对线性齐次递推式
hn a1hn1 a2 hn 2 ... ak hn k 0 (ak 0)
若 q1 , q2 , ... qt 是特征方程的全部互异 的特征根， qi 是si 重根（ i 1,2,..., t )，则 hn H n 其中 Hn
(i ) (1)
错位排列 :
Dn ( n 1)( Dn-1 Dn-1 )
二阶变系数线性齐次式。
Dn nDn-1 ( 1)n
一阶变系数线性非齐次式。 例2 Fibonacci数列 f n f n-1 f n- 2 , f 0 0, f1 1 二阶常系数线性齐次式。 例3 等比数列 hn qhn1 一阶常系数齐次 等差数列 hn hn1 d 一阶常系数非齐次 阶乘数列 hn n hn1 一阶变系数齐次

利用递推关系解决组合问题

利用递推关系解决组合问题

利用递推关系解决组合问题在数学上，组合问题是指从给定集合中选取一定数量的元素（不能有序）的方式和数量。

解决组合问题可以用递推关系的方法来进行。

在这里，我们将探讨如何利用递推关系解决组合问题。

首先，让我们回顾一下组合的概念。

假设有一个具有n个元素的集合，我们想要从中选择r个元素（r≤n），这样的选择称为一个组合。

组合数通常表示为C(n,r)，表示从n个元素中选择r个元素的方式数量。

计算组合数可以用以下的组合公式：\[ C(n,r) = \frac{n!}{r!(n-r)!} \]其中，n!表示n的阶乘，即n*(n-1)*(n-2)*...*1。

然而，在某些情况下，直接计算组合数可能会比较麻烦，这时候可以利用递推关系来解决组合问题。

递推关系指的是通过已知的子问题的解来推导出更大规模问题的解。

在组合问题中，可以利用以下的递推关系来计算组合数：\[ C(n,r) = C(n-1,r) + C(n-1,r-1) \]这个递推关系的意思是，要么选择第n个元素，然后从前n-1个元素中再选择r-1个元素；要么不选择第n个元素，然后从前n-1个元素中选择r个元素。

通过不断地递归计算，最终可以得到从n个元素中选择r个元素的组合数。

举个例子来说明递推关系的运用。

假设我们想要从{A, B, C, D, E}这个集合中选择3个元素的组合数。

根据递推关系，可以得到以下计算过程：C(5,3) = C(4,3) + C(4,2)C(4,3) = C(3,3) + C(3,2)C(4,2) = C(3,2) + C(3,1)C(3,3) = 1C(3,2) = 3C(3,1) = 3通过上面的计算过程，我们可以得到C(5,3)=10，即从{A, B, C, D, E}这个集合中选择3个元素的组合数为10种。

总而言之，递推关系是一种解决组合问题的有效方法。

通过不断地推导子问题的解，最终可以得到更大规模问题的解。

利用递推关系解决组合问题，不仅可以简化计算过程，还可以提高计算效率，是解决组合问题的一种重要方法。

组合数学课件(第四章二项式系数)

组合数学课件(第四章二项式系数)
重点：二项式定理、多项式定理证明方法及其应用；
难点：一些组合恒等式证明方法，非降路径问题组合意
义及应用。
§4.1二项式定理
1.二项式系数
( ) 组合数C(n,k)或者
n k
也叫二项式系数.
2. 组合数的定义
n k
0, n!
k!(n
, k )!
0
k n, k n.
3.组合数的一些恒等式
（1）对称式
剩下的n-1个元素中选择k-1个，组合数为C(n-1,k-1)。选出的k个
元素都有可能被第一次选中，因是组合，故重复度为k。得证。
) ) 或通过计算证明： 若k n,
n k
n k
n1 k 1
0
若1 k n, 有
)n
k
n(n 1)...(n k 1) k(k 1)...1
) n (n 1)(n 2)...(n k 1) n
恒等式(4.12)：如n,r∈N，有C(n+r+1,r) = C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)
证明I：反复利用Pascal公式，即可证明。 或利用组合分析法，在集合A={an+r+1}的n+r+1个不同元素选出r 个元素的组合可分为以下多种情况：如r个元素中不包含a1，相 当于从除去a1的n+r个元素中选出r个元素的组合，组合数为 C(n+r,r)；如r个元素中包含a1但不包含a2，相当于从除去a1,a2的 n+r-1个元素中选出r-1个元素的组合，再加上a1而得到，组合数 为C(n+r-1,r-1), …,同理如r个元素中包含a1,a2,…,ar-1，但不包含ar ，相当于从剩下的n+1个元素中选出1个元素的组合，再加上 a1,a2,…,ar-1而得到，组合数为C(n+1,1)；如r个元素中包含 a1,a2,…,ar，相当于从剩下的n个元素中选出0个元素的组合，组 合数为C(n,0) 。由加法法则得

递推算法分析课件

递推算法分析课件
递推算法概述
定义与特点
定义
递推算法是一种通过已知信息逐步推 导出其他信息的方法，通常从一个初 始状态出发，按照一定的规则逐步推 导出最终结果。
特点
递推算法具有明确性、可计算性和可 实现性，能够根据已知信息逐步推导 出结果，适用于解决一些具有规律性 的问题。
递推算法的分类
线性递推
根据已知的线性关系式，逐步推导出最终结果， 如等差数列求和等。
研究如何提高递推算法的稳定 性，减少初始值对结果的影响
，提高结果的可靠性。
探索新的应用场景
挖掘递推算法在其他领域的应 用潜力，如物理、化学、生物 等学科中的复杂问题求解。
REPORT
THANKS
感谢观看
CATALOG
DATE
ANALYSIS
SUMMAR Y
O(2^n)等。
03
递推算法时间复杂度分析
递推算法的时间复杂度取决于递推关系的复杂度和递归深度。通过分析
递推关系，可以估算算法的时间复杂度，并比较不同算法的效率。
空间复杂度
1 2 3
空间复杂度定义
空间复杂度是衡量算法所需存储空间随输入规模 增长而增长的量级，也用大O表示法表示。
递归与堆栈空间
递归算法需要使用堆栈来保存递归过程中的状态 ，因此其空间复杂度通常较高。迭代算法则通常 只需少量额外空间。
要点二
详细描述
杨辉三角是一个由数字组成的三角形，每个数字是它正上 方和左上方的两个数字之和。从第二行开始，每个数字都 是上一行相邻两个数字之和。通过递推关系式，我们可以 依次生成每个数字，最终得到完整的杨辉三角。
插入排序算法的改进
总结词
插入排序算法是一种简单的排序算法，通过将元素逐个 插入到已排序序列中实现排序。

新教材2023版高中数学第六章计数原理6.2排列与组合6.2.3组合6.2.4组合数第2课时课件

新教材2023版高中数学第六章计数原理6.2排列与组合6.2.3组合6.2.4组合数第2课时课件
团中既有国内媒体团又有国外媒体团，且国内媒体团不能连续提问，
则不同的提问方式的种数为(
)
A．306
B．198 C．268
D．378
答案：B
解析：由题可知选出的3个媒体团的构成有如下两类：
①选出的3个媒体团中只有一个国内媒体团，有 1632 33 ＝108(种)不同的提问
方式；
②选出的3个媒体团中有两个国内媒体团，有 2631 22 ＝90(种)不同的提问方
61 51 41 31 22
解析：将6名教师分组，只有一种分法，即1，1，1，1，2，共有
，
44
61 51 41 31 22
5
再排列得
×5 ＝1 800，故选.44方法归纳
分组、分配问题的解法
巩固训练3 (1)[2022·湖北武汉高二期末]将5名核酸检测工作志愿者
分配到防疫测温、信息登记、维持秩序、现场指引4个岗位，每名志
愿者只分配1个岗位，每个岗位至少分配1名志愿者，则不同分配方案
共有(
)
A．120种 B．240种
C．360种 D．480种
答案：B
解析：首先从5人中选出2人作为一组，再与其余3人一同分配到4个不同的岗位，
选法？
(1)至少有一名队长当选；
(2)至多有两名女生当选；
(3)既要有队长，又要有女生当选．
方法归纳
有限制条件的组合问题的解题策略
巩固训练1 现有男选手3名，女选手5名，其中男女队长各1名．选
派4人外出比赛，在下列情形中各有多少种选派方法？(结果用数字表
示)
(1)至少有1名男选手；
(2)既要有队长，又要有男选手．
第2课时
课标解读
1.能正确利用组合公式及分类讨论思想解决一些有限制条件的组合

高中数学高一必修《数列的性质和递推关系》教育教学课件

高中数学高一必修《数列的性质和递推关系》教育教学课件
第2课时 数列的性质和递推关系
汇报时间：xxx
CONTENTS
1 自主学习 新知突破 2 合作探究 课堂互动 3 高效测评 知能提升 4 课后作业 巩固提升
目标导航
1．了解递推公式是给出数列的一种方法． 2．理解递推公式的含义，能够根据递推公式写出数列的前几项． 3．掌控由一些简单的递推公式求数列的通项公式的方法．
4．设数列满足a1＝1，an＝2＋an1－1(n>1)，试写出这个数列 的前4项．
解析： ∵a1＝1，∴an＝2＋an1－1(n>1)， ∴a2＝2＋a11＝3， a3＝2＋a12＝2＋13＝73， ∴a4＝2＋a13＝2＋37＝177.
合作探究 课堂互动 由递推公式写数列的项并求通项公式
已知数列{an}，a1＝2，an＋1＝2an，写出数列的前4项，料想an，并加以证明． [思路点拨] 由递推公式写出前4项 ―→ 猜想an ―→ 探寻an与an＋1的关系 ―→ 结论得证
(1)写出此数列的前5项；
(2)通过公式bn＝
an an＋1
构造一个新的数1)∵an＝an－1＋an－2(n≥3)，且a1＝1，a2＝2， ∴a3＝a2＋a1＝3，a4＝a3＋a2＝3＋2＝5， a5＝a4＋a3＝5＋3＝8. 故数列{an}的前5项依次为 a1＝1，a2＝2，a3＝3，a4＝5，a5＝8.
(1)根据递推公式写出数列的前几项，这类问题要弄清公式中各部分的关系，顺 次代入运算．
(2)由形如an＝f(n)·an－1(n≥2)的数列的递推公式求通项公式时，通常用累乘法或迭 代法，形成函数的运动变化的观点，不断地变换递推公式中的“下标”，直到可以 利用首项或前几项是解题的关键．
变式训练
1．已知数列{an}中，a1＝1，a2＝2，以后各项由an＝an－1 ＋an－2(n≥3)给出．

组合数学递推关系47页文档

组合数学递推关系47页文档

谢谢！
组合数学递推关系
56、死去何所道，托体同山阿。 57、春秋多佳日，登高赋新诗。 58、种豆南山下，草盛豆苗稀。晨兴 理荒秽 ，带月 荷锄归 。道狭 草木长 ，夕露 沾我衣 。衣沾 不足惜 ，但使 愿无违 。 59、相见无杂言，但道桑麻长。 60、迢迢新秋夕，亭亭月将圆。
61、奢侈是舒适的，否则就不是奢侈 。——CocoCha nel 62、少而好学，如日出之阳；壮而好学 ，如日 中之光 ；志而 好学， 如炳烛 之光。 ——刘 向 63、三军可夺帅也，匹夫不可夺志也。 ——孔 丘 64、人生就是学校。在那里，与其说好 的教师 是幸福 ，不如 说好的 教师是 不幸。 纳勒 尔·乔治·S·巴顿

组合数学课件第六章递推关系

组合数学课件第六章递推关系

那么
也是齐次递推关系的解。
证: 由
是齐次递推关系的解知
6.2.1 相异特征根的解法
证明：由于qi(i=1,2,…,k)是特征方程xk-b1xk-1-b2xk-2-…-bk=0的根， 由定理6.1有qin =b1 qin-1 +b2 qin-2 +…+ bk qin-k，i=1,2,…,k 将上式两边同乘以ci ，然后从1到k求和有
因此an=c1q1n+c2q2n+…+ckqkn是递推关系an=b1an-1+b2an-2+…+ bkan-k 的解。
6.2.1 相异特征根的解法
成立，则称 是递推关系的通解，其中
为任意常数。
证b61.a明2n.-11：+b由相2a定n异-2理+特…6.征+2知b根k，an的-ka的n解=解c法1q。1n只+c需2q证2n+明…，+c若kq该kn是式递满推足关递ห้องสมุดไป่ตู้推a关n=系
6.2.2 相同特征根的解法
1: 1 2: 1 3: 2 4: 3 5: 5 6: 8 7: 13
§6.1 递推关系建立例3-1
表示幼兔 表示成兔 实线表示成长 虚线表示生殖
解：设第n个月时养殖场中兔子的对数为Fn。并定义F0=1， 显然有，F1=1。 由于在第n个月时，除了有第n-1个月时养殖场中的全部兔子 Fn-1外，还应该有Fn-2对新兔子，这是因为在第n-2个月就已 经有的每对兔子，在第n个月里都应生一对新的兔子。因此可 以建立如下带初值的递推关系
（求解方法以后几节再介绍）这就是问题的解答。
例2、在一个平面中，有n个圆两两相交， 但任二个圆不相切，任三个圆无公共点， 求这n个圆把平面分成多个区域？
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第第66章章 递递推关关系系
教学目标： 1．掌握几种递推关系的建立方法； 2．理解并掌握常系数线性齐次及非齐次递推关系的求解方法； 3．能运用迭代归纳法求解递推关系； 4．记住并理解Fibonacci数的定义及递推公式，会推导
Fibonacci数的一些性质，能运用它们解决一些组合计数问 题。 重点：
例题
例2、在一个平面中，有n个圆两两相交， 但任二个圆不相切，任三个圆无面分成an个区域。 如图。易见 ，a1=2, a2=4。 现在假设前n-1个圆将平面分成了an-1 个区域，当加入第n个圆时，由题设 这个圆与前面的n-1个圆一定交于 2(n-1)个点，这2(n-1)个点把第n个圆 分成2(n-1)条弧，而每条弧正好将前 面的 n-1个圆分成的区域中的其经过 的每个区域分成2个区域，故新加入的第n个圆使所成的区域数 增加了2(n-1) 。因此可以建立如下带初值的递推关系：
解关：系要即求可§解 。6.1这递个推问关题系§建，6立.首1例先递1-必2推须关建系立递的推建关立系，然后求解递推
设这n条直线将圆分成的区域数为an，如果有n-1条直线将圆分成 a交n-。1个例显区然域题，，这那条么直再线加在入圆第内n条被直分线成与n条在线圆段内，的而其每他条n-线1条段直又线将相第
n条直线在圆内经过的区域分成两个区域。这样，加入第n条直
线后，圆内就增加了n个区域。而对于n=0，显然有a0=1，于是 对于每个整数 n，可以建立如下带初值的递推关系
an an1 n (n 1)
a0 1
求解递推关系得an
n2
n 2
2
（求解方法以后几节再介绍）这就是问题的解答。
§6.1 递推关§系6建.1立例递2 推关系的建立
注：以上各例均为经典组合数学问题，在算法分析中常用； 对普通的递推关系无一般规则可解。
§6.1 Fibonacci数§列6.应1 用递及推性关质系的建立
Fibonacci数列在组合计数中的应用
例：确定2×n棋盘用多米诺牌完美覆盖的方
法数hn。
规定h0=1. 容易看到h1=1， h2=2， h3=3。
习题
第八章 Polya定理 8.1置换群中的共轭类与轨道 8.2 Polya定理的特殊形式及其应用 本章小结
习题
********************** 课程总结
第6章 递推关系
本章主要介绍递推关系的建立及几种 常见的求解方法：
•6.1 Fibonacci数列 •6.2 常系数线性齐次递推关系的求解 •6.3 常系数线性非齐次递推关系的求解 •6.4 用迭代和归纳法求解递推关系
1: 1
§6§.16.1递递推推关关系建系立的例3建-1 立
表示幼兔
表示成兔
2: 1
实线表示成长
3: 2
虚线表示生殖
4: 3
5: 5 6: 8 7: 13
§6.1 递推关§系建6.立1例递3-2推关系的建立
解：设第n个月时养殖场中兔子的对数为Fn。并定义F0=1， 显然例有，题F1=1。 由于在第n个月时，除了有第n-1个月时养殖场中的全部兔子 Fn-1外，还应该有Fn-2对新兔子，这是因为在第n-2个月就已 经有的每对兔子，在第n个月里都应生一对新的兔子。因此可 以建立如下带初值的递推关系
（优选）组合数学课件第六章 递推关系
目录（2）
第六章 递推关系 6.1 Fibonacci数列 6.2 常系数线性齐次递推关系的求解 6.3 常系数线性非齐次递推关系的求 解 6.4 用迭代和归纳法求解递推关系 本章小结
习题 第七章 生成函数 7.1生成函数的定义和性质 7.2多重集的r-组合数 7.3正整数的划分 7.4指数生成函数与多重集的排列问 题 7.5 Catalan数和Stiring数 本章小结
an an1 2(n 1) (n 2)
a1 2
求解这个递推关系可以得到问题的解答。
§6.1 递推关§系建6.立1例递3-1推关系的建立
例题
例3、“Fibonacci兔子问题”也是组合数学 中的著名问题之一。这个问题是指：从某一 年某一月开始，把雌雄各一的一对兔子放入 养殖场中，从第二个月雌兔每月产雌雄各一 的一对新兔。每对新兔也是从第二个月起每 月产一对兔子。试问第n个月后养殖场中共 有多少对兔子？
将递推关系和初值结合起来称为带初值的递推关系。如
Dn (n 1)(Dn1 Dn2 )
D1 0, D2 1
(n 3),
an 3an1 a0 1
(n 1)
§6§.1 6递.1推关递系推建立关例系1-1的建立（Fibonacci数列）
例题
例1、在一个平面上有一个圆和n条直线， 这些直线中的每一条在圆内都同其他的直 线相交。如果没有多于三条的直线相交于 一点，试问这些直线将圆分成多少个不同 区域？
起来的方程称做一个递推关系（递归关系）。
如第3章的错排数Dn=(n-1)(Dn-1+Dn-2)，(n≥3) 和关系式an=3an-1，(n≥1)都是递推关系。
如a0=d0 , a1=d1,…, ak=dk，di为常数(i=0,1,…,k)，称为递推 关系的初值。
如D1=0, D2=1作为初值即可惟一的确定序列(D0,D1,…, Dn,…)，a0=1作为初值即可惟一的确定序列(1,3,32,…,3n,…)。
Fn Fn1 Fn2 (n 2)
F0 1, F1 1 求解上式可以得到我们所需的答案。 注：利用该式我们可以推得
(F0,F1,…,Fn,…)=(1,1,2,3,5,8,13,21,34,55,…) 常称Fn为Fibonacci数， (F0,F1,…,Fn,…)为Fibonacci数列。 Fibonacci数列在数学中是一个奇特而又常见的序列，它在算 法分析中起着重要的作用。
递推关系的建立方法、常系数线性齐次及非齐次递推关系的求 解方法、Fibonacci数和Catalan数的定义、递推公式及性质
难点： Catalan数的定义、递推公式及性质
§6.1
递推关系定义
§6.1 递推关系的建立
定义 6.1
设{H(n)}为一序列，把该序列中H(n)和它前面几 个H(i)(0≤i≤n-1)用等号（或大于、小于号）关联