Mathematics
Examination
Test
Archives
【4】 を以上の整数とする.番から番までの番号がふられたボールがつずつある.このとき,以下の問いに答えよ.
(1) 以下のような操作でボールを列に並べる:
1. 番目のボールを適当な位置におく.
2. 番のボールを番のボールの左または右に同じ確率でおく.
3. 番のボールをすでに並んでいるつのボールの左または間または右に同じ確率でおく.
4. 以下番まで番号順に,番のボールを,すでに並んでいるボールの一番左または間または右に同じ確率でおく,ことを繰り返す.
例えば,左から番,番,番のボールが並んでいるとき,番のボールが番と番の間におかれる確率はである.
番のボールをおき終えたとき,番のボールが左から番目に並ぶ確率はであることを証明せよ.ただし,とは以上,以下の整数とする.
(2) (1)のボールの列を,(左から)番号順に並び替えるため,以下の操作を考える:
隣り合ったつのボールの組で,左のボールの番号が右のそれより大きなもの(入れ替え可能な組と呼ぶ)が存在するとき,そのようなボールの組をつ選び,入れ替える.
入れ替え可能な組があった場合に,入れ替える組をどのように選んだとしても,この操作を繰り返すことにより,すべてのボールの列は,必ず番号順の列になることを証明せよ.
(3) (2)の操作の回数は,入れ替える組の選び方とは無関係であることを証明せよ.
(4) (2)においてボールの列を番号順に並べ替えるとき,番のボールを,より番号の小さいボールと入れ替える回数の期待値をとする.このとき,
を求めよ.