Combinatorics Harvard-MIT
2018


Problem - 4498

A permutation of $\{1,\ 2,\ \cdots,\ 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 partitioned correctly. 


report an error