某城市有 4 條東西向與 4 條南北向的道路，構成一個方格網。有人從西北角 A 走到東南角 B，在每個路口只能選擇往東或往南。共有幾條不同的路線？

Step-by-step solution

1. 1

   先數出每條路線必須走的步數。 兩個方向各有 $4$ 條道路，就等於各有 $3$ 個街廓，所以每條路線都恰好由

   $3\ \text{次向東}\quad\text{與}\quad 3\ \text{次向南}$

   組成，總共 $6$ 步 — 而且每一條路線都一樣，這正是讓計數變成純粹組合問題的原因。

2. 2

   把一條路線轉成一個字串。 一條路線完全由它各步的順序決定，也就是由一串 $6$ 個字母、三個 E 與三個 S 所描述，例如 $EESESS$。不同字串對應不同路線，每條路線也都對應一個字串，所以「數路線」就等於「數字串」。

3. 3

   決定向東那幾步的位置。 一旦決定 $6$ 個位置中哪 $3$ 個放 E，剩下的就由 S 填滿。方法數為

   $\binom{6}{3}$

4. 4

   算出這個二項式係數。

   $\binom{6}{3}=\frac{6!}{3!\,3!}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20$

   $\boxed{20\ \text{條路線}}$

5. 5

   用格子上的巴斯卡三角形交叉檢查。 在每個路口標上從 $A$ 走到該點的路線數：最上面那一列與最左邊那一行全都是 $1$，其餘每個節點都是它上方節點與左方節點之和。這樣會建出 $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ / $1,4,10,20$ 這幾列 — 而角落 $B$ 上寫著 $20$ ✓，與二項式係數的計數吻合。