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.

I came across the following question:If we pick a random permutation of $n$ distinct letters,what is the probability that our permutation has at most $k$ cycles?

I am not sure I understand the question.Can anyone please explain what these $k$-cycles are without group theory?

Thanks! Edit:It was given to me by a friend who in turn is attending the India IMO training camp.

share|improve this question
1  
It might help if you reference where you "came across" that term. Most authors would use $k$-cycle to mean a cycle (cyclic permutation) of length exactly $k$, not a permutation having at most $k$ cycles. You are perhaps aware that a permutation of $n$ distinct letters can be expressed as a product of disjoint cycles? –  hardmath May 2 '12 at 2:46
    
It was given to me by a friend who in turn is attending the India IMO training camp. –  Eisen May 2 '12 at 2:48

1 Answer 1

up vote 5 down vote accepted

Here's a randomish permutation of the numbers from 1 to 10: $$\matrix{3&8&5&1&9&10&2&7&4&6\cr1&2&3&4&5&6&7&8&9&10\cr}$$ We see that 1 goes to position 4, 4 goes to position 9, 9 goes to position 5, 5 goes to position 3, and 3 goes to position 1, completing a cycle: $1\to4\to9\to5\to3\to1$. Also, $2\to7\to8\to2$, and $6\to10\to6$. So, all told, this permutation has 3 cycles.

Now, you mention both "$k$ cycles" and "$k$-cycles", and these are different things. $1\to4\to9\to5\to3\to1$ is a 5-cycle, for instance, since there are 5 different things in it. So our permutation has 3 cycles, namely, a 5-cycle, a 3-cycle, and a 2-cycle.

share|improve this answer
1  
Thank you for the crystal-clear explanation.Time for me to solve the problem! –  Eisen May 2 '12 at 3:29

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.