An Asymptotic Version of a Theorem of Knuth

2009/06/28 by Jonathan Novak, Novak, Jonathan
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.0906.5167

openalex publication_date 2009/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let S(d,N) denote the number of permutations in the symmetric group on [N] which have no decreasing subsequence of length d+1. We prove that S(d,dn) is asymptotically equal to the number of standard Young tableaux of rectangular shape R(d,2n) in the limit n → ∞, with d fixed.

Related

• Recent results on permutations without short cycles
• Asymptotics for skew standard Young tableaux via bounds for characters
• On the Enumeration of Skew Young Tableaux
• Asymptotics of the number of standard Young tableaux of skew shape
• Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings