Ponder This Challenge - December 2006 - Cycles size in random permutation

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Roberto Tauraso (12.01.2006 @03:06:36 PM EST)
• V. Balakrishnan (12.01.2006 @05:24:13 PM EST)
• Charles Reilly (12.01.2006 @05:56:50 PM EST)
• Dave Blackston (12.01.2006 @07:31:26 PM EST)
• Alan Murray (12.02.2006 @01:26:52 AM EST)
• Dan Dima (12.02.2006 @08:02:48 AM EST)
• Firat Solgun (12.02.2006 @08:57:01 AM EST)
• Frank Yang (12.02.2006 @12:02:36 PM EST)
• Amghibech Said (12.02.2006 @01:24:24 PM EST)
• John T. Robinson (12.02.2006 @02:59:02 PM EST)
• Rich Kaye (12.02.2006 @03:54:58 PM EST)
• Yoav Raz (12.02.2006 @06:44:20 PM EST)
• Miroslava Sotakova (12.03.2006 @02:49:36 AM EST)
• Oded Margalit (12.03.2006 @10:04:41 AM EST)
• John G. Fletcher (12.03.2006 @07:36:40 PM EST)
• Eddie Marcus (12.03.2006 @10:56:21 PM EST)
• Arjun Archarya (12.03.2006 @11:29:20 PM EST)
• Eugene Vasilchenko (12.04.2006 @09:42:28 AM EST)
• Wolfgang Kais (12.04.2006 @11:52:04 AM EST)
• Frank Mullin (12.04.2006 @01:42:34 PM EST)
• Christian Blatter (12.04.2006 @02:18:08 PM EST)
• Jack Kennedy (12.04.2006 @02:38:59 PM EST)
• David Friedman (12.04.2006 @05:00:11 PM EST)
• Tom Gutman (12.04.2006 @06:44:17 PM EST)
• Zhou Guang (12.06.2006 @04:14:26 AM EST)
• arnab.x.bose (12.07.2006 @03:32:52 AM EST)
• Jiri Hrdina (12.07.2006 @07:58:35 AM EST)
• Fang Yu (12.07.2006 @01:19:35 PM EST)
• Phil Muhm (12.07.2006 @01:20:11 PM EST)
• Riyaaz Shaik (12.08.2006 @07:22:54 AM EST)
• John Tromp (12.08.2006 @05:18:13 PM EST)
• Ashish Srivastava (12.08.2006 @08:10:39 PM EST)
• dineshk (12.09.2006 @12:08:31 PM EST)
• Michael Quist (12.09.2006 @10:37:36 PM EST)
• Justin T. Miller (12.11.2006 @12:47:14 PM EST)
• Matthew Samuel (12.11.2006 @11:07:04 PM EST)
• Lawrence Hon (12.11.2006 @11:54:44 PM EST)
• David McQuillan (12.12.2006 @01:15:23 PM EST)
• Ed Shepard (12.12.2006 @03:54:34 PM EST)
• Rajeev Rao (12.12.2006 @07:27:26 PM EST)
• Du Yang (12.13.2006 @06:12:59 PM EST)
• Yurun Liu (12.13.2006 @10:33:19 PM EST)
• Ashutosh Mahajan (12.14.2006 @07:56:23 AM EST)
• Bryan Bell (12.17.2006 @06:43:23 PM EST)
• John Durham (12.19.2006 @09:18:10 PM EST)
• Viral Gupta (12.22.2006 @02:33:22 AM EST)
• Jakub Łopuszański (12.25.2006 @02:17:29 PM EST)
• Arthur Breitman (12.26.2006 @01:13:08 PM EST)
• Ray Gregory (12.27.2006 @04:26:56 PM EST)
• Dharmadeep Muppalla (12.28.2006 @07:33:07 AM EST)
• Se Kwon Kim (12.28.2006 @10:16:21 AM EST)
• Chris Messer (12.31.2006 @08:48:26 PM EST)