Find the number of homomorphisms from $Z_m$ to $S_n$

Question

The kernel of the homomorphism will be a normal subgroup and the normal subgroups of $Z_m$ are of the form $\langle\frac{m}{d}\rangle$ where $d|m$.I can find out for particular cases but how do I generalize this? Any suggestion would be really helpful.

Answer 1

As Thorgott says, this is the number of permutations in $S_n$ of order dividing $m$. Equivalently this is the number of permutations whose cycles have length dividing $m$. There isn't a particularly simple closed form for these, but if we let $a_m(n)$ denote the number of such permutations then there is an exponential generating function

$$\sum_{n \ge 0} \frac{a_m(n)}{n!} t^n = \exp \left( \sum_{k \mid m} \frac{t^k}{k} \right).$$

This follows from a general result that I think is called the "exponential formula in permutation form" and unfortunately I don't know a really elementary discussion of it but see, for example, this blog post or (more advanced) this blog post or the first few chapters of Flajolet and Sedgewick's Analytic Combinatorics about techniques for writing down generating functions.

For example, when $m = 2$ we get

$$\sum_{n \ge 0} \frac{a_2(n)}{n!} t^n = \exp \left( t + \frac{t^2}{2} \right)$$

which gives the generating function of the involution numbers, counting the number of involutions (permutations of order dividing $2$) in $S_n$. Already this simple case doesn't have a nice closed form but this generating function allows at least a precise description of the asymptotics.

Were you really given this problem as homework? It would make more sense to me if $m$ and $n$ were fixed small integers in your homework. Then you can just do casework on the possible cycle decompositions.