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