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

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

文章目录

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

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

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

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



组合恒等式参考博客 :


【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 )

【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )

【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )

【组合数学】组合恒等式 ( 八个组合恒等式回顾 | 组合恒等式 积 1 | 证明 | 使用场景 )

【组合数学】组合恒等式 ( 组合恒等式 积之和 1 | 积之和 1 证明 | 组合恒等式 积之和 2 | 积之和 2 证明 )






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


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



非降路径问题 :


( 1 ) 基本模型


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


( 3 ) 非降路径模型应用


① 证明恒等式

② 单调函数计数

③ 栈输出





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


image.png


计算 从 ( 0 , 0 ) (0,0)(0,0) 到 ( m , n ) (m, n)(m,n) 的非降路径条数 ?



1 . 非降路径要求 :


出发点 : 从 ( 0 , 0 ) (0,0)(0,0) 出发 ;


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


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




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


步数分析 : 从 ( 0 , 0 ) (0,0)(0,0) 到 ( m , n ) (m, n)(m,n) , 向右要走 m mm 步 , 向上要走 n nn 步 ;


选取问题说明 : 总共走 m + n m+nm+n 步 , 需要选择那些步向上 , 哪些步向右 , 只要在之和 m + n m + nm+n 步中 , 将向右的 m mm 步都标定后 , 剩下的就是向上的步了 ;


选取问题组合数计算 : 因此这里只要 从 m + n m+nm+n 步中选取 m mm 步即可 , 结果是 C ( m + n , m ) C(m+n, m)C(m+n,m) , 又可以写成 ( m + n m ) \dbinom{m + n}{m}(

m

m+n


)






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


计算 从 ( a , b ) (a,b)(a,b) 到 ( m , n ) (m, n)(m,n) 的非降路径条数 ?



上述 从 ( a , b ) (a,b)(a,b) 到 ( m , n ) (m, n)(m,n) 的非降路径数 ,


等于


从 ( 0 , 0 ) (0,0)(0,0) 到 ( m − a , n − b ) (m-a, n-b)(m−a,n−b) 的非降路径数 ;



坐标平移 : 上述的原理是 坐标平移 , 将整体坐标 向左平移 a aa , 向下平移 b bb , 即可得到 从 ( 0 , 0 ) (0,0)(0,0) 到 ( m − a , n − b ) (m-a, n-b)(m−a,n−b) 的 非降路径问题基本模型 ;



因此 从 ( a , b ) (a,b)(a,b) 到 ( m , n ) (m, n)(m,n) 的非降路径条数为 C ( m − a + n − b , m − a ) C(m-a + n-b , m-a)C(m−a+n−b,m−a) 条 ;






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


计算 从 ( a , b ) (a,b)(a,b) 经过 ( c , d ) (c, d)(c,d) 到 ( m , n ) (m, n)(m,n) 的非降路径条数 ?



1 . 计算过程说明 :


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


( 2 ) 第一步 : 先计算从 ( a , b ) (a,b)(a,b) 到 ( c , d ) (c, d)(c,d) 的非降路径条数 ;


( 3 ) 第二步 : 然后计算从 ( c , d ) (c, d)(c,d) 到 ( m , n ) (m, n)(m,n) 的非降路径条数 ;


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




2 . 计算第一步


计算从 ( a , b ) (a,b)(a,b) 到 ( c , d ) (c, d)(c,d) 的非降路径条数 , 代入之前的 公式


从 ( a , b ) (a,b)(a,b) 到 ( m , n ) (m, n)(m,n) 的非降路径条数为 C ( m − a + n − b , m − a ) C(m-a + n-b , m-a)C(m−a+n−b,m−a) 条


结果为 : C ( c − a + c − b , c − a ) C(c-a + c-b , c-a)C(c−a+c−b,c−a)




3 . 计算第二步


计算从 ( c , d ) (c,d)(c,d) 到 ( m , n ) (m, n)(m,n) 的非降路径条数 , 代入之前的 公式


从 ( a , b ) (a,b)(a,b) 到 ( m , n ) (m, n)(m,n) 的非降路径条数为 C ( m − a + n − b , m − a ) C(m-a + n-b , m-a)C(m−a+n−b,m−a) 条


结果为 : C ( m − c + n − d , m − c ) C(m-c + n-d , m-c)C(m−c+n−d,m−c)




4 . 乘法法则


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


从 ( a , b ) (a,b)(a,b) 经过 ( c , d ) (c, d)(c,d) 到 ( m , n ) (m, n)(m,n) 的非降路径条数是 : C ( c − a + c − b , c − a ) C ( m − c + n − d , m − c ) C(c-a + c-b , c-a) C(m-c + n-d , m-c)C(c−a+c−b,c−a)C(m−c+n−d,m−c)


目录
相关文章
|
算法 Linux 数据处理
《操作系统》—— 处理机调度算法
《操作系统》—— 处理机调度算法
2712 1
|
机器学习/深度学习 人工智能 数据可视化
机器学习:详解贝叶斯网络+例题分析
机器学习:详解贝叶斯网络+例题分析
3300 0
机器学习:详解贝叶斯网络+例题分析
|
算法 调度
详解操作系统四大常用的作业调度算法(FCFS丨SJF丨HRRN丨RR)
详解操作系统四大常用的作业调度算法(FCFS丨SJF丨HRRN丨RR)
6378 0
|
10月前
|
前端开发 JavaScript
使用 try-catch 语句来捕获 Promise 中的异常
【10月更文挑战第26天】使用try-catch语句捕获Promise中的异常是一种非常实用的技术,能够使异步代码的错误处理更加清晰、可控,提高程序的可靠性和稳定性。在实际开发中,合理地运用try-catch语句以及其他相关的错误处理机制,可以有效地应对各种可能出现的异常情况,为用户提供更好的体验。
|
人工智能 Cloud Native 数据管理
重磅升级,阿里云发布首个“Data+AI”驱动的一站式多模数据平台
阿里云发布首个AI多模数据管理平台DMS,助力业务决策提效10倍
1382 17
|
11月前
|
人工智能 监控
unsloth微调LLama3,指令遵循优化模型独家秘籍
【10月更文挑战第15天】在人工智能领域,LLama3是一款基于Transformer架构的先进语言模型,通过大量数据训练,学习了语言的模式和规律。然而,面对特定任务时,仍需微调以提升性能。unsloth工具为此提供了极大便利,通过数据增强、正则化、学习率调整等优化策略,有效提升了LLama3的指令遵循能力。本文将介绍如何利用unsloth对LLama3进行微调,包括数据准备、模型加载、微调过程及性能监控等步骤。
426 4
|
机器学习/深度学习 Kubernetes 算法框架/工具
容器服务 ACK 大模型推理最佳实践系列一:TensorRT-LLM
在 ACK 中使用 KServe 部署 Triton+TensorRT-LLM
|
存储 网络协议 网络架构
使用ensp搭建路由拓扑,并使用BGP协议实现网络互通实操
使用ensp搭建路由拓扑,并使用BGP协议实现网络互通实操
550 0
|
机器学习/深度学习 算法 数据挖掘
周志华《机器学习》课后习题(第九章):聚类
周志华《机器学习》课后习题(第九章):聚类
1367 0
周志华《机器学习》课后习题(第九章):聚类
油管公式(全)
油管公式(全)
5111 0