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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – xan May 8 '11 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.