MathDB

Increasing Subsequence Length

Source: KöMaL A. 759

March 20, 2022

combinatoricskomalpermutationexpected value

Problem Statement

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}.