$n$を$4$以上の整数とする．$1$番から$n$番までの番号がふられたボールが$1$つずつある．このとき，以下の問いに答えよ．
(1) 以下のような操作でボールを$1$列に並べる：
(ⅰ) $1$番のボールを適当な位置におく．
(ⅱ) $2$番のボールを$1$番のボールの左または右に同じ確率でおく．
(ⅲ) $3$番のボールをすでに並んでいる$2$つのボールの左または間または右に同じ確率でおく． [$\tokeishi$] 以下$n$番まで番号順に，$k$番のボールを，すでに並んでいるボールの一番左または間または一番右に同じ確率でおく，ことを繰り返す．
例えば，左から$2$番，$1$番，$3$番のボールが並んでいるとき，$4$番のボールが$2$番と$1$番の間におかれる確率は$\displaystyle \frac{1}{4}$である．
$n$番のボールをおき終えたとき，$i$番のボールが左から$j$番目に並ぶ確率は$\displaystyle \frac{1}{n}$であることを証明せよ．ただし，$i$と$j$は$1$以上，$n$以下の整数とする．
(2) $(1)$のボールの列を，（左から）番号順に並び替えるため，以下の操作を考える：
隣り合った$2$つのボールの組で，左のボールの番号が右のそれより大きなもの（入れ替え可能な組と呼ぶ）が存在するとき，そのようなボールの組を$1$つ選び，入れ替える．
入れ替え可能な組が複数あった場合に，入れ替える組をどのように選んだとしても，この操作を繰り返すことにより，すべてのボールの列は，必ず番号順の列になることを証明せよ．
(3) $(2)$の操作の回数は，入れ替える組の選び方とは無関係であることを証明せよ．
(4) $(2)$においてボールの列を番号順に並べ替えるとき，$i$番のボールを，より番号の小さいボールと入れ替える回数の期待値を$E_i$とする．このとき， \[ \sum_{i=1}^n E_i \] を求めよ．