On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasi ng and strongly decreasing subsequences in words of length N from an alphab et of k letters. (In the limit as k --> infinity these become the correspon ding distributions for permutations on N letters.) We find Toeplitz determi nant representations for the exponential generating functions ton N) of the se distribution functions and show that they are expressible in terms of so lutions of Painleve V equations. We show further that in the weakly increas ing case the generating function gives the distribution of the smallest eig envalue in the k x k Laguerre random matrix ensemble and that the distribut ion itself has, after centering and normalizing, an N --> infinity limit wh ich is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k x k hermitian matrices of trace zero.