  We find a two term asymptotic expansion for the optimal expected value of a
sequentially selected monotone subsequence from a random permutation of length
n. A striking feature of this expansion is that tells us that the expected
value of optimal selection from a random permutation is quantifiably larger
than optimal sequential selection from an independent sequences of uniformly
distributed random variables; specifically, it is larger by at least (1/6)log n
+O(1).
