从
到
除端点外 , 不接触对角线的非降路径数 ?
此时无法使用基本公式进行处理了 , 必须使用组合对应的思想 ;
上图示例中 , 从
出发到
, 只有两个端点
和
接触了对角线 , 中间的每一步都没有接触该对角线 ;
1 . 计算原理 , 先计算对角线下方的非降路径 : 这里只计数在对角线下方的非降路径数 , 因为 对角线上下的非降路径是对称的 , 因此这里 先将对角线下方的非降路径计算出来 ;
对角线下方的非降路径 乘以
, 就是总的 不接触对角线的 非降路径数 ;
2 . 出发点分析 : 从
出发后 , 第
步必须向右走 , 走到
点 , 如果向上走就不能再下来了 ( 否则就会接触对角线 ) , 此时就不是对角线下方的非降路径了 ;
3 . 终止点分析 :
到达
点 , 只有两种情况 :
到右边的
点 , 该路径在对角线上方 ;
到上边的
点 , 该路径在对角线下方 ;
由于当前只统计 对角线下方的非降路径数 , 到达
之前的一步 , 必须是从
位置走到
的 ;
4 . 对应关系
上述 出发点之后必须走
点 , 终点之前必须走
点 ,
因此 在对角线下方 从
到
除端点外 , 不接触对角线的非降路径数
等价于
从
到
除端点外 , 不接触对角线的非降路径数
5 . 计算
到
除端点外 , 不接触对角线的非降路径数
下面讨论 “从
到
除端点外 , 不接触对角线的非降路径数” 的计数方式 ;
使用反向思路考虑 , 统计 从
到
之间 , 接触过对角线的非降路径 , 剩下的就是不接触对角线的路径 ;
上述两者的总数是
个 ;
上图是 一个 “从
到
, 接触过对角线的非降路径” ,
图中的 红色点
是该非降路径最后接触对角线的位置 , 前面可能有多次接触该对角线 ;
将
点 与
点 之间的蓝色线段 , 关于对角线作对称图像 , 得到 红色线段 ,
上图中的 蓝色线段 起点是
, 那么对应的 红色线段的起点必定是
;
每一条从
开始到
的接触对角线的非降路径 , 都有蓝色的线段 , 都可以使用对称的方法 , 得到一个 从
到达
点的红色线段 ;
这里就得到了一个组合对应关系 :
每条从
出发 , 到
的 非降路径 ( 即将 红色的线段 与 剩余的 黑色线段 可以拼接起来的路径 )
都可以与
从
出发 , 到
的接触对角线的 非降路径
一一对应 ;
因此如果要求 "从
出发 , 到
的接触对角线的 非降路径数 " , 可以通过求 “从
出发 , 到
的 非降路径数” ;
“从
出发 , 到
的 非降路径数” 可以使用公式进行计算 , 结果为
,
对应的 "从
出发 , 到
的接触对角线的 非降路径数 " , 结果为
;
6 . 计算
到
的所有非降路径数
根据公式计算即可 , 结果是 :
7 . 计算
到
除端点外 , 不接触对角线的非降路径数
"
到
除端点外 , 不接触对角线的非降路径数" 就是
"
到
的所有非降路径数" 减去 "
到
除端点外 , 不接触对角线的非降路径数" ;
8 . 计算 从
到
除端点外 , 不接触对角线的非降路径数
上面的
只是计算的是对角线下面的非降路径数 ,
从
出发 , 到
不接触对角线的非降路径数 , 再乘以
, 就得到了本题目的最终结果 ;
从
到
除端点外 , 不接触对角线的非降路径数
最终结果是 :