Combinatorics – Number of Permutations of [2n] with Longest Increasing Subsequence of Length n

Question

In A267433 the result $a(n) \sim 16^n (n-1)! / (\pi e^2)$ is quoted as being from Vaclav Kotesovec with a link to his page. However I can't find the result in any of those papers.

Does anyone know a reference or proof for this result?

Answer 1

This can be worked out pretty simply using the Robinson–Schensted correspondence. One of the consequences of this correspondence is that the number of permutations on $m$ letters with longest ascending subsequence of length $k$ equals $$\sum_{\lambda\vdash m,\ \lambda_1=k} \left(\frac{m!}{H(\lambda)}\right)^2,$$ where the sum is over all Young tableaux $\lambda$ with $m$ cells and first row of length $k$. [1] Here, a Young tableau is an array of cells arranged in rows whose length decreases from top to bottom, with each row having its leftmost edge in the same place, $$ \begin{array}{l} \square \square \square \square \square \\ \square \square \\ \square \end{array} $$ and $H(\lambda)$ is the product of the number of cells in each hook in $\lambda$, where a hook consists of a cell in the tableau together with all cells directly underneath and to its right. You can write $\lambda_1\ge\lambda_2\ge\cdots$ for the row lengths of the tableau and $\lambda'_1\ge\lambda'_2\ge\cdots$ for its column lengths.

Given this, if you want the number of permutations $a(n)$ on $2n$ letters with longest ascending subsequence of length $n$, you need to sum over $\lambda\vdash 2n$ with $\lambda_1=n$; but these tableaux are just the tableaux with $\lambda\vdash n$ with an extra row of length $n$ inserted at the top, so $$a(n)=\sum_{\lambda\vdash n} \left(\frac{(2n)!}{H(\lambda)\prod_{1\le i\le n} (n+1-i+\lambda'_i)}\right)^2.\qquad (1)$$ Here, the denominator consists of the product of the hook sizes for cells in the first row of the expanded tableau, together with the product $H(\lambda)$ of the hook sizes for the remainder of the tableau, and I am setting $\lambda'_k:=0$ if there are fewer than $k$ columns in $\lambda$, or, equivalently, $k>\lambda_1$.

You can use the correspondence to compute the total number of permutations on $n$ letters: $$ n!=\sum_{\lambda\vdash n} \left(\frac{n!}{H(\lambda)}\right)^2 $$ so $$ \sum_{\lambda\vdash n}\frac{1}{H(\lambda)^2}=\frac{1}{n!}.\qquad\qquad (2) $$ Now split the sum (1) into piece A, where $\max(\lambda_1,\lambda'_1)<3\sqrt{n}$, and piece B, where $\max(\lambda_1, \lambda'_1)\ge3\sqrt{n}$. The number of permutations on $n$ letters with a longest ascending subsequence of length $k$ or more is no more than $$ \binom{n}{k}^2 (n-k)!, $$ since you can specify such a permutation by picking $k$ positions and letters for the first portion of the ascending subsequence and an ordering of the remaining $n-k$ letters which fill the other $n-k$ positions. Then $$ \frac{1}{n!} \binom{n}{k}^2 (n-k)! \le \frac{n^k}{k!^2} \le \left(\frac{ne^2}{k^2}\right)^k $$ but if $k=\lfloor 3\sqrt{n} \rfloor$, this vanishes as $n\to\infty$. It follows that $$ \sum_{\lambda\vdash n,\ \lambda_1\ge 3\sqrt{n}} \frac{1}{H(\lambda)^2}=o{\left(\frac 1 {n!}\right)}, $$ and since $H(\lambda)$ is not changed by reflecting the tableau so that rows and columns are interchanged, $$ \sum_{\lambda\vdash n,\ \max(\lambda_1,\lambda'_1)\ge 3\sqrt{n}} \frac{1}{H(\lambda)^2}=o{\left(\frac 1 {n!}\right)}, \qquad\qquad(3) $$ and piece B doesn't contribute much to (1). On the other hand, if $\lambda$ is in piece A, then \begin{eqnarray*} \prod_{1\le i\le n} (n+1-i+\lambda'_i) &=& n! \prod_{1\le i\le n} (1 + \frac{\lambda'_i}{n+1-i}) \\ &=& n! e^{\sum_i \lambda'_i/n} (1 + o(1)) \\ &=& n!\ e (1 + o(1)),\qquad\qquad (4) \end{eqnarray*} uniformly in $\lambda$. Combining (1), (2), (3) and (4) gives $$ a(n)= \left(\frac{1}{n!}+o\left(\frac{1}{n!}\right)\right) \left(\frac{(2n)!}{n!e}\right)^2(1+o(1)) +o\left(\frac{1}{n!} \left(\frac{(2n)!}{n!}\right)^2\right). $$ Dividing by $n!$, simplifying and using Stirling's approximation on the factorials, and multiplying back by $n!$ then gives $$ a(n)=\left(\frac{1}{\pi n} \frac{2^{4n}}{e^2} \cdot n!\right)\,(1+o(1)), $$ which is what you want.

1: "Longest Increasing and Decreasing Subsequences", C. Schensted, Canadian Journal of Mathematics, 13 (1961), pp. 179-191, DOI: https://doi.org/10.4153/CJM-1961-015-3