首页 > 代码库 > 组合数学及其应用——格路径与Schroder数

组合数学及其应用——格路径与Schroder数

  格路径问题是探讨在如下所示中的一个格点图上,从(0,0)位置到达(p,q)所有可能的情况数。我们称这样的通路为一条格路径。

  格点图:

  · · · · ·

  · · · · ·

 · · · · ·

 · · · · ·

 · · · · ·

 通常按照笛卡尔坐标系的习惯给各个格点标号,即左下角为(0,0),横坐标沿右侧增大,纵坐标沿上侧增大。

  技术分享

 现在我们去考察一种特殊的格路径:对于某个格点图,我们规定该格路径不允许超过y=x这条直线,我们称这样的格路径为下对角线矩形格路径。

 这里和我们在卡特兰数一节中某个实例应用(穿越街区)联系在了一起,在那里,我们得到对于方阵格点图,从(0,0)到(n,n)的下对角线矩形格路径的数目是第n个卡特兰数,这里我们将通过下一个定理看到,上面这种情形其实是该定理下的一个特殊情况。

  技术分享

    技术分享

   

组合数学及其应用——格路径与Schroder数