×

On the distributions of the lengths of the longest monotone subsequences in random words. (English) Zbl 0989.60012

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.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05A16 Asymptotic enumeration
PDFBibTeX XMLCite
Full Text: DOI arXiv