文章目录
一、限制条件的非降路径数
一、限制条件的非降路径数
----
从
(0,0)
到
(n,n)
除端点外 , 不接触对角线的非降路径数 ?...计算原理 , 先计算对角线下方的非降路径 : 这里只计数在对角线下方的非降路径数 , 因为 对角线上下的非降路径是对称的 , 因此这里 先将对角线下方的非降路径计算出来 ;
对角线下方的非降路径 乘以...2
, 就是总的 不接触对角线的 非降路径数 ;
2 ....使用反向思路考虑 , 统计 从
(1, 0)
到
(n,n-1)
之间 , 接触过对角线的非降路径 , 剩下的就是不接触对角线的路径 ;
上述两者的总数是
C(2n-2 , n-1)...这里就得到了一个组合对应关系 :
每条从
(0,1)
出发 , 到
(n, n-1)
的 非降路径 ( 即将 红色的线段 与 剩余的 黑色线段 可以拼接起来的路径 )
都可以与
从
(1,0)