問題
原点から出発して，座標平面上を軸の正の方向，または軸の正の方向に1だけ進むことを次々に行って得られる経路を道という．右の図は，原点と点とを結ぶ道の例である．原点と点を結ぶ，領域内の道の総数をとする．次の問に答えよ．
(1) ，，を求めよ．
(2) のとき，を求めよ．
(3) のとき，をとで表し，を求めよ．
出典：九州大学 1996年度 前期日程 第2次学力試験 文系 第4問
方針
条件 を破らない格子経路を数える。小さい値は実際の経路を分類し、 は上向きの一歩が最初に来ないことから数える。 は最後の一歩が右向きか上向きかで分けて漸化式を立て、初期値から和を取る。
解答
(1)
へ行くには右向きの一歩を 、上向きの一歩を として、 を二回、 を二回使う。条件 を満たすものは の二つである。したがって である。 へ行くには を三回、 を一回使う。最初に を置くと に出て条件を破るので、 は二歩目以降の三か所に置ける。よって である。 へ行く道を同様に数えると、条件を満たすものは である。したがって である。
(2)
へ行くには、 を 回、 を 回使う。 が最初に来ると となってしまうが、二歩目以降なら、その時点で少なくとも なので条件を破らない。全体で 歩あり、 を置ける場所は最初以外の か所である。よって である。
(3)
へ到達する最後の一歩を考える。最後が右向きなら直前は 、最後が上向きなら直前は である。この二つは重ならないので である。
(1), (2) より 、 だから である。したがって である。
別解。反射の考え方を使うと、 へ向かう全経路は 通りである。条件 を初めて破る道は、初めて直線 に達するところまでを反射することで、 から へ向かう道に対応する。その数は 通りである。よって となる。