一共有多少種走法

尚代清

[題目]如圖1，按1，2，3，…，9的順序從“1”走到“9”，一共有多少種走法?

[分析與解]觀察圖1發現：

1從“1”出發走到“2”，不論是走到第二行的第一個“2”，還是第二個“2”，都各只有1種走法，就是1～2(第二行的第一個“2”)、1～2(第二行的第二個“2”)，于是給這兩個“2”都標記下標“1”(見圖2，下同)。

2從“1”出發走到“3”，如果要走到第三行的第一個或第三個“3”，也都各只有一種走法，分別是1～2(第二行的第一個“2”)～3(第三行的第一個“3”)、1～2(第二行的第二個“2”)～3(第三行的第三個“3”)，于是給這兩個“3”都標記下標“1”；如果要走到第三行的第二個“3”，就先要經過上一行的第一個或第二個“2”，已經知道，先走到上一行的第一個“2”有1種走法，先走到上一行的第二個“2”也只有1種走法，所以走到第三行的第二個“3”一共有1+1=2(種)走法，就是1～2(第二行的第一個“2”)～3(第三行的第二個“3”)、1～2(第二行的第二個“2”)～3(第三行的第二個“3”)，于是給這個“3”標記下標“2”。

3從“1”出發走到“4”，如果要走到第四行的第一個“4”，只有1種走法，就給這個“4”標記下標“1”；如果要走到第四行的第二個“4”，只有先經過上一行的第一個或第二“3”，而先走到上一行的第一個“3”有1種走法，先走到上一行的第二個“3”有2種走法，所以走到第四行的第二個“4”，共有1+2=3(種)走法，就是1～2(第二行的第一個“2”)～3(第三行的第一個“3”)～4(第四行的第二個“4”)、1～2(第二行的第一個“2”)～3(第三行的第二個“3”)～4(第四行的第二個“4”)、1～2(第二行的第二個“2”)～3(第三行的第二個“3”)～4(第四行的第二個“4”)，于是給這個“4”標記下標“3”：同理，給第四行的第三個“4”標記下標“3”，給第四個“4”標記下標“1”。

依次類推，容易發現這個規律：后來標記的數，等于它的“肩”上(在上一行)兩個標數的和(當然，有的缺左“肩”，有的缺右“肩”)。按照這個規律，從左到右、自上而下標數，最終標到“9”，就會標出”70”來。所以，按1，2，3，…，9的順序從“1”走到“9”，共有70種走法。