How many are there with ?

Thanks in advance.

Printable View

- April 14th 2009, 04:17 PMBiscaimabout permutation
How many are there with ?

Thanks in advance. - April 14th 2009, 10:16 PMThePerfectHacker
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. - April 14th 2009, 11:11 PMNonCommAlg
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: