Number of homomorphisms from $D_n$ to $S_n$

Calculate the number of homomorphisms from $D_n$ (dihedral group of order $2n$) to $S_n$ (symmetric group of order $n!$).

For example, I calculated for $D_3$ to $S_3$ and it came to $10$ and for $D_4$ to $S_4$ it came to $124$.

Solution 1:

We can use $\textsf{GAP}$ to find the first few terms in this sequence:

gap> for n in [1..8] do
         Print( Size(AllHomomorphisms(DihedralGroup(2*n),SymmetricGroup(n))), "\n" );
         od;
1
4
10
76
146
3616
5272
195280

This sequence doesn't appear in the OEIS. Note that the 76 disagrees with the OP's result of 124.

It's not hard to work out how many homomorphisms there from $D_p$ to $S_p$ when $p$ is prime. If $\varphi\colon D_p\to S_p$ is such a homomorphism, then $\varphi(r)$ must have order $1$ or $p$:

• If $\varphi(r)$ is the identity, then $\varphi(s)$ can be any self-inverse element of $S_p$.

• If $\varphi(r)$ has order $p$, it must be a $p$-cycle, of which there are $(p-1)!$ possible choices. Then $\varphi(s)$ must be an element of order two that conjugates this $p$-cycle to its inverse, of which there are exactly $p$ choices, for a total of $p(p-1)! = p!$ homomorphisms of this type.

So the total number of homomorphisms $D_p\to S_p$ is $$ a_p \,+\, p! $$ where $a_p$ is the number of $\sigma\in S_p$ for which $\sigma^2=1$. The sequence $a_n$ is entry A000085 in the OEIS, and doesn't seem to have a nice closed-form formula.

Incidentally, this formula agrees with the $\textsf{GAP}$ data above for $n=2,3,5,7$. It doesn't work when $n$ isn't prime since the order of $\varphi(r)$ can be any divisor of $n$, and because an element of order $n$ in $S_n$ need not be an $n$-cycle.

Solution 2:

Just like with linear maps and vector spaces, homomorphisms are determined by where they send the generating elements of the group. For the dihedral group, these generators are an element of order $n$ (call it $r$) and an element of order two (call it $s$). So the question is, what values can $\phi(r)$ and $\phi(s)$ take?

One thing that will help is that the order of $\phi(r)$ must divide the order of $r$ (since $r^k = 1$ implies $\phi(r)^k = \phi(r^k) = 1$), and so the answer will have something to do with the number of elements in $S_n$ whose order divides $n$.

Edit: As noted in the comment below, the two generators of $D_n$ have the additional relationship that $srs = r^{-1}$, and so their image must share the same relationship (ie $\phi(s)\phi(r)\phi(s) = \phi(r)^{-1}$. So once you've determined how many options there are for $\phi(r)$, you must calculate how many elements of order one or two satisfy this property as well in order to determine how many options there are for $\phi(s)$.