说明
本文参考了组合数学课件,精简整理了一下内容并谈谈自己的理解
定义
设{
an
a
n
}为一序列,把该序列中
an
a
n
和它前面几个
ai
a
i
(0≤i≤n)关联起来的方程称做一个递推关系(递归关系)。
类似于
a0
a
0
=1,
a1
a
1
=1的叫做初值
初值+递推关系=带初值的递推关系
说白了就是用前面推出来的值推出当前值,然后再推出后面的值的一个递推式,和dp的递推式差不多。
经典例子
1.在一个平面上有一个圆和n条直线,这些直线中的每一条在圆内都同其他的直线相交。如果没有多于三条的直线相交于一点,试问这些直线将圆分成多少个不同区域?
设这n条直线将圆分成的区域数为
an
a
n
,如果有n-1条直线将圆分成
an−1
a
n
−
1
个区域,那么再加入第n条直线与在圆内的其他n-1条直线相交。显然,这条直线在圆内被分成n条线段,而每条线段又将第n条直线在圆内经过的区域分成两个区域。这样,加入第n条直线后,圆内就增加了n个区域。而对于n=0,显然有
a0
a
0
=1,所以有如下递推公式:
an=an−1+n(n>=1)
a
n
=
a
n
−
1
+
n
(
n
>=
1
)
a0=1
a
0
=
1
展开可以看出类似等差数列,化简后得:
an=n∗(n+1)+22
a
n
=
n
∗
(
n
+
1
)
+
2
2
2.“Hanoi塔”问题:n个大小不一的圆盘依半径的大小,从下而上的套在柱子A上。如图所示。现要求将所有的圆盘从柱子A上全部移到柱子C上,每次只允许从一根柱子上转移一个圆盘到另一根柱子上,且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上的n个圆盘全部转移到柱子C上去?
用
an
a
n
表示从一根柱子上的
n
n
个圆盘全部转移到另一根柱子上的转移次数。显然,a1=1,
a2=3
a
2
=
3
。当
n≥3
n
≥
3
时,要将柱子A上的
n
n
个圆盘转移到柱子C上,可以这样设想。先把柱子A上的n−1个圆盘转移到柱子B上,这需要转移
an−1
a
n
−
1
次;然后把柱子A上最后一个圆盘转移到柱子C上,显然这需要转移一次;最后再把柱子B上的n-1个圆盘转移到柱子C上,这也需要转移
an−1
a
n
−
1
次。到此时转移完毕,一共转移了
2an−1+1
2
a
n
−
1
+
1
次。于是可以建立如下带初值的递推关系:
an=2an−1+1(n>=2)
a
n
=
2
a
n
−
1
+
1
(
n
>=
2
)
a1=1
a
1
=
1
3.“Fibonacci兔子问题”也是组合数学中的著名问题之一。这个问题是指:从某一年某一月开始,把雌雄各一的一对兔子放入养殖场中,从第二个月雌兔每月产雌雄各一的一对新兔。每对新兔也是从第二个月起每月产一对兔子。试问第n个月后养殖场中共有多少对兔子?
设第
n
n
个月时养殖场中兔子的对数为Fn。并定义
F0=1
F
0
=
1
,显然有,
F1=1
F
1
=
1
。
由于在第
n
n
个月时,除了有第n−1个月时养殖场中的全部兔子
Fn−1
F
n
−
1
外,还应该有
Fn−2
F
n
−
2
对新兔子,这是因为在第
n−2
n
−
2
个月就已经有的每对兔子,在第
n
n
个月里都应生一对新的兔子。因此可以建立如下带初值的递推关系.
Fn=Fn−1+Fn−2
F0=F1=1
F
0
=
F
1
=
1
该数列即为Fibonacci数列
5.在一个平面中,有n个圆两两相交,但任二个圆不相切,任三个圆无公共点,求这n个圆把平面分成多个区域?
设这
n
n
个圆将平面分成an个区域。易知,
a1=2,a2=4
a
1
=
2
,
a
2
=
4
。
现在假设前
n−1
n
−
1
个圆将平面分成了
an−1
a
n
−
1
个区域,当加入第
n
n
个圆(虚线圆)时,由题设这个圆与前面的n−1个圆一定交于
2(n−1)
2
(
n
−
1
)
个点,这
2(n−1)
2
(
n
−
1
)
个点把第n个圆分成
2(n−1)
2
(
n
−
1
)
条弧,而每条弧正好将前面的
n−1
n
−
1
个圆分成的区域中的其经过的每个区域分成
2
2
个区域,故新加入的第n个圆使所成的区域数增加了
2(n−1)
2
(
n
−
1
)
。因此可以建立如下带初值的递推关系:
an=an−1+2(n−1)
a
n
=
a
n
−
1
+
2
(
n
−
1
)
a1=2
a
1
=
2
5.设有
n
n
个数b1,b2,...,bn的连乘积为
b1×b2×...×bn
b
1
×
b
2
×
.
.
.
×
b
n
。试求不同的结合方式数(加括号的方式)。
设不同的结合方式数为
an
a
n
。定义
a1=1
a
1
=
1
,显然有
a2=1
a
2
=
1
。
由于对乘积
b1×b2×…×bn
b
1
×
b
2
×
…
×
b
n
的任一结合方式,必有某一个k使得最后的运算为积
b1×b2×…×bk
b
1
×
b
2
×
…
×
b
k
与积
bk+1×bk+2×…×bn
b
k
+
1
×
b
k
+
2
×
…
×
b
n
相乘。当k 固定时,对乘积
b1×b2×…×bk
b
1
×
b
2
×
…
×
b
k
有
ak
a
k
种不同的结合方式,而对乘积
bk+1×bk+2×…×bn
b
k
+
1
×
b
k
+
2
×
…
×
b
n
有
an−k
a
n
−
k
种不同的结合方式。由乘法法则知,对某一个
k
k
共有ak∗an−k 种不同的结合方式。再由加法法则即得如下带初值的递推关系:
an=∑n−1k=1ak∗an−k
a
n
=
∑
k
=
1
n
−
1
a
k
∗
a
n
−
k
a1=1,a2=1
a
1
=
1
,
a
2
=
1