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

格点图:

· · · · ·

· · · · ·

· · · · ·

· · · · ·

· · · · ·

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

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

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

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

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

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

05-11 20:19