Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
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. –  xan May 8 '11 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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