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 .
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