Permutation and cycles

Let \([n]\) be the set \(\{1,2,...,n\}\) (we call each element a vertex) and a permutation of \([n]\) be \(\pi=[\pi(1),\pi(2),\cdots,\pi(n)]\), i.e., denote \(\pi(x)=y\) the fact that in a permutation, position \(x\) has vertex \(y\). There are \(n!\) possible permutations of \([n]\).

For example, permutation of 1,2,3,4 into 3,2,4,1 has a 1-cycle of 2, i.e. \(\pi(2) = 2\), and a 3-cycle, \(\pi(1) = 3, \pi(3) = 4, \pi(4) = 1\).

A cycle is such that we have a sequence of \(\pi(j) = k, \pi(k) = \ell, \cdots, \pi(p) = q, \pi(q) = j\).

expected number of cycles

Assume all permutation is of equal probability. The expected number of cycles in permutation of \([n]\) be \(h(n)\). Then obviously \(h(1) = 1\) because there is only one permuatation. \(h(2) = 1.5\) for the only permuatation are 1,2 and 2,1 which has 2 and 1 cycles respectively.

\(h(n) = \sum_{i=1}^n \frac{1}{n}\). Proof as follows. (adapted from ref #1)

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

And by induction, \(h(n) = \sum_{i=1}^n \frac{1}{i}\)

Indeed, we can understand it as \(h(n) = \sum_{k=1}^n h_i(n)\) where \(h_k(n) = \frac{1}{k}\) is the expected number of \(k\)-cycles in the permutation.

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

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

1-cycle: This means \(\pi(k)=k\), so for any particular \(k\), the probability is \(1/n\). 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, \(\pi(v)=v\) for all \(v\), which is \(1/n!\).

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

If vertex \(v_1\) is in a \(k\)-cycle, it means \(\pi(v_1)=v_2, \pi(v_2)=v_3, \cdots, \pi(v_{k-1})=v_k, \pi(v_k)=v_1\). By counting, we have \((n-1)(n-2)\cdots(n-k+1) \times (n-k)! = (n-1)!/(n-k)! \times (n-k)! = (n-1)!\) ways to make a \(k\)-cycle with \(v_1\) in it in a permutation. The term after \(\times\) refers to the permutation of remaining \(n-k\) vertices not in the cycle. Therefore, given \(v_1\), the probability is \((n-1)!/n! = 1/n\).

Alternatively, we can derive the probability by multiplying the probability of correct \(\pi(v_i)\) in each step (adapted from ref #2): For \(\pi(v_1)\), it can be anything but \(v_1\), which has the probability of \(\frac{n-1}{n}\). For \(\pi(v_2)\), it cant be anything but \(v_1,v_2\) but due to the bijective nature of \(\pi(\cdot)\) function, \(\pi(v_2)=v_2\) has been ruled out by the fact that \(\pi(v_1)=v_2\). Therefore the probability is \(\frac{n-2}{n-1}\). Similarly, for \(\pi(v_i)\) up to \(i = k-1\), the probability is \(\frac{n-i+1}{n-i+2}\). Finally \(\pi(v_k)=v_1\) has probability of \(\frac{1}{n-k+1}\). So the overall probability is

probability of a large cycle

There are \(\binom{n}{k}\) ways to pick \(k\) vertices from \([n]\) and each set of \(k\) picked symbols has \((k-1)!\) ways to make a cycle (and the remaining \(n-k\) vertices has \((n-k)!\) possible permutations). For \(2k > n\), the probability is:

This is also the probability that a permutation has at least one \(k\)-cycle for \(k \le n\).

expected number of k-cycle

In a permutation, there is probability \(1/n\) that any vertex is in a \(k\)-cycle. If we check each of the \(n\) vertices whether it is in a \(k\)-cycle, the expected number of affirmative vertices is \(n\times (1/n) = 1\). Since if there is a \(k\)-cycle, there must be \(k\) vertices affirmative to such test, we have the expected number of \(k\)-cycle as \(1/k\).

average length of cycle

A permutation always has \(\pi(v_i) = v_j\) for each \(v_i\). If we consider that as a graph, there is always \(n\) edges. Since we know that the expected number of cycle in a permutation is \(\sum_i \frac{1}{i}\), the average cycle length (i.e., counting number of edges, or equivalently the number of vertices), is \(n/\sum_i\frac{1}{i} \approx n/\ln n\).

Additional properties

From ref #4:

• Probability of having \(j_k\) number of \(k\)-cycle, for \(k=1,\cdots,n\), in the permutation is \(\prod_{k=1}^n \frac{1}{k^{j_k} j_k!}\)
• As \(n\to\infty\), the distribution of number of \(k\)-cycle in permutation converges to Poisson with intensity \(1/k\)

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