First this is true for so let us forget about this one.

Next, write where are disjoint cycles.

We have that the order of is the lowest common multiple of the lengths of each .

Therefore, we require for to be a product of disjoint 2-cycles.

The # of transpositions is:

The # of double disjoint transpositions is:

The # of triple disjoint transpositiong is: .

And so on ...

Add them up to get your answer.