Closed formula for mean Suppose we have the i.i.d. random variables $X_{11}, X_{12},\ldots, X_{nn}$, such that each $X_{ij}$ has standard normal distribution $N(0,1)$, with mean $0$ and variance $1$. Given some integer $k>0$, is there some closed formula for the mean
$$E\Big(\sum_{i_1,i_2,\ldots,i_k=1}^nX_{i_1i_2}X_{i_2i_3}\ldots X_{i_{k-1}i_k}X_{i_ki_1}\Big)$$
?
I worked the cases for $k=1,2,3,4$, which gave, respectively, $0,n,0,8n^2+3n$. I'm not certain about the last one, but I know the mean is $0$ if $k$ is odd.
Just for clarification, this is the mean of the trace of $X^k$, where $X$ is a random matrix (it's a square matrix) with entries $X_{ij}$, i.e., 
$$X = \left[ \begin{array}{ccc}
X_{11} & \ldots & X_{1n}\\
\vdots & \ddots & \vdots\\
X_{n1} & \ldots & X_{nn}\\
\end{array} \right]. $$
Any insight will be helpful, thanks.
 A: Not a complete answer, but a suggested approach to the problem... It reduces the problem to counting certain partitions.
The approach I suggest is to go via Isserlis' Theorem, which gives an expression for the product of centred normal distributions as
\begin{align*}
\mathbf E[ X_1 \cdots X_{2n} ] = \sum \prod_{p=1}^{n} E[ X_{p_1} X_{p_2} ],
\end{align*}
where the sum runs over all partitions of $\{1,\ldots, 2n\}$ into pairs $(p_1,p_2)$: i.e.
\begin{align*} \bigcup_{p=1}^n \{p_1,p_2\} = \{1,\ldots, 2n\}.
\end{align*}
This result holds in general for correlated normal variables. Noteably in the independent case, the expectation $E[X_{p_1} X_{p_2}] = 0$ unless $X_{p_1} = X_{p_2}$, and further the product $\prod_{p=1}^{n} E[ X_{p_1} X_{p_2} ] = 0$ unless $X_{p_1} = X_{p_2}$ is true for all $p=1,\ldots, n$.
The problem is now purely combinatorial: given a multiset of variables $\{X_1,\ldots, X_{2n}\}$, how many ways are there to partition the multiset into pairs such that each pair consists of two copies of the same variable?
As I said, this is not a complete answer but it does leave you with a tractable approach so long as you're willing to do some counting!
