Combinatorial constructions for integrals over normally distributed random matrices

Recent results of Hanlon, Stanley, and Stembridge give the expected values of certain functions of matrices of normal variables in the real and complex cases. They point out that in both cases the results are equivalent to combinatorial results and suggest further that these results may have purely combinatorial proofs, in this way avoiding the use of the theory of spherical functions. Such proofs are given in this paper. In the complex case we use the familiar cycle decomposition for permutations. In the real case we introduce an analogous decomposition into cyclically ordered sequences, called chains, which makes the real and complex cases strikingly similar.