Let $X_N$ be the random variable corresponding to the number of fixed points (1-cycles) in a permutation chosen uniformly at random from $S_N$.
Then, the $m^{\text{th}}$ moment, when $m < N$, is equal to $B_m$ where $B_k$ is the $k^{\text{th}}$ Bell number (equal to the number of partitions of the set $[k]$).
This is a really interesting combinatorial fact, not least because all the moments are integers (moments past the $N^{\text{th}}$ are as well) and deserves a combinatorial solution.
Now, I have two proofs that are fairly combinatorial - however, both involve sums and avoid the combinatorial meaning of $X_{N}^m$, whatever that may be. I reproduce the first below:
Let $X_N$ be the number of fixed points in a random permutation on $N$ elements. It is well known that $E[X_N]=1$.
For $0\leq M \leq N$, $E\left[{X_N \choose M}\right]$ counts the expected number of sets of $M$ fixed points. We can count this using indicator random variables. Consider all subsets of $[N]$ containing $M$ elements.
The probability that a subset of size $M$ is pointwise fixed by a random permutation $\pi$ is $\frac{(N-M)!}{N!}$ because there are $(N-M)!$ permutations on the remaining elements that keep the subset of $M$ elemnts fixed (the number of automorphisms on $[N]-[M]$). This factor can also come from realizing that a permutation on $[N]$ induces an injection from a subset of $M$ elements to $[N]$ of which only $1$ sends each element to itself. Because the injections are uniformly chosen, we have a factor of $\frac{1}{N^{\underline{M}}} = \frac{(N-M)!}{N!}$.
Hence the expected value is ${N \choose M} \times \frac{(N-M)!}{N!} = \frac{1}{M!}$. Hence the expected value of $E[(X_N)^{\underline{M}}]$ is $1$.
Hence the expected value of $E[(X_N)^M]$ is $B_M$, the $M^{th}$ Bell Number for $0 \leq M \leq N$.
However, this involves at the end an ugly summation and (in my mind) fails to capture why the expectation ought to be an integer outside of coincidence.
It is also the case that as $N \rightarrow \infty$, $X_N \rightarrow \text{Poi}(1)$ where Poi($\lambda$) is the Poisson distribution with mean $\lambda$. Hence, it may be related to properties of the Poisson random distribution when the mean is $1$. I believe that the number of $k$-cycles is in generally asymptotically Poi($1/k$) but I don't remember where I read this and have not proven it myself - it would be interesting to see if they too had integer moments though I'd doubt it.
I'm really just looking for combinatorial intuition on this - a proof that doesn't involve summation or less intuitive things would be nice (summation in the context of a union is fine, but the random M! in the above summation leaves me unhappy). Thanks for your help!
The natural object for the $M$-th power of the number of fixed points isn't a subset of $M$ fixed points put an $M$-tuple of fixed points. Classify the $M$-tuples according to the subsets of entries that are equal. The number of these types is the Bell number $B_M$. A straightforward calculation shows that each such type contributes $1$ to the expected number of $M$-tuples of fixed points.