第3問 (20点)
ぎ方について考える。 2つの点の組を2本以上の線で結ぶことはないものとする。 2点の組すべてに
れは2以上の整数とする. 1,2,…,nの番号がついた複数の点の間のいくつかを線でつなぐつな
ついてつながれているかつながれていないかが一致しているつなぎ方全体を1通りと考える。ある点
aから線でつながれた点を次々に移動して別の点に到達できるとき, aとbは連結であるというこ
とにする。また,ある点aから線でつながれた点を逆戻りせずに次々に移動して元の点aに到達でき
るとき,そのつなぎ方にはループがあるということにする.
ST
図1
図2
X//
図3
2点の組を2本以上の線で結ぶ
ことはない
(A)
2
3
このような場合はループがある
00=d+a is
なお,線と線は交差していてよいが, 交差しているところで移動の切り替えはできないものとする。
3の場合,どの2点も連結でループがないつなぎ方は3通りである.
3
1と3,2と3は連結ではない
2
(1)=4の場合について,どの2点も連結でループがないつなぎ方について考える。このときつな
方には次の(A), (B)の2つのパターンがある。
3
(B)
ラブについて
20
パターン(A)についてはたとえば図の左から順に1,2,3,4と点が並ぶ場合と右から順に 1,2,
3,4と点が並ぶ場合とが同じ場合であることに注意するとアイ通りとわかる。 パターン(B)に