523 : 先頭のソート I

リストをソートするための次のアルゴリズムを考える。

1. リストの先頭から始めて、隣接する要素の各ペアを順番に調べる。

2. 要素の順序が正しくない場合:

   1. ペアの最小の要素をリストの先頭に移動する。

   2. 手順 1 からプロセスを再開する。

3. すべてのペアが正しい順序になったら停止する。

例えばリスト $\{4,1,3,2\}$ は次のようにソートされる。

• $\underline{4\,1}\,3\,2$ (4と1は順序が間違っているため、1をリストの先頭に移動する)

• $1\,\underline{4\,3}\,2$ (4と3は順序が間違っているので、3をリストの先頭に移動する)

• $\underline{3\,1}\,4\,2$ (3と1は順序が間違っているので、1をリストの先頭に移動する)

• $1\,3\,\underline{4\,2}$ (4と2は順序が間違っているため、2をリストの先頭に移動する)

• $\underline{2\,1}\,3\,4$ (2と1は順序が間違っているので、1をリストの先頭に移動する)

• $1\,2\,3\,4$ (リストはソートされた)

リスト $L$ をソートするためにステップ2aを実行する回数を $F(L)$ とする。 例えば、$F(\{\,4\,1\,3\,2\,\}) = 5$である。

$E(n)$ を、整数 $\{1, 2, \dots, n\}$ のすべての順列 $P$ に対する $F(P)$の期待値とする。 $E(4) = 3.25$, $E(10) = 115.725$が与えられている。

$E(30)$ を求めよ。答えは小数点以下2桁に丸めて与えよ。