アルゴリズムと計算量の問題

互いに異なる $6$ 個の実数を、$6!$ 通りの並べ方のどれもが等確率 $\frac{1}{720}$ で起こるように並べ、配列 $A[1],A[2],\dots ,A[6]$ を作る。$1\leqq i<j\leqq 6$ を満たす整数の組 $(i,j)$ のうち、$A[i]>A[j]$ となるものを転倒といい、転倒の個数を $X$ とする（$X$ は、この配列を挿入ソートで昇順に並べかえるときに行われる隣り合う要素の交換の回数に等しい）。$X$ の期待値 $E(X)$ を求めよ。

互いに異なる $7$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[7]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,6$ の順に、$j=1,2,\dots ,7-k$ の順で $A[j]$ と $A[j+1]$ を比べ、$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

最初の並びは、$7$ 個の数の $7!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

互いに異なる $10$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[10]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,9$ の順に、各 $k$ について $j=1,2,\dots ,10-k$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

入力の並びは $10!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる対象の数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 対象の数が $m$ 個（$m\ge 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等しい確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較し（比較は $m-1$ 回）、ピボットより小さい数の組と大きい数の組に分ける。それぞれの組に対して、同じ手順を繰り返す。

ピボットの選択はすべて互いに独立に行われるものとする。このとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 並べる数が $m$ 個（$m\geqq 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個の数とそれぞれ $1$ 回ずつ比較し、ピボットより小さい数の組と大きい数の組に分ける。そのあと、それぞれの組に同じ手順を行う。

ピボットの選択は毎回ほかの選択と独立に行うものとする。数どうしの比較は上の「ピボットと残りの数との比較」だけで行われるとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。