演算第 5 題：
(1)如下之街道圖中，每一小格皆是邊長 1 單位的正方形。
為了方便，我們簡稱此街道圖的規格為8×4。
小松從 A 點出發，要沿著街道走捷徑到 B 點。因為溽暑難耐，
他每走 1 單位或每走2 單位就停下來休息一下。
請問，在如上所述的條件下，從 A 到 B 共有幾種走法？
(2)我們可將(1)中之街道圖規格改為 m×n (m,n為正整數)，而在(1)所述的規
則下，考慮從 A 到B 共有幾種走法。
設規格為m×n , m×(n+1) , (m+1)×(n+1) 的街道圖所對應之走法數分別是
x , y , z ，請將 z 用 x, y 及 m,n 表示。
解答：
令
f(n) = 路徑長共需
n 單位時，每次走
1 或
2 單位就需停頓休息，所有停頓點排列的可能數。
則
f(1)=1,\, f(2)=2,\, f(n)=f(n-1)+f(n-2) \,\forall n\geq 3
| n | 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
|
| f(n) | 1 | 2
| 3
| 5
| 8
| 13
| 21 | 34 | 55 | 89 | 144
| 233
|
(1)
所求
=\mbox{A 到 B 的所有捷徑走法}\times f(12)=495\times233=115335.
(2)
\displaystyle x=\frac{\left(m+n\right)!}{m!n!}f(m+n)\Rightarrow f(m+n)=\frac{x\cdot m!\cdot n!}{\left(m+n\right)!}
\displaystyle y=\frac{\left(m+n+1\right)!}{m!\left(n+1\right)!}f(m+n+1)\Rightarrow f(m+n+1)=\frac{y\cdot m!\cdot \left(n+1\right)!}{\left(m+n+1\right)!}
\displaystyle z=\frac{\left(m+n+2\right)!}{\left(m+1\right)!\left(n+1\right)!}f(m+n+2) \Rightarrow f(m+n+2)=\frac{z\cdot (m+1)!\cdot (n+1)!}{\left(m+n+2\right)!}
再由
f(m+n+2)=f(m+n+1)+f(m+n)，可得如下
\displaystyle\frac{z\cdot (m+1)!\cdot (n+1)!}{\left(m+n+2\right)!} =\frac{y\cdot m!\cdot \left(n+1\right)!}{\left(m+n+1\right)!}+\frac{x\cdot m!\cdot n!}{\left(m+n\right)!},
化簡後可得如下，
\displaystyle z=\frac{m+n+2}{m+1}y+\frac{(m+n+2)(m+n+1)}{(m+1)(n+1)}x.
