Increasing Subsequences and the Classical Groups

Abstract

We show that the moments of the trace of a random unitary matrix have combinatorial interpretations in terms of longest increasing subsequences of permutations. To be precise, we show that the $2n$-th moment of the trace of a random $k$-dimensional unitary matrix is equal to the number of permutations of length $n$ with no increasing subsequence of length greater than $k$. We then generalize this to other expectations over the unitary group, as well as expectations over the orthogonal and symplectic groups. In each case, the expectations count objects with restricted "increasing subsequence" length.