3
$\begingroup$

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.

  • 0
    It was given to me by a friend who in turn is attending the India IMO training camp.2012-05-02

1 Answers 1

9

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.

  • 1
    Thank you for the crystal-clear explanation.Time for me to solve the problem!2012-05-02