I am interested in asymptotics for the number of permutations of $[n^2]$ with longest increasing subsequence of length $n$. The first few values are:
1,13,89497,1744049683213,320348783206253047567401
The next few terms are approximately 1.39502e+39, 3.03849e+59, 6.19775e+84, 2.03345e+115.
This sequence is not in the OEIS.
By numerical experimentation it seems the function may approximately be of the form:
$$A \cdot B^n \cdot(n^2-n-1)!$$
for constants $A$ and $B$ and $n \geq 2$.
By taking logs and fitting for $n$ going from $2$ to $9$, we get $A \approx 0.003822$ and $B \approx 58.3669$.
@DavidMoews gave a very nice proof for the number of permutations of $[2n]$ with longest increasing subsequence of length $n$. However I can't see how to use the proof technique here because the argument in the $[2n]$ case no longer applies. Specifically,
but these tableaux are just the tableaux with $\lambda\vdash n$ with
an extra row of length $n$ inserted at the top
is no longer true.
What can be used instead?
Best Answer
Here's an approximation. Let $m=n^2$, and let $L_{m}$ be the length of the longest increasing subsequence.
In the paper
ON THE DISTRIBUTION OF THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE OF RANDOM PERMUTATIONS[*] "On Increasing Subsequences of I.I.D. Samples" DEUSCHEL, J.-D., & ZEITOUNI, O. (1999) Combinatorics, Probability and Computing, 8(3), doi:10.1017/s0963548399003776, it's proved the result:$$P(L_m < x \sqrt{m}) \to e^{-2 m H(x)} \tag {1}$$
in the range $0<x<2$, with $H(x)=-\frac12+ \frac{x^2}{8} + \log \frac{x}{2} -(1+\frac{x^2}{4}) \log(\frac{2 x^2}{4+x^2})$
Using the continuity approximation $P(L_m = c) \approx F'(c)$ where $F(c) = P(L_m \le c) \approx P(L_m < c)$ we are led to
$$ P(L_m= \sqrt{m}) \approx e^{-m a} \, b \sqrt{m} \tag {2}$$
where $a=2 \,H(1) = 0.1544324$ and $b = -2 \, H(1) \, H'(1) = 0.0450719$
Letting $S_m = m! \, P(L_m= \sqrt{m})$ be the desired counting, we get
$$\begin{align} \log S_m &\approx m \log m - m + \frac12(\log 2 \pi m)- a m + \frac12 \log(m) + \log b \\ &= m \log m - (1+a) m + \log(m) + \log(b) + \frac12(\log 2 \pi) \tag {3}\\ &\approx m \log m - 1.1544 \, m + \log (0.113 \,m) \end{align}$$
The graph shows the comparison between the approximation $(3)$ and the exact values (in log scale).
If we wish to fit $S_n$ to a factorial, we should rather write something like
$$S_m \approx \left( m - a \, \frac{m}{\log m}\right)\large! \tag4$$
with the same $a$ as before. Of course, that means $x! = \Gamma(x+1)$. For some reason (perhaps mere luck), approximation $(4)$ works even better (considerably so) than $(3)$, at least in that range.
[*] The original paper had an error, a $2$ factor was missing, as hinted by numerical fitting.