I saw Scott’s talk today on some complexity results related to his and Alex Arkhpov’s work on linear optics. I missed the main seminar but I saw the theory talk, which was on how hard it is to approximate the permanent of a matrix $X$ whose entries $(X_{ij})$ are drawn iid complex circularly-symmetric Gaussian $\mathcal{CN}(0,1)$. In the course of computing the expected value of the 4th moment of the permanent, he gave the following cute result as a puzzle. Given a permutation $\sigma$ of length $n$, let $c(\sigma)$ be the number of cycles in $\sigma$. Suppose $\sigma$ is drawn uniformly from the set of all permutations. Show that
$\mathbb{E}[ 2^{c(\sigma)}] = n + 1$.