5
$\begingroup$

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

1 Answers 1

8

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.

  • 1
    Brilliant -- that did the trick. I think I understand it now. Treat every permutation as the kind we want and then divide out the duplicate representations. Each cycle can be arranged _k_ ways, and there are _ak_ of those, which can be arranged _ak!_ ways.2011-05-08