基本内容

为了研究方便我们规定:从原点开始,水平向右走一个单位距离记为(1,0),垂直向上走一个单位距离记为(0,1),沿单位正方形对角线斜向上的步伐记为(1,1),沿对角线斜向下的步伐记为(1,-1)。格路V0V1V2…Vm+n5 ，Vi+1-Vi属于{(1,0),(0,1)}为从原点(0,0)到格点P(m， n)的一条非降格路。

半长为n的路是指在平面直角坐标系的第一象限内从原点(0,0)到点(2n,0)的格路,并且允许的步伐只能为(1,1), (1, -1)分别记为(U ,D)。

半长为nde Schroder格路是指在平面直角坐标系的第一象限内,从原点(0,0)到点(2n, 0)的格路,并且允许的步伐集合只能为{ (1,1),(1,-1),(2,0)}(分别记为U,D,E)。

长度为n的Motzkin路路是指在平面直角坐标系的第一象限内,从原点(0,0)到点(n,0)的格路,并且允许的步伐只能为{(1,1),(1,0),(1,-1) }(分别记为U,F,D)。

问题分析

(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。问题的解即为C(m+n,m)。1

推广

如果从（a,b）走到（c,d），其中ca,db。,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=C((c-a)+(d-b)，c-a)。

参考资料