4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.