How many are there with ?
Thanks in advance.
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.
there's a combinatorial way of looking at this problem: let and now let and if then there are possibilities for
if then we must have because so there will be possibilities for in this case. thus we have this recurrence relation:
with initial conditions there are only non-closed form expressions for and one of them was given by ThePerfectHacker:
for more insight about the mysterious sequence see here.
Edit: simplifying ThePerfectHacker's formula gives you this better looking one: