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

互いに異なる $6$ 個の実数 $a_1,a_2,\dots ,a_6$ を、比較だけを使って昇順に並べかえる。$1$ 回の比較では、ある $2$ 個 $a_i,a_j$ について「$a_i<a_j$ か」を調べ、「はい」か「いいえ」の答えを得る。どのような比較ソートのアルゴリズムでも、最悪の場合の比較回数は決定木による下界 $\lceil {\log }_{2}6!\rceil$ 以上になる。この下界 $\lceil {\log }_{2}6!\rceil$ の値を求めよ。ただし、$\lceil x\rceil$ は $x$ 以上の最小の整数を表す。

互いに異なる $5$ 個の実数 $a_1,a_2,a_3,a_4,a_5$ を昇順に並べかえる。使える操作は「$2$ つの要素を比べて、どちらが小さいかを知る」比較だけとし、$1$ 回の比較の結果は $2$ 通りであるとする。このような比較にもとづくソートの手順を決定木で表すと、葉はそれぞれ $1$ つの並べ方（順列）に対応し、すべての並べ方が葉として現れる必要がある。この考え方から得られる「最悪の場合の比較回数の下界」$\lceil {\log }_{2}5!\rceil$ の値を求めよ。

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

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