Cycles and Permutations
Source: Iran PPCE 2008
December 29, 2008
probabilityfactorialexpected valueprobability and stats
Problem Statement
A permutation is selected randomly through all -permutations.
a) if C_a(\pi)\equal{}\mbox{the number of cycles of length }a\mbox{ in }\pi then prove that E(C_a(\pi))\equal{}\frac1a
b) Prove that if the probability that does not have any cycle with lengths is at most \frac1{\sum_{i\equal{}1}^ka_i}