A. 759

Part of KoMaL A Problems 2019/2020

Problems(1)

Increasing Subsequence Length

Source: KöMaL A. 759

We choose a random permutation of

1,2,\ldots,n

with uniform distribution. Prove that the expected value of the length of the longest increasing subsequence in the permutation is at least

\sqrt{n}.

combinatoricskomalpermutationexpected value