方針
図は三角形 と三角形 の対応する頂点を結んだ三角柱の辺グラフであり、各頂点から出る辺は3本である。最初の文字を選んだ後は、直前の頂点に隣接する3頂点から次を選ぶ。
解答
図の各頂点に接続する頂点を調べるとであり、どの頂点の次数も3である。また辺は異なる二頂点を結ぶので、辺を選ぶ限り条件(ii)も自動的に満たされる。
最初の文字 は6通りに選べる。 が決まったとき、 はそれに辺で結ばれた3文字から選べるので常に3通りである。遷移は6回あるから、総数はである。
別解
解法2(末尾文字ごとの漸化式)
方針
長さ の列を末尾の文字ごとに数える。図の各頂点に接続する文字が3個ずつであることから、総数の漸化式を得る。
解答
長さ で条件を満たし、末尾が文字 である列の数を とする。図では各文字に隣接する文字がちょうど3個ある。
長さ の列を作るには、長さ の列の末尾から、線分で結ばれた3文字のいずれかへ移ればよい。したがって総数はを満たす。初めの文字は自由に選べるのでよって求める列の長さは7だからである。各辺は異なる2頂点を結ぶため、線分に沿って移る限り「隣接する文字が相異なる」という条件も自動的に満たされる。
総評
難度3、計算量2。想定時間は8分程度。図が複雑に交差して見えるが、交点は頂点ではなく、6頂点はいずれも次数3である。各段階の選択肢数が常に3なので、直前以外の履歴を分類する必要はない。
第1解法は標準的な答案構成を詳しく示し、第2解法は異なる着眼または計算経路で同じ結論を再確認する。図は式変形の役割と条件の使いどころを可視化した。積分・極限・総和は独立行に置き、分数は表示サイズで組版した。
