Proof for number of permutations of $[n^2]$ with longest increasing subsequence of length n.

Question

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?

Answer 1

Let $\ell_n$ be the longest increasing subsequence (LIS) in a permutation of $[n^2]$ chosen uniformly at random. Writing $T_n$ for the number of permutations of $[n^2]$ with LIS of length $n$ then $$T_n = (n^2)! P(\ell_n = n)$$ since $P(\ell_n = n)$ is the proportion of permutations with LIS $n$.

Since $$P(\ell_n = n) = P(\ell_n \leqslant n) - P(\ell_n \leqslant n-1) = P(\ell_n \leqslant n) - P(\ell_n \leqslant (1-n^{-1})n),$$ the large deviation result in Deuschel & Zeitouni, i.e. $$\frac1{n^2} \log(P(\ell_n < x n)) \to -2 H(x) \;\; \text{as $n \to \infty$, for} \;\; 0 < x <2$$ with $x=1$ and $x=1-n^{-1}$, gives $$T_n \approx (n^2)! \left\{e^{-2n^2H(1)} - e^{-2n^2 H(1-n^{-1})}\right\}$$

This approximation of $T_n, n=2,\dots,9$ produces

12.0982, 85999.7, 1.71451e+12, 3.20664e+23, 1.41747e+39, 3.12697e+59, 6.44930e+84, 2.13673e+115.

Answer 2

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.