6
$\begingroup$

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.

  • 0
    @Qiaochu: oops: *mea culpa*. Indeed, to get an $n$-cycle in $S_n$, write down anything of the form $(1 a_2 a_3 \cdots a_n)$ with $a_i$ distinct elements of $\{2,\ldots,n\}$, so there are $(n-1)!$ such: soprheis is correct!2012-02-16

1 Answers 1

13

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

  • 2
    This is in the Online Encyclopedia of Integer Sequences at https://oeis.org/A074759.2012-02-16