---

Problem 523

---

First Sort I

Consider the following algorithm for sorting a list:

1. Starting from the beginning of the list, check each pair of adjacent elements in turn.
2. If the elements are out of order:
   • Move the smallest element of the pair at the beginning of the list.
   • Restart the process from step 1.
3. If all pairs are in order, stop.

For example, the list { 4 1 3 2 } is sorted as follows:

• 4 1 3 2 (4 and 1 are out of order so move 1 to the front of the list)
• 1 4 3 2 (4 and 3 are out of order so move 3 to the front of the list)
• 3 1 4 2 (3 and 1 are out of order so move 1 to the front of the list)
• 1 3 4 2 (4 and 2 are out of order so move 2 to the front of the list)
• 2 1 3 4 (2 and 1 are out of order so move 1 to the front of the list)
• 1 2 3 4 (The list is now sorted)

Let F(L) be the number of times step 2a is executed to sort list L. For example, F({ 4 1 3 2 }) = 5.

Let E(n) be the expected value of F(P) over all permutations P of the integers {1, 2, …, n}.
You are given E(4) = 3.25 and E(10) = 115.725.

Find E(30). Give your answer rounded to two digits after the decimal point.

---

首位排序 I

考虑如下的数列排序算法：

1. 从数列的起始位置开始，逐一比较每一对相邻的数。
2. 如果相邻的数顺序有误：
   • 将其中较小的数移至数列的首位。
   • 回到第1步。
3. 如果每一对相邻的数均已有序，算法结束。

例如，数列{ 4 1 3 2 }的排序过程如下：

• 4 1 3 2 （4和1顺序有误，将1移至数列的首位）
• 1 4 3 2 （4和3顺序有误，将3移至数列的首位）
• 3 1 4 2 （3和1顺序有误，将1移至数列的首位）
• 1 3 4 2 （4和2顺序有误，将2移至数列的首位）
• 2 1 3 4 （2和1顺序有误，将1移至数列的首位）
• 1 2 3 4 （数列排序完毕）

记F(L)为数列L排序过程中将数移至首位的次数。例如，F({ 4 1 3 2 }) = 5。

记E(n)为数集{1, 2, …, n}的任意排列P进行排序所得F(P)的期望值。
已知E(4) = 3.25以及E(10) = 115.725。

求E(30)。将你的答案四舍五入到小数点后两位数字。

---