【组合数学】非降路径问题 ( 非降路径问题概要说明 | 非降路径问题基本模型 | 非降路径问题拓展模型 1 非原点起点 | 非降路径问题拓展模型 2 有途经点 )

韩曙亮

发布于 2023-03-28 18:26:28

7880

发布于 2023-03-28 18:26:28

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

组合恒等式参考博客 :

一、非降路径问题概要说明

非降路径问题是组合计数模型 , 利用该组合计数模型 , 可以处理一些常见的组合计数问题 ;

非降路径问题 :

( 1 ) 基本模型

( 2 ) 在限制条件下的非降路径个数

( 3 ) 非降路径模型应用

① 证明恒等式
② 单调函数计数
③ 栈输出

二、非降路径问题基本模型

计算从

(0,0)

到

(m, n)

的非降路径条数 ?

1 . 非降路径要求 :

出发点 : 从

(0,0)

出发 ;

移动坐标要求 : 向右走整数坐标 , 水平和垂直坐标都走整数长度 ;

移动方向要求 : 每次只能向右 , 或者向上移动 ; 不能向左 , 向下走 ;

2 . 转为选取问题 : 将其变成一个选取问题 ,

步数分析 : 从

(0,0)

到

(m, n)

, 向右要走

m

步 , 向上要走

n

步 ;

选取问题说明 : 总共走

m+n

步 , 需要选择那些步向上 , 哪些步向右 , 只要在之和

m + n

步中 , 将向右的

m

步都标定后 , 剩下的就是向上的步了 ;

选取问题组合数计算 : 因此这里只要从

m+n

步中选取

m

步即可 , 结果是

C(m+n, m)

, 又可以写成

\dbinom{m + n}{m}

二、非降路径问题拓展模型 1

计算从

(a,b)

到

(m, n)

的非降路径条数 ?

上述从

(a,b)

到

(m, n)

的非降路径数 ,

等于

从

(0,0)

到

(m-a, n-b)

的非降路径数 ;

坐标平移 : 上述的原理是坐标平移 , 将整体坐标向左平移

a

, 向下平移

b

, 即可得到从

(0,0)

到

(m-a, n-b)

的非降路径问题基本模型 ;

因此从

(a,b)

到

(m, n)

的非降路径条数为

C(m-a + n-b , m-a)

条 ;

三、非降路径问题拓展模型 2

计算从

(a,b)

经过

(c, d)

到

(m, n)

的非降路径条数 ?

1 . 计算过程说明 :

( 1 ) 分步处理 : 使用分步计数原理 , 对应乘法法则 ;

( 2 ) 第一步 : 先计算从

(a,b)

到

(c, d)

的非降路径条数 ;

( 3 ) 第二步 : 然后计算从

(c, d)

到

(m, n)

的非降路径条数 ;

( 4 ) 乘法法则 : 根据乘法法则 , 将上述两个结果相乘 , 最终就是结果要求的非降路径条数 ;

2 . 计算第一步

计算从

(a,b)

到

(c, d)

的非降路径条数 , 代入之前的公式

从

(a,b)

到

(m, n)

的非降路径条数为

C(m-a + n-b , m-a)

条

结果为 :

C(c-a + c-b , c-a)

3 . 计算第二步

计算从

(c,d)

到

(m, n)

的非降路径条数 , 代入之前的公式

从

(a,b)

到

(m, n)

的非降路径条数为

C(m-a + n-b , m-a)

条

结果为 :

C(m-c + n-d , m-c)

4 . 乘法法则

将上述两个非降路径数相乘 , 就是最终结果 ;

从

(a,b)

经过

(c, d)

到

(m, n)

的非降路径条数是 :

C(c-a + c-b , c-a) C(m-c + n-d , m-c)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-20，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度