組合的路徑計數

參數方程

在 $m\times n$ 矩形格中，每步僅向右或向上，從左下到右上共有 $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ 條最短路徑。動畫可逐條畫出路徑，或把路徑疊合在網格上。

路徑數：

遞迴（到達 $(i,j)$ 的路徑數）：

互動說明

• 向右步數 m／向上步數 n：決定網格尺寸，各為 2 到 9
• 單一路徑：逐步繪製一條由向右、向上組成的路徑，畫完再換下一條；畫面不標 R、U 字母
• 路徑疊合：半透明疊加路徑，最多畫 900 條；這是繪圖上限，不是 $N(m,n)$ 的值
• 計數場：以節點的圓大小標示到達該點的路徑數，圓越大路徑越多；畫面不標出數字
• 新路徑：單一路徑模式下跳到一條隨機路徑；其他兩種模式畫面不變

觀察重點

• 一條路徑就是在 $m+n$ 步中選出哪 $m$ 步向右，所以 $N(m,n)=\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$；改選向上的步，得到相同的個數 $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$
• 角落 $(m,n)$ 標的是完整的路徑數；格內節點 $(i,j)$ 標的是 $P(i,j)=\left(\genfrac{}{}{0ex}{}{i+j}{i}\right)$，屬於較前面的二項式係數，不是整個第 $m+n$ 列
• 本頁計數的是路徑，不畫帕斯卡三角形，也不畫停在對角線下方的卡特蘭路徑

相關作品

• 帕斯卡三角形
• 二項式展開的幾何意義
• 卡特蘭數

延伸閱讀

• 組合數學（維基百科）