格路問題

從

(0,0)

點出發，每步只能沿

x

軸或

y

軸的正方向每步走一個單位，最終走到

(m,n)

點，有多少條路徑？

解答：

這個問題的解答很簡單。因為一共要走

m+n

步，其中必定有

m

步是向左走一格、有

n

步是向上走一格。

格路問題

所以方案數就是

{m+n \choose m} ={m+n \choose n}

。

格路問題的一般化

從

(m_0,n_0)

點出發，每步只能沿

x

軸或

y

軸的正方向每步走一個單位，最終走到

(m+m_0,n+n_0)

點，有多少條路徑？

解答：

{m+n \choose m} ={m+n \choose n}

，道理不解釋。

不能“接觸”對角線的格路問題

假設要從

(0,0)

到

(m,n)

（其中

m> n

），要求途徑的每個點

(a,b)

都滿足

a> b

（除起點外）。

格路問題

解答：

首先第一步一定是

(0,0)\rightarrow (1,0)

之後每1條接觸對角線的道路都一一對應1條從

(0,1)

到

(m,n)

的道路（就是第一次接觸對角線之前的道路做關於對角線的對稱）：

格路問題

從

(0,1)

到

(m,n)

的路線方案數是：

{m+(n-1) \choose m}

。

所以結果是

{(m-1)+n \choose n} -{m+(n-1) \choose m} =\frac{(m+n-1)!}{m!n!}(m-n) ={m+n \choose m} \frac{m-n}{m+n}

。

特別是當

m=n+1

時，結果是

\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}{2n \choose n}

——這就是著名的

卡特蘭數（Catalan number）

C_n

。

例如

n=2

時，

格路問題

n=3

時，

格路問題

不能“穿越”對角線的格路問題

假設要從

(0,0)

到

(m,n)

（其中

m\geq n

），要求途徑的每個點

(a,b)

都滿足

a\geq b

。

格路問題

解答：

相當於將對角線上移一格，移到

l_2:y=x+1

。轉化為不可“接觸”

l_2

的問題。

格路問題

然後每一條從

(0,0)

到

(m,n)

的、接觸

l_2

的路徑都一一對應於一條從

(-1,1)

到

(m,n)

的路徑。

格路問題

從

(-1,1)

到

(m,n)

的路徑數是

{ (m+1)+(n-1) \choose m+1}

。

所以總方案數就是

{m+n \choose m}-{(m+1)+(n-1) \choose m+1} = {m+n \choose m} \left(1-\frac{n}{m+1}\right)

。

當

m=n

時，方案數是：

{ 2n \choose n }\left(1-\frac{n}{n+1}\right) = { 2n \choose n }\left(\frac{1}{n+1}\right)

。

n=4

的情況：

格路問題