I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are really interested in the expected value of the LIS length in a random permutation of the first $n$ positive integers. A [paper by Mike Phulsuksombati](http://stanford.edu/~mikep15/mike_math310_report.pdf) states
$$l\_n=2\sqrt{n}+cn^{1/6}+o(n^{1/6})$$
Where $c\approx-1.771088$ as a known asymptotic.


**Questions:** Is there a better asymptotic known? Is there a polynomial or logartihmic(in terms of $n$) time algorithm for finding $l\_n$ or approximating it to a desired precision?



State of the art in the expected length of the Longest Increasing Subsequence of a random permutation
@user61318 and @JosephORourke, thanks for the advertisement for my book.


@chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (essentially the formula you wrote, along with some additional background) and the relevant references. However, in a broader sense *much more* is understood about the asymptotic formula for $l\_n$ and where it comes from. The main important points as relates to your question are:


1. The asymptotic formula for $l\_n$ is closely related to a more detailed distributional limit for the random variable $L(\sigma\_n)$ defined as the maximal length of an increasing subsequence in a uniformly random permutation $\sigma\_n$ of order $n$. The result, known as the Baik-Deift-Johansson theorem, says that for any $t\in\mathbb{R}$,
$$ \mathbb{P}\left(
\frac{L(\sigma\_n)-2\sqrt{n}}{n^{1/6}} \le t 
\right) \to F\_2(t) \quad \textrm{as }n\to\infty,
$$
where $F\_2(t)$ is a certain probability distribution known as the Tracy-Widom distribution. $F\_2(t)$ can be expressed explicitly as
$$F\_2(t) = \exp\left(
-\int\_x^\infty (x-t)q(x)^2\,dx
\right),
$$
where $q(x)$ is the unique solution to the Painleve II ODE
$$y''(x)=2y(x)^3+xy(x)$$
with certain asymptotic boundary conditions.
2. The constant $c$ in the asymptotic formula for $l\_n=\mathbb{E}(L(\sigma\_n))$ is simply the expected value of this distribution, that is
$$ c = \int\_{-\infty}^{\infty} x F\_2'(x)\,dx. $$
3. Proving a rate of convergence estimate in the asymptotic formula for $l\_n$ would be extremely interesting (and, I suspect, difficult) and is an open problem as far as I know.


