方針
8個の端の完全な組分けは 通りである。 は全てのひもが自分自身で結ばれる場合, は4本すべてが1つの輪になる場合として数える。期待値は も数えて分布を完成させてから計算する。
解答
4本のひもを区別し,各ひもの2つの端も区別して考える。8個の端を2個ずつ4組に分ける総数は通りである。
(1)
となるのは,4本すべてのひもについて,同じひもの両端どうしを結ぶ場合だけである。したがって確率はである。
(2)
1つの端を固定し,そこから1つの大きな輪をたどる。固定した端と結ぶ相手は,他の3本のひもの6個の端のいずれかである。次に,そのひもの反対側の端と結ぶ相手は,まだ使っていない2本のひもの4個の端のいずれかである。さらに次は残り1本のひもの2個の端のいずれかで,最後は固定したひもの残りの端に結ばれる。よって となる組分けは通りである。したがって確率はである。
(3)
となるのは,1本だけでできる輪が2つ,残り2本でできる輪が1つの場合である。1本だけでできる輪にする2本の選び方は 通り,残り2本の端を互い違いに結ぶ方法は2通りであるから, は12通りである。
したがって となる場合は通りである。よって期待値はである。
別解
解法2
方針
(1) ,(2)は端の組分けを直接数える。(3)では, 本の無作為な結び方へ第 のひもを挿入する生成法を考える。新しい輪が1個増える確率は なので,期待値を漸化的に求められる。
解答
端を区別すると,8個の端を2個ずつ組にする総数は通りである。
(1)
となる結び方は,各ひもの両端を結ぶ1通りだけなので,確率はである。
(2)
1本目の片端から大きな輪をたどる。次に結ぶ端は他の3本から6通り,その次は未使用の2本から4通り,さらに残り1本から2通りである。よって は 通りで,確率はである。
(3)
本のひもを結んだときの輪の数の期待値を とする。 本の無作為な結び方に第 のひもを加える。新しいひもの一方の端の相手は,残る 個の端の中で一様である。
相手が新しいひものもう一方の端なら独立な輪が1個増え,その確率は である。それ以外なら,既存の結び目1本を切ってその間に新しいひもを挿入した形になり,輪の個数は変わらない。この操作は 本の端のすべての組分けを等確率に生成する。したがってである。 だからを得る。
総評
難度5,計算量4。想定時間は15分程度。端を区別すれば全事象は105通りである。直接解法は を数えて分布を完成させ,別解は新しいひもを挿入したとき輪が増える確率 を足し上げる。 の48通りを回転や向きで二重計数すること,期待値を確率でなく結び方の個数だけで加重することが典型的な失点である。