Let be the set (we call each element a vertex) and a permutation of be , i.e., denote the fact that in a permutation, position has vertex . There are possible permutations of .

For example, permutation of 1,2,3,4 into 3,2,4,1 has a 1-cycle of 2, i.e. , and a 3-cycle, .

A cycle is such that we have a sequence of .

expected number of cycles

Assume all permutation is of equal probability. The expected number of cycles in permutation of be . Then obviously because there is only one permuatation. for the only permuatation are 1,2 and 2,1 which has 2 and 1 cycles respectively.

. Proof as follows. (adapted from ref #1)

Assume we have a permutation of , , we have ways to generate a permutation of from it: insert before any or insert after . Result of such is either we make into one of the existing cycle (first ways) or we make into a 1-cycle (last way). Therefore we have:

And by induction,

Indeed, we can understand it as where is the expected number of -cycles in the permutation.

probability of having a n-cycle/1-cycle in a permutation of [n]

-cylce: By counting: can be anything but 1, can be anything but 1 or , and so on. Therefore we have such permutations. Alternatively, there are ways of arranging symbols in a cycle. Since there are possible permutations, the probability of having -cycle is .

1-cycle: This means , so for any particular , the probability is . But note that, this is the probability of any particular vertex in a 1-cycle, which is different from the probability of a random permutation has any 1-cycle.

The probability that the permutation has only 1-cycle is the probability that the permutation is an identity mapping, for all , which is .

probability of a vertex in a k-cycle in a permutation of [n]

If vertex is in a -cycle, it means . By counting, we have ways to make a -cycle with in it in a permutation. The term after refers to the permutation of remaining vertices not in the cycle. Therefore, given , the probability is .

Alternatively, we can derive the probability by multiplying the probability of correct in each step (adapted from ref #2): For , it can be anything but , which has the probability of . For , it cant be anything but but due to the bijective nature of function, has been ruled out by the fact that . Therefore the probability is . Similarly, for up to , the probability is . Finally has probability of . So the overall probability is

probability of a large cycle

There are ways to pick vertices from and each set of picked symbols has ways to make a cycle (and the remaining vertices has possible permutations). For , the probability is:

This is also the probability that a permutation has at least one -cycle for .

expected number of k-cycle

In a permutation, there is probability that any vertex is in a -cycle. If we check each of the vertices whether it is in a -cycle, the expected number of affirmative vertices is . Since if there is a -cycle, there must be vertices affirmative to such test, we have the expected number of -cycle as .

average length of cycle

A permutation always has for each . If we consider that as a graph, there is always edges. Since we know that the expected number of cycle in a permutation is , the average cycle length (i.e., counting number of edges, or equivalently the number of vertices), is .

Additional properties

From ref #4:

  • Probability of having number of -cycle, for , in the permutation is
  • As , the distribution of number of -cycle in permutation converges to Poisson with intensity

Referneces

  1. Math Stackexchange, Name Drawing Puzzle, 2012-07-01
  2. http://www.inference.org.uk/itila/cycles.pdf
  3. Kent E. Morrison, “Random Maps and Permutations”, 1998-04-14
  4. Terence Tao, “The number of cycles in a random permutation”, 2011-11-23