Number of permutations with a given partition of cycle sizes

Question

Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a particular partition of cycle sizes.

For example, how many permutations of 1..10 have a 5 cycle, a 3 cycle and two 1 cycles? Or what is Count(5, 3, 1, 1)?

To clarify, I can figure the easy cases.

• Count(1, 1, ..., 1) = 1
• Count(n) = n!/n
• Count(n - 1, 1) = n!/(n-1) (I think assuming n-1 > n/2)

How do I count permutations for the general case?

(The contest is over, but I'd like to fill in this piece to see if the rest of my logic was correct.)

Answer 1

I believe this is relatively simple. If you are trying to find a permutation of $n$ elements with $a_k$ cycles of size $k$, then the number is:

$$\frac{n!}{\prod { {a_k}! k^{a_k}}}$$

So, in the case of $(5,3,1,1)$, that gives $a_5=1$, $a_3=1$, $a_1=2$, and all other $a_k=0.$

That gives a denominator of $1! 5^1 1! 3^1 2! 1^2 = 30$, and acount of $10!/30 = 120960$.

This is a relatively easy counting argument. Take one of the $n!$ permutations of $\{1,...,n\}$. List the permutation and break it up into blocks of the appropriate size in a fixed order (say, sorted.) So if you started with the permutation of size 10: $$(9,1,3,5,6,2,7,8,10,4)$$

Break it up into cycles of the required size, yielding an output permutation:

$$(9\,1\,3\,5\,6)(2\,7\,8)(10)(4)$$ Then count how many times each permutation comes up out of this process, which is the denominator of the formula above.