IBM Ponder This #104 · December 2006

Puzzle for December 2006.

Consider a random permutation, P, on n elements. P can be decomposed into cycles. Let x be a fraction between .5 and 1. Let f(x,n) be the probability that all the cycles of P have size less than x*n. This month's problem is to find the asymptotic behavior of f(x,n) for fixed x as n --> infinity.

Solution

Best opened after a real attempt

To be added.