Problem 595

Incremental Random Sort

A deck of cards numbered from 1 to n is shuffled randomly such that each permutation is equally likely.

The cards are to be sorted into ascending order using the following technique:

Look at the initial sequence of cards. If it is already sorted, then there is no need for further action. Otherwise, if any subsequences of cards happen to be in the correct place relative to one another (ascending with no gaps), then those subsequences are fixed by attaching the cards together. For example, with 7 cards initially in the order 4123756, the cards labelled 1, 2 and 3 would be attached together, as would 5 and 6.
The cards are ‘shuffled’ by being thrown into the air, but note that any correctly sequenced cards remain attached, so their orders are maintained. The cards (or bundles of attached cards) are then picked up randomly. You should assume that this randomisation is unbiased, despite the fact that some cards are single, and others are grouped together.
Repeat steps 1 and 2 until the cards are sorted.

Let S(n) be the expected number of shuffles needed to sort the cards. Since the order is checked before the first shuffle, S(1) = 0. You are given that S(2) = 1, and S(5) = 4213/871.

Find S(52), and give your answer rounded to 8 decimal places.

改进随机排序

一叠编号为1至n的卡片被随机地洗匀，每一种排列出现的可能性相等。

这些卡片将按照以下步骤排序成递增顺序：

查看卡片的初始顺序。如果卡片已经有序，那么没必要采取额外的操作。否则，如果卡片中有任何子序列已经有序（连续的上升序列），则这些子序列会被固定在一起。例如，如果7张卡片的初始顺序是4123756，那么标号为1，2和3的卡片和标号为5和6的卡片将会分别固定在一起。
将这些卡片扔到空中“洗牌”，注意已经被固定在一起的卡片在这个过程中不会被分开，因此其顺序不发生改变。这些卡片（或卡片组）然后被随机地捡起来，你可以假设这一随机操作是无偏的，即使其中有些卡片只有一张，而有些则被固定在一块儿。
重复步骤1和2，直到卡片已经有序。

记S(n)为将这些卡片排序所需要的期望洗牌次数。因为在第一次洗牌前会检查顺序，故S(1) = 0。已知S(2) = 1，以及S(5) = 4213/871。

求S(52)，并将你的答案保留8位小数。