从网格左上角出发，每次只能向右或向下移动一格。

穿过 $2\times 2$ 网格共有 6 条这样的路径。

穿过 $20\times 20$ 网格共有多少条路径？

提示

每次打开一个

每条路径使用的向右和向下步数都一样。

在整个步骤序列中，选择哪些位置放向右移动。

解答

认真尝试后再打开

把路径编码成字符串

每条合法路径都恰好包含 20 次向右移动和 20 次向下移动，区别只在于它们的排列顺序。因此，每条路径就是一个长度为 40、包含 20 个 $R$ 和 20 个 $D$ 的字符串。

选择 20 个位置放置向右移动：

$$(\genfrac{}{}{0ex}{}{40}{20})=\frac{40!}{20!20!}=\mathrm{137,846,528,820.}$$

图形让人想要尝试搜索；而移动序列把它显露成了一个标准的组合对象。