Source: Mailed to me by
Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley)
Problem:
Given a permutation p of length n, let c(p) be the number of cycles in p. Suppose p is drawn uniformly from the set of all permutations. Show that
Expectation of 2 raised to the power of number of cycles is n+1, i.e E[2^c(p)]=(n+1)
Hint:
1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/
2) After you are done, you might want to read
this (*Spoiler Alert*)
Solution:
Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!