MathDB

A permutation of

\{1, 2, \dots, 7\}

is chosen uniformly at random. A partition of the permutation into contiguous blocks is correct if, when each block is sorted independently, the entire permutation becomes sorted. For example, the permutation

(3, 4, 2, 1, 6, 5, 7)

can be partitioned correctly into the blocks

[3, 4, 2, 1]

and

[6, 5, 7]

, since when these blocks are sorted, the permutation becomes

(1, 2, 3, 4, 5, 6, 7)

. Find the expected value of the maximum number of blocks into which the permutation can be partioned correctly.

Problem Statement