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

互いに異なる $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!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

$1,2,\dots ,10$ を $1$ 列に並べた配列 $A[1],A[2],\dots ,A[10]$ がある。並び方は $10!$ 通りのどれも同様に確からしいとする。この配列を、次のバブルソートで昇順に並べかえる。

$i=1,2,\dots ,9$ の順に、各 $i$ について $j=1,2,\dots ,10-i$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を入れかえ（交換し）、そうでなければ何もしない。

このバブルソートで行われる交換の回数の期待値を求めよ。

互いに異なる $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)$ を求めよ。

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

$i=2,3,\dots ,6$ の順に、次の操作を行う。$x=A[i]$ とし、$j=i-1$ から始めて、$j\geqq 1$ である間「$A[j]$ と $x$ を比較し、$A[j]>x$ ならば $A[j]$ を $A[j+1]$ に移して $j$ を $1$ 減らす。$A[j]<x$ ならばそこで止める」をくり返す。止まったとき（または $j=0$ になったとき）、$A[j+1]=x$ とする。

ここで、数どうしの比較（$A[j]$ と $x$ の比較）だけを数え、$j\geqq 1$ かどうかの判定は数えない。最初の配列が $6$ 個の数の $6!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

互いに異なる $8$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[8]$ の最大値と最小値を、次のアルゴリズムで同時に求める。

• 最初に $M\leftarrow A[1]$, $m\leftarrow A[1]$ とする。
• $i=2,3,\dots ,8$ の順に、次の操作を行う。
• まず $A[i]$ と $M$ を比較する。$A[i]>M$ ならば $M\leftarrow A[i]$ とし、この $i$ についての操作を終える（$m$ とは比較しない）。
• $A[i]<M$ ならば、続けて $A[i]$ と $m$ を比較する。$A[i]<m$ ならば $m\leftarrow A[i]$ とする。

配列の並び方は $8!$ 通りのどれも同様に確からしいとする。このアルゴリズムで行われる要素どうしの比較（$A[i]$ と $M$ の比較、$A[i]$ と $m$ の比較）の回数の期待値を求めよ。