格路計數

這是一個經典的組合數學問題。在平面直角坐標系中,橫坐標和縱坐標都是整數的點稱為平面格點,平面格路是指在所有的平面格點中,從一點到另一點只走格點的路,格路的長度是指其所走的路的步數。

為了研究方便我們規定:從原點開始,水平向右走一個單位距離記為(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)。

基本介紹

• 中文名：格路計數
• 外文名：Price channel clock number
• 適用領域：排列組合
• 套用學科：數學

問題分析

(0,0)→(m,n)的每一條路徑可表示為m個x與n個y的一個有重排列。將每一個有重排列的x與y分別編號，可得m!n!個m+n元的無重全排列。問題的解即為C(m+n,m)。

推廣

如果從（a,b）走到（c,d），其中ca,db。,則由(a,b)到(c,d)的簡單格路數為|(a,b)(c,d)|=C((c-a)+(d-b)，c-a)。

格路計數