# What is the expected length of the longest increasing subsequence of a random permutation of the first n natural numbers?

What is the average length of the longest increasing subsequence of a random permutation of the first n natural numbers?

• IIRC, this is asymptotic as $2\sqrt{n}$. Don't think there is a known closed form. – Macavity Mar 31 '13 at 6:45
• @Macavity do you know a reference for this fact ? – Ewan Delanoy Mar 31 '13 at 6:59
• @ewanDelanoy search for aldous & diaconis, 1995 Don't have the exact reference handy. – Macavity Mar 31 '13 at 7:21
• Ok - here it is. – Macavity Mar 31 '13 at 7:43