首页 > 代码库 > 组合数学及其应用——格路径与Schroder数
组合数学及其应用——格路径与Schroder数
格路径问题是探讨在如下所示中的一个格点图上,从(0,0)位置到达(p,q)所有可能的情况数。我们称这样的通路为一条格路径。
格点图:
· · · · ·
· · · · ·
· · · · ·
· · · · ·
· · · · ·
通常按照笛卡尔坐标系的习惯给各个格点标号,即左下角为(0,0),横坐标沿右侧增大,纵坐标沿上侧增大。
现在我们去考察一种特殊的格路径:对于某个格点图,我们规定该格路径不允许超过y=x这条直线,我们称这样的格路径为下对角线矩形格路径。
这里和我们在卡特兰数一节中某个实例应用(穿越街区)联系在了一起,在那里,我们得到对于方阵格点图,从(0,0)到(n,n)的下对角线矩形格路径的数目是第n个卡特兰数,这里我们将通过下一个定理看到,上面这种情形其实是该定理下的一个特殊情况。
组合数学及其应用——格路径与Schroder数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。