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.)
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.