某城市有 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$ ✓，与组合数算出的结果一致。