Probability 1 & 2
Probability
Level
3
What is the probability that a permutation of the first n positive integers has the numbers 1 and 2 within the same cycle. ( Note : It's a problem taken from a book by sir Andreescu)
The answer is 0.5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The total number of permutations is of course n!. We will count instead the number of permutations for which 1 and 2 lie in different cycles. If the cycle that contains 1 has length k, we can choose the other k − 1 elements in {(n-2) \choose(k-1)}. ways from the set {3, 4,...,n}. There exist (k − 1)! circular permutations of these elements, and (n − k)! permutations of the remaining (n - k) elements. Hence the total number of permutations for which 1 and 2 belong to different cycles is equal to
\displaystyle\sum_{ k=1}^(n-1) {(n-2) \choose(k-1)} (k-1)! (n-k)! = n!/2
It follows that exactly half of all permutations contain 1 and 2 in different cycles, and so half contain 1 and 2 in the same cycle. The probability is 1/2