How many homomorphisms are there from $\mathbb{Z}_{n}$ into $S_{n}$? I would like to know how many homomorphisms there are from $\mathbb{Z}_{n}$ into $S_{n}$?
If $n=2$ or $n$ is odd, I think that there are $(n-1)!+1$. I am counting those cycles of order $n$, when $n$ is odd and adding to them the trivial homomorphism. Am I right? In the general case I've failed.
I would appreciate any help here.
 A: We might as well ask the more general question: how many homomorphisms are there from $\mathbb{Z}/n\mathbb{Z}$ to $S_m$? This is precisely the number of permutations of order dividing $n$ in $S_m$, which we can compute as follows. First, recall that if $G$ is a finite group acting on a finite set $X$, then the cycle index polynomial $Z_G$ is given by
$$Z_G(z_1, z_2, ...) = \frac{1}{|G|} \sum_{g \in G} z_1^{c_1(g)} ...$$
where $c_i(g)$ is the number of cycles of the permutation $g$ acting on $X$. 
Theorem (Exponential formula): The cycle index polynomials of the symmetric groups $S_m$ acting on the sets $\{ 1, 2, ... m \}$ in the usual way are given by
$$\sum_{m \ge 0} Z_{S_m}(z_1, z_2, ...) t^m = \exp \left( \sum_{i \ge 1} z_i \frac{t^i}{i} \right).$$
I am sure this result is well-known to combinatorialists but I don't actually know where to find a published proof; you can find a proof in this blog post. 
Now, I claim that a permutation has order dividing $n$ precisely when each cycle in its cycle decomposition has order dividing $n$. This is not difficult to see. Given that result, the sequence we want (for fixed $n$) can be obtained by setting $z_i = 0$ if $i$ doesn't divide $n$ and $z_i = 1$ otherwise. Thus the relevant generating function for the number of permutations of order dividing $n$ in $S_m$ is given by
$$\exp \left( \sum_{i | n} \frac{t^i}{i} \right).$$
For example, if $n = m = 6$ then we want the coefficient of $\frac{t^6}{6!}$ in
$$\exp \left( t + \frac{t^2}{2} + \frac{t^3}{3} + \frac{t^6}{6} \right)$$
which any computer algebra system (such as WolframAlpha!) will tell you is $396$. For a larger example, if $n = m = 12$ then we want the coefficient of $\frac{t^{12}}{12!}$ in
$$\exp \left( t + \frac{t^2}{2} + \frac{t^3}{3} + \frac{t^4}{4} + \frac{t^6}{6} + \frac{t^{12}}{12} \right)$$
which is $133494912$. 
