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.

-
There are no homomorphisms from $Z_n$ onto $S_n$ for any $n \geq 3$, since the former group is abelian and the latter group is not. Do you really intend for your homomorphisms to be surjective? If not, the problem becomes decidedly less trivial... –  Pete L. Clark Feb 16 '12 at 0:04
@PeteL.Clark: I agree with you. There are no surjective homomorphism from $Z_{n}$ onto $S_{n}$. So, I am trying to find homomorphisms that are not surjective, since they don't exist. –  spohreis Feb 16 '12 at 0:09
Cycles of order $n$ only give you some of the injective homomorphisms. In general you're trying to count the number of permutations of order dividing $n$, and such permutations may have cycles of any order dividing $n$. –  Qiaochu Yuan Feb 16 '12 at 0:11
But there is, for example, a map $\mathbf Z/6\mathbf Z \to S_6$ sending $1$ to $[12]$ (this factors through $\mathbf Z/2\mathbf Z$), and another sending $1$ to $[12][345]$ (this is injective). Are you counting these? –  Dylan Moreland Feb 16 '12 at 0:12
@QiaochuYuan: I know (I think I know) how many homomorphisms there are when $n$ is odd or $n=2$ –  spohreis Feb 16 '12 at 0:15

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$.

-
This is in the Online Encyclopedia of Integer Sequences at oeis.org/A074759. –  Gerry Myerson Feb 16 '12 at 3:28