問題
下図の三角柱において，を始点として，辺に沿って頂点を回移動する．すなわち，この移動経路
において，はすべて辺であるとする．また，同じ頂点を何度通ってもよいものとする．このような移動経路で，終点がのいずれかとなるものの総数を求めよ．% 図は省略
出典：京都大学 2022年度 前期日程 第2次学力試験 文系 第2問
方針
三角柱の6頂点を、 側にいる状態と 側にいる状態の2種類にまとめる。各頂点からは、同じ三角形内の頂点へ進む辺が2本、反対側の対応する頂点へ進む辺が1本出ている。したがって、終点が上側にある経路数 と下側にある経路数 は2本の漸化式を満たす。和は全経路数 、差は不変であることから を求める。
解答
終点が のいずれかである経路数を 、終点が のいずれかである経路数を とする。初期状態は であるから である。
三角柱の各頂点からは、同じ三角形内の別の2頂点へ向かう辺が2本あり、反対側の対応する頂点へ向かう辺が1本ある。したがって、 回移動後に上側 にいる経路からは、次の1回で上側へ行くものが2通り、下側へ行くものが1通りである。同様に、下側にいる経路からは、次の1回で上側へ行くものが1通り、下側へ行くものが2通りである。
よって が成り立つ。
まず和をとると である。 だから である。これは、各回の移動先が常に3通りあることとも一致する。
次に差をとると である。したがって は一定で、初期値より である。
以上の2式 を加えると である。よって求める総数は である。