方針
条件 を破らない格子経路を数える。小さい値は実際の経路を分類し、 は上向きの一歩が最初に来ないことから数える。 は最後の一歩が右向きか上向きかで分けて漸化式を立て、初期値から和を取る。
解答
(1) へ行くには右向きの一歩を 、上向きの一歩を として、 を二回、 を二回使う。条件 を満たすものは の二つである。したがって である。 へ行くには を三回、 を一回使う。最初に を置くと に出て条件を破るので、 は二歩目以降の三か所に置ける。よって である。 へ行く道を同様に数えると、条件を満たすものは である。したがって である。
(2) へ行くには、 を 回、 を 回使う。 が最初に来ると となってしまうが、二歩目以降なら、その時点で少なくとも なので条件を破らない。全体で 歩あり、 を置ける場所は最初以外の か所である。よって である。
(3) へ到達する最後の一歩を考える。最後が右向きなら直前は 、最後が上向きなら直前は である。この二つは重ならないので である。
(1) , (2) より 、 だから である。したがって である。
別解
解法2
方針
反射原理を使い、条件 を満たす経路数の一般式を先に求める。全経路から、初めて に達する不適経路を引けば、各小問が同じ式から直ちに得られる。
解答
(1)
へ至る全経路は 通りである。条件 を破る経路について、初めて直線 に達するまでを直線 に関して反射する。すると、これは から へ至る経路と一対一に対応する。その数はである。したがってこれより(2)だから(3)
最後の一歩が右向きか上向きかで分けるとまた一般式から直接である。したがって
総評
格子経路を条件付きで数える基本問題。目安時間は18分。小問の流れは、直接列挙、一次の場合、最後の一歩による漸化式という設計になっている。 では「上向きの一歩が最初以外ならよい」と言い切れる理由を添えると、条件 の確認が明確になる。 2解法の結論を相互照合し、定義域、端点、場合分け、図示範囲まで確認した。