13
满足要求的路径一定不会经过(0,1)点 满足要求的路径一定不会经过(0,1)点. 可以建立一个新坐标系: 原点在( 可以建立一个新坐标系: 原点在(-1,0), 这样我们原来( 这样我们原来(m,n)点在新坐标系里面 的坐标就成了( +1,n 自然m+1>n 的坐标就成了(m+1,n), 自然m+1>n. 从新坐标系原点出发到达( +1,n 从新坐标系原点出发到达(m+1,n)点的 路径, 如果所经过的点( 满足a 路径, 如果所经过的点(a,b)满足a>b, 则 (1,0)点后的路径正好是满足条件的路 (1,0)点后的路径正好是满足条件的路 (图4.3) 径. (图4.3) 所以只需求出(0,0)到 +1,n 不经过y=x 所以只需求出(0,0)到(m+1,n)不经过y=x 上点的路径数. 上点的路径数.
19
对于(4.1)中的 阶齐次递归关系: 对于(4.1)中的r阶齐次递归关系: 中的r H n a1 H n1 a 2 H n 2 a r H n r = 0 我们定义如下的一元 r 次方程: 次方程:
11
这样的向量有m 这样的向量有m个0元素, n个1元素, 共 元素, 元素, C(m+n, 有C(m+n, m)个. 可以建立(m+n) 0,1向量与从 向量与从(0,0)点到 可以建立(m+n)维0,1向量与从(0,0)点到 点路径间一一对应: (0,0)点出 达(m,n)点路径间一一对应: 从(0,0)点出 =0沿 轴方向走一个单位, 发, 第i步: 若ai=0沿x轴方向走一个单位, =1沿 轴方向走一个单位, 若ai=1沿y轴方向走一个单位, i=1,…,m+n. =1,…,m+n. 要保证顾客能顺利地买到票相当于要 必须满足x 求路径上各点( 求路径上各点(x,y)必须满足x≥y.
12
我们的问题相当于求从(0,0)点到 我们的问题相当于求从(0,0)点到(m,n) 点到( 点的路径中, 不穿越过y=x线上点的路 点的路径中, 不穿越过y=x线上点的路 径数(可以经过), 径数(可以经过), 即需求出路径上各点 (x,y)满足条件 x≥y的路径数. 的路径数. 这个问题与例 的问题不一样, 这个问题与例2的问题不一样, 那里不 允许经过y=x上点 现在可以经过, 上点. 允许经过y=x上点. 现在可以经过, 但不 许穿过y=x这条直线是的点 这条直线是的点. 许穿过y=x这条直线是的点. 但是我们可以把这个问题转化为例 但是我们可以把这个问题转化为例2中 的情况来加以解决. 的情况来加以解决. 实际上相当于进行 一个坐标变换. 一个坐标变换.
(m,n)
(0,1) (0,0) (1,0)
图4.2
4
问题也可以提为: 求从( 问题也可以提为: 求从(0,1)点到(m,n)点 点到(m,n)点 并且所经过的点( 均满足条件a 并且所经过的点(a,b)均满足条件a<b的 路径数. 路径数. 由于m 显然从( 点到( 由于m<n, 显然从(1,0)点到(m,n)点的每 一条路径, 必然穿过y=x上的点 上的点. 一条路径, 必然穿过y=x上的点. 的路径可以分成两类: 从(0,0)到(m,n)的路径可以分成两类: 第一类: 经过( 第一类: 经过(1,0)点. 这类路径至少要穿 过一次y=x上的点 上的点. 过一次y=x上的点. 第二类: 经过( 第二类: 经过(0,1)点. 这类路径可以分成 两部分. 两部分.
《组合数学》 组合数学》
第四讲
常系数递归关系
1
第四讲: 第四讲: 常系数递归关系
I. 路径问题选讲 II. 常系数齐次递归关系 常系数齐次 齐次递归关系 (1) 特征值为不同的实数 (2) 特征值均为实数但是有重根 (3) 特征值有复根* 特征值有复根* III. 常系数非齐次递归关系* III. 常系数非齐次递归关系* 非齐次递归关系
2
I. 与路径有关的问题
例1 设某地的街道把城市分割成矩形方格, 每 设某地的街道把城市分割成矩形方格, 个方格称为块. 某甲从家里出发上班, 个方格称为块. 某甲从家里出发上班, 向东 要走m 向北要走n 要走m块, 向北要走n块. 问某甲上班的路径 有多少种? 有多少种? (m,n) 某甲上班路径数等于 从原点到 (m, n)点的 总径数: 总路径数:
10
例3 音乐会票价为50元一张, 排队买票的 音乐会票价为50元一张 元一张, 顾客中有m位持50元的钞票 位持100 元的钞票, 顾客中有m位持50元的钞票, n位持100 元的钞票. 售票处没有50元的零钱 元的零钱. 元的钞票. 售票处没有50元的零钱. 问 有多少种排队的办法使购票能顺利进 不出现找不出钱的状态, 行, 不出现找不出钱的状态, 假定每位 顾客只买一张票, 而且m 顾客只买一张票, 而且m≥n. 分析: 可以用m+n维 1向量来表示一种 分析: 可以用m+n维0, 1向量来表示一种 排队状态, 令该向量为: 排队状态, 令该向量为: (a1,a2,…, am+n), 其中a =1,2,… m+n. 其中ai=0 或1, i=1,2,…,m+n. ai=0表示第i个顾客持50元的票款; =0表示第 个顾客持50元的票款 表示第i 元的票款; ai=1表示第i个顾客持100元的票款. =1表示第 个顾客持100元的票款 表示第i 元的票款.
16
教材第 教材第3版p.53给出的结果是错误的. 53给出的结果是错误的 给出的结果是错误的. 只要对于m 只要对于m=3, n=2的情况简单验证一 下就可以发现书中的结果不对. 下就可以发现书中的结果不对. 习题" 构成的字符串中, 习题"由n个0和n个1构成的字符串中, 在任意前k个字符串中, 在任意前k个字符串中,0的个数不少 的个数的字符串有多少? 于 1 的个数的字符串有多少 ? " 与买 票问题相同. 票问题相同. 路径问题很典型, 希望大家能掌握. 路径问题很典型, 希望大家能掌握.
9
(2) N=从(0,1)点到(m,n)点的路径数 (0,1)点到 点到( - 从(1,0)点到(m,n)点的路径数 (1,0)点到 点到( N=C(m+nN=C(m+n-1, m)-C(m+n-1,m-1). C(m+n-1,m
m + n 1 m + n 1 N = m 1 m 1 1 = ( m + n 1)! m! ( n 1)! ( m 1)! n! ( m + n 1)! (n m ) = m! n!
7
(m,n)
Pk
P2 (0,1) (0,0) P1
(1,0)
图4.2
8
这样建立了从(1,0)点到 这样建立了从(1,0)点到(m,n)点的一条 点到( 路径与从(0,1)到 点且过y=x上点 路径与从(0,1)到(m,n)点且过y=x上点 的路径之间的一一对应关系. 的路径之间的一一对应关系. 利用以上结论, 利用以上结论, 可以用两种方式得到 题目中要求的路径数目N 题目中要求的路径数目N: (1) N=从(0,0)点到(m,n)点的总路径数 (0,0)点到 点到( - 2×从(1,0)点到(m,n)点的路径数 (1,0)点到 点到( N=C(m+n,m)-2C(m+n-1,m-1) =C(m+n, 2C(m+n-1,m =C(m+n=C(m+n-1, m)-C(m+n-1,m-1). C(m+n-1,m
14
(m,n) (m+1,n)
(0,1) (-1,0) (0,0) (1,0)
图4.3
15
这样变换之后, +1相当于 这样变换之后, m+1相当于例2中的n, 相当于例 中的n 则相当于其中的m 而n则相当于其中的m. 由此我们知道 所要求的路径数目N如下: 所要求的路径数目N如下:
N = C (m + n + 1 1, n) C (m + n + 1 1, n 1) = C (m + n, n) C (m + n, n 1) = C (m + n, m) C (m + n, n 1) (m + n)! (m + n)! = m! n! (m + 1)!(n 1)! mn+1 (m + n)! = (m + 1)! n!
17
II. 常系数齐次线性递归关系 常系数齐次 齐次线性递归关系
常系数线性递归关系有齐次 常系数线性递归关系有齐次和非齐次 齐次和 两种. 是一个递归数列. 两种. 设Hn是一个递归数列. 常系数齐次递归关系: 常系数齐次递归关系:
Hn a1Hn1 a2 Hn2 ar Hnr = 0 (4.1)
C ( m + n, m ) = C ( m + n, n).
(0,0)
图4.1
3
例2 从(0,0)点到达(m,n)点, 其中m<n. 要求中 点到达( 其中m<n. 间所经过的路径上的点( 恒满足a 间所经过的路径上的点 (a,b)恒满足a<b, 问 有多少不同的路径? 有多少不同的路径? 解 与 例 1 不同 , 现 不同, 在要求路径不经 在要求路径 不经 y=x上的点 上的点. 过y=x上的点. 这 点第1 样, 从(0,0)点第1 步必须到( 步必须到(0,1)点, 而不允许到( 而不允许到 ( 1 , 0 ) 点.
5
第一部分: 不经过y=x上任何的点 第一部分: 不经过y=x上任何的点. 这正 上任何的点. 是题目中要求的路径. 是题目中要求的路径. 第二部分: 至少经过一次y=x上的点 上的点. 第二部分: 至少经过一次y=x上的点. 下面我们说明: 第一类路径数目正好 下面我们说明: 第一类路径数目正好 等于第二类中第二部分的路径数目 第二类中第二部分的路径数目. 等于第二类中第二部分的路径数目. 这可以通过建立起从(1,0)到 这可以通过建立起从(1,0)到(m,n)点的 路径与从(0,1)到 点但经过y=x线上 路径与从(0,1)到(m,n)点但经过y=x线上 点的路径间之间一一对应关系来加以 证明. 证明.