Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
2  
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
1  
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

1 Answer 1

up vote 12 down vote accepted

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

share|improve this answer
2  
This is in the Online Encyclopedia of Integer Sequences at oeis.org/A074759. –  Gerry Myerson Feb 16 '12 at 3:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.