一共有多少种走法

尚代清

[题目]如图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种走法。