An asymptotic version of a theorem of Knuth

作者：Novak Jonathan^*

来源：Advances in Applied Mathematics, 2011, 47(1): 49-56.

DOI：10.1016/j.aam.2010.04.001

• Permutations
• Pattern avoidance
• Young tableaux
• Asymptotics

A well-known theorem of Knuth establishes a bijection between permutations in e(N) with no decreasing subsequence of length three and rectangular standard Young tableaux of shape R(2. N). We prove an asymptotic version of this result: for any fixed integer d >= 2, the number of permutations in e(dn) with no decreasing subsequence of length d + 1 is asymptotically equal, as n -> infinity, to the number of standard Young tableaux on the rectangle R(d, 2n). This yields a new proof of Regev's theorem on the asymptotic number of permutations without long decreasing subsequences, and consequently an alternative, elementary evaluation of Mehta's integral at beta = 2.

• 出版日期2011-7