格路問題

問題起源

格路問題是組合數學中的經典模型問題，它的思想最早源於19世紀的選票問題。對格路的系統研究主要起源於20世紀中葉，記錄了最早將選票問題轉化為計數的格路問題並利用反射原理計算得到相應的組合數。從前人對格路的研究成果來看，許多學者都是利用生成函式的方法來研究不同步伐集合下的格路，或者是研究在不同限制條件下的格路計數問題，利用這種方法可以求得格路的個數以及格路與x軸所圍區域面積的計算。

問題定義

在平面直角坐標系中，橫坐標和縱坐標都是整數的點稱為平面格點，平面格路是指在所有的平面格點中，從一點到另一點只走格點的路，格路的長度是指其所走的路的步數。一般情況下，研究的都是第一象限的平面格路。從(0,0)點出發沿x軸或y軸的正方向每步走一個單位，最終走到(m,n)點的路徑數。

如右圖所示。無論怎樣走法，在x方向上一共走m步，在y方向上一共走n步。若用一個字母x來表示x方向上的一步，字母y來表示y方向上的一步，則(0,0)→(m,n)的每一條路徑可表示為m 個x與n個y的一個有重排列。

問題推廣

　　　將每一個有重排列的x與y分別編號，可得m!n!個m+n元的無重全排列。設所求方案數為P(m+n;m,n)，則P(m+n;m,n)*m!*n! = (m+n)! ，故P(m+n;m,n)= (m+n)! / (m!*n!) = C(m+n,m)，即|(0,0) (m,n)| = C(m+n,m) 。如左圖所示，此結論可推廣到一般，設c≥a,d≥b,則由(a,b)到(c,d)的簡單格路數為|(a,b) (c,d)| = C((c-a)+(d-b), (c-a))