December 2006
<<November December January>>
Answer:
This problem can be solved by counting the permutations, P, with maximum cycle size greater than x*n. Since x > .5 there is at most one such large cycle, C. Let C have size k. There are B(n,k). (B(n,k) denotes the binomial coefficient n choose k) ways of picking the elements in C, (k-1)! ways of permuting them cyclically and (n-k)! ways of permuting the remaining (n-k) elements. Since B(n,k) = n!/(k!*(n-k)!), it follows that there are n!/k permutations on n elements with maximum cycle k (when k > n/2). Since there are n! permutations total, this means the probability of obtaining such a permutation is 1/k. So f(x,n) = 1 - Sum(k>x*n)(1/k). As n --> infinity the sum can be approximated by the Integral(x*n to n)(1/x) = log(z)(x*n to n) = log(n)-log(x*n) = -log(x). Since f(x,n) is defined
as the probability that there is no large cycle we subtract from 1 obtaining the answer 1+log(x).
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com