Number of permutations with longest increasing subsequences of length at most $n$

Question

Is there a known expression for, or a nontrivial upper bound on, the number of permutations in $S_k$ with longest increasing subsequence of length at most $n$?

Let $l(\sigma)$ denote the length of the longest increasing subsequence of a permutation $\sigma\in S_k$. It seems like a lot is known about $l(\sigma)$ for a random permutation (and its asymptotic scaling), but are there upper bounds on the number of permutations in $\sigma\in S_k$ with $l(\sigma)\leq n$.

Motivation/context for this question: the moments of traces of random unitaries. It is known that $\int dU |{\rm tr}(U)|^{2k} = k!$ for $k\leq n$, where we integrate over the unitary group $U(n)$ with respect to the Haar measure. More generally, for any $k$ and $n$ one may write the expression as [1] $$ \int dU |{\rm tr}(U)|^{2k} = \sum_{\lambda \vdash k,~\ell(\lambda)\leq n} \chi_\lambda(\mathbb{I})^2\,, $$ summing over integer partitions $\lambda$ of $k$ with length at most $n$, and where $\chi_\lambda(\mathbb{I})$ is the identity character with respect to $\lambda$. The RHS is then counting the number of pairs of Young tableaux with width $\leq n$, which is equivalent to counting the number of permutations in $S_k$ with no increasing subsequences longer than $n$. I'm essentially interested in upper bounds on this quantity which are tighter than the trivial bound of $k!$.

[1] E. Rains, "Increasing Subsequences and the Classical Groups," Electron. J. Comb. 5 (1998) R12. http://eudml.org/doc/119270.

Answer 1

There is an explicit determinental formula for these numbers due to Gessel in Symmetric functions and P-recursiveness (JCTA, 1990). Asymptotics were known much earlier and appear in a paper by Amitai Regev Asymptotic values for degrees associated with strips of young diagrams (Adv. Math. 1981). The gross asymptotics are that the $k$th root of the number of such permutations approaches $n^2$. Note that in most of the literature, $k$ and $n$ will play the opposite roles, i.e., the question will be about enumeration of permutations in $S_n$ with no increasing subsequence of size greater than $k$.

Answer 2

An explicit formula is the hook-product formula, due to Schensted I believe. This formula is used in the classical work of Logan and Shepp, as well as in Vershik-Kerov. See for example equation (1.1) in the Logan-Shepp paper

Asymptotics will depend greatly on whether $n>2\sqrt{k}$ or not. I assume you meant $n<2\sqrt{k}$. In that case, the asymptotics (under the name of Large deviations principle) are known, and involve the Logan-Shepp functional. See Increasing subsequences of iid samples and Large deviations for increasing sequences in the plane. There is also work in the moderate deviations regime due to Lowe.

Answer 3

This relates to the Stanley-Wilf Conjecture (now a theorem). More generally you can consider $S_k(\sigma)$ the number of permutations of $k$ elements which do not contain the pattern given by the permutation $\sigma$. Here you are looking at the particular case $S_k(12\cdots(n+1))=:u_n(k)$. Exhaustive references on the subject are the books "Combinatorics of Permutations" by Bóna and "Patterns in Permutations and Words" by Kitaev. Theorem 4.10 in Bóna's book gives a very elementary combinatorial proof for the bound $$ u_n(k)\le n^{2k}\ . $$ A similar bound was conjectured by Arratia for any pattern $\sigma$ of length $n+1$ but this is known to fail for $\sigma=1324$.

Note that the bound is trivial from the Haar integral formula because $U$ has eigenvalues of modulus one and so $|{\rm tr} (U)|\le n$. Also, the numbers form a supermultiplicative sequence by a result of Arratia (same article as above). The supermultiplicative property also follows from the Haar integral: the $S_k(12\cdots(n+1))$ sequence in $k$ being a Stieltjes moment sequence is log-convex.

I first thought that this fact (Feteke's Subadditive Lemma) combined with Regev's asymptotic formula might give a better exponential upper bound (rather than asymptotic). However one ends up with the same upper bound. That's because Regev's formula gives, after computing a Selberg integral, $$ u_n(k)\sim 1!2!\cdots(n-1)!\ (2\pi)^{-\frac{n-1}{2}} \ 2^{-\frac{n^2-1}{2}}\ n^{\frac{n^2}{2}}\ \frac{n^{2k}}{k^{\frac{n^2-1}{2}}} $$ when $k\rightarrow\infty$ (I took the formula from Stanley's ICM survey). So the correct exponential growth of $n^{2k}$ is already in the trivial bound.