Tracy, Craig A.; Widom, Harold On the distributions of the lengths of the longest monotone subsequences in random words. (English) Zbl 0989.60012 Probab. Theory Relat. Fields 119, No. 3, 350-380 (2001). Summary: We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length \(N\) from an alphabet of \(k\) letters. (In the limit as \(k\to\infty\) these become the corresponding distributions for permutations on \(N\) letters.) We find Toeplitz determinant representations for the exponential generating functions (on \(N\)) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating function gives the distribution of the smallest eigenvalue in the \(k\times k\) Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an \(N\to\infty\) limit which is equal to the distribution function for the largest eigenvalue in the Gaussian unitary ensemble of \(k\times k\) Hermitian matrices of trace zero. Cited in 1 ReviewCited in 32 Documents MSC: 60C05 Combinatorial probability 60F05 Central limit and other weak theorems 05A16 Asymptotic enumeration Keywords:Toeplitz determinant representations; exponential generating functions; solutions of Painlevé V equations; Laguerre random matrix ensemble PDFBibTeX XMLCite \textit{C. A. Tracy} and \textit{H. Widom}, Probab. Theory Relat. Fields 119, No. 3, 350--380 (2001; Zbl 0989.60012) Full Text: DOI arXiv