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.


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$.

  • $\begingroup$ Thanks! These references are helpful. I didn't know about the determinantal expression. I'll check the paper more carefully, but I guess you're saying the trivial upper bound of $\leq$min$\{k!,n^{2k}\}$ (with $\leq n^{2k}$ from the unitary integral expression) is asymptotically tight in $k$ for fixed $n$. $\endgroup$ – 4xion Jun 21 '20 at 17:21
  • $\begingroup$ Sorry the notation is unfortunate, talking about $k$-th moments of unitaries in $U(n)$ gives the reverse of the convention in the combinatorics literature. $\endgroup$ – 4xion Jun 21 '20 at 17:24

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.

  • $\begingroup$ The hook-product theorem is for fixed shapes under RSK. One has to sum over all relevant shapes, which is how Regev did the asymptotics. $\endgroup$ – Richard Stanley Jun 21 '20 at 0:23
  • $\begingroup$ Sure. At the scale of large deviations, this is also what Logan-Shepp did.This gives a variational formula for the rate function. $\endgroup$ – ofer zeitouni Jun 21 '20 at 12:22
  • $\begingroup$ This explicit formula is the sum over integer partitions given above, i.e. counting Young tableaux and summing over all relevant shapes, as was mentioned. And thanks for the references. I'm interested in upper bounds for a fixed $n$ at all $k$, so I care about both regimes. But the large $k$ asymptotics are helpful. $\endgroup$ – 4xion Jun 21 '20 at 17:47
  • $\begingroup$ If $n>2\sqrt{k}+\Omega(k^{1/6})$, I believe the number is asymptotic to $k!$, so what improvement would you be after in that regime? $\endgroup$ – ofer zeitouni Jun 22 '20 at 13:06

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.

  • $\begingroup$ It should be said that $12...(n+1)$ is very different from an arbitrary pattern: I believe this is the only infinite family of patterns with a something like a "formula" (+ precise asymptotics) known (the aforementioned Gessel's formula) $\endgroup$ – Sam Hopkins Jun 20 '20 at 16:55
  • $\begingroup$ The funny thing is Gessel's formula for the Haar integral, using a determinant of Bessel functions was known to mathematical physicists, in particular Bars and collaborators. $\endgroup$ – Abdelmalek Abdesselam Jun 20 '20 at 17:10
  • $\begingroup$ Thanks for the response and suggestions! And yes, I should have mentioned that the trivial upper bound is min$\{k!,n^{2k}\}$. Interesting that your suggestion essentially gives a similar behavior. $\endgroup$ – 4xion Jun 21 '20 at 17:48
  • $\begingroup$ The paper by Bars and Green which already contains the Haar integral analogue of Gessel's formula is journals.aps.org/prd/abstract/10.1103/PhysRevD.20.3311 see the appendix. $\endgroup$ – Abdelmalek Abdesselam Jun 21 '20 at 23:04
  • $\begingroup$ @4xion: It seems $n^{2k}$ is indeed the best one can do. Is that bound good enough for your goals? $\endgroup$ – Abdelmalek Abdesselam Jun 21 '20 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.