問題
文字を頂点とし、辺がである図を考える。7文字列で、各が6文字のいずれか、かつ隣接する2文字が相異なり図の辺で結ばれているものの総数を求めよ。
出典：京都大学 2003年度 後期日程 第2次学力試験 後期・理系 後期 第6問
方針
図は三角形 と三角形 の対応する頂点を結んだ三角柱の辺グラフであり、各頂点から出る辺は3本である。最初の文字を選んだ後は、直前の頂点に隣接する3頂点から次を選ぶ。
解答
図の各頂点に接続する頂点を調べると
であり、どの頂点の次数も3である。また辺は異なる二頂点を結ぶので、辺を選ぶ限り条件(ii)も自動的に満たされる。
最初の文字 は6通りに選べる。 が決まったとき、 はそれに辺で結ばれた3文字から選べるので常に3通りである。遷移は6回あるから、総数は
である。