方針
三つの を大きな三角形の左下・右下・上に配置して考える。二頂点間の道を「残る頂点を通らない 型」と「通る 型」に分けたまま連結する。大きな図形で を通るか否かごとに、三つの小図形で選ぶ型を列挙して漸化式を作る。
解答
(1)
の六頂点からなる図で、同じ点を二度通らない道を列挙する。 から へ行く道は、 を通らないものが7通り、通るものが3通りである。したがって(2)
三つの小図形 のそれぞれで、二つの端点を結ぶ道は、第三の端点を通らない 型と、第三の端点を通る 型に分かれる。
を通らない道を、小図形ごとの型で分類すると、に対応する場合が得られる。これらは連結点を通る順序が異なり、互いに重ならない。よって一方、 を通る道は、上側の小図形で第三頂点を通る場合を同様に分けると(3)
を代入してしたがって
総評
目安は30分。図を目で追うだけでは重複・漏れが起きるので、各 内の道を 型と 型に固定して積で数えることが核心である。(2)の五つ・二つの型が互いに排反であることを連結点の通過順序で確認する。(3)は代入計算なので、ここを確実に得点する。



