Permutations: Cycle Structure and Derangements

Section 2.6 Permutations: Cycle Structure and Derangements

When we write permutations in one-line notation, some feature of the permutation are brought to the surface. However, other features are obscured. Thus, it is useful to have multiple representations of a permutation. Our next representation is called cycle notation.

🔗

Definition 2.6.1.

A cycle in a permutation \(\pi\in \ss_n\) is a sequence of elements \((x_1,x_2,\ldots,x_k)\) with each \(x_i\in [n]\) satisfying

\begin{equation*} \pi(x_i)=x_{i+1} \end{equation*}

for all \(m\) and \(\pi(x_k)=x_1\text{.}\) The length of the cycle is the number of elements in the cycle.

🔗

Example 2.6.2.

In the permutation \(37416528\text{,}\) we have the cycle \((1,3,4)\) of length three and the cycle \((8)\) of length 1.

🔗

Figure 2.6.3. A diagram of the cycle \((1,3,4)\text{.}\)
🔗

🔗

Checkpoint 2.6.4.

Find all the cycles contained in \(\pi=375916824\text{.}\) Write them in both cycle notation and in diagram form.

🔗

Definition 2.6.5.

Let \(\pi\in\ss_n\text{.}\) We construct the standard cycle representation of a permutation \(\pi\in\ss_n\) as follows. First, create the cycle \(C_1\) containing \(n\text{,}\) with \(n\) listed first in \(C_1\text{.}\) Second, create the cycle \(C_2\) containing the largest value not in \(C_1\text{,}\) where the largest value is listed first. Third, create the cycle \(C_3\) containing the largest value not in \(C_1\) or \(C_2\text{,}\) where the largest value is listed first. Continue in this fashion until all of the elements of \([n]\) are in a cycle, resulting in cycles \(C_1,C_2,\ldots,C_k\text{,}\) and then write

\begin{equation*} \pi=C_kC_{k-1}\cdots C_2C_1 \, . \end{equation*}

This is the standard cycle representation.

🔗

Checkpoint 2.6.6.

Write \(\pi=375916824\) in standard cycle representation. Draw the diagrams for all the cycles in \(\pi\text{.}\)

🔗

There are some special permutations that we will need names for:

The identity permutation is the permutation \(1234\cdots n\text{.}\)
🔗

🔗
An \(n\)-cycle is a permutation consisting of only one cycle of length \(n\text{.}\)
🔗

🔗
A cycle of length one in a permutation corresponds to a fixed point, since the cycle \((i)\) in \(\pi\) indicates that \(\pi_i=i\text{.}\)
🔗

🔗
A permutation with a single cycle of length two, and all other cycles of length one, is called a transposition because it exchanges, i.e., transposes, two values in \([n]\text{.}\)
🔗

🔗
A permutation is a derangement if it has no fixed points, i.e., if it has no one-cycles.
🔗

🔗

🔗

Checkpoint 2.6.7.

Create two examples for each of the definitions above.

🔗

Theorem 2.6.8.

There are \((n-1)!\) cycles of length \(n\) in \(\ss_n\text{.}\)

🔗

Proof.

Suppose \(\pi\) is an \(n\)-cycle in standard cycle representation; thus, the cycle begins with \(n\text{.}\) The remaining \(n-1\) entries can be any permutation in \(\ss_{n-1}\text{,}\) and the result follows.

🔗

We will finish our survey of cycle structure by answering two questions. The first question is: how many derangements are there in \(\ss_n\text{?}\) The second question is: how many permutations in \(\ss_n\) have exactly \(k\) cycles in their standard cycle representation?

🔗

Theorem 2.6.9.

Let \(D_n\) denote the number of derangements in \(\ss_n\text{.}\) Then \(D_1=0\) and \(D_2=1\text{,}\) and the remaining values satisfy the recursion

\begin{equation*} D_n=(n-1)(D_{n-1}+D_{n-2}) \, . \end{equation*}

🔗

Checkpoint 2.6.10.

Use the recursion above to compute the first ten derangement numbers \(D_n\text{.}\)

🔗

Proof.

It is straightforward to check that \(D_1=0\) and \(D_2=1\text{.}\) Let \(\pi\) be a derangement in \(\ss_n\) and consider the value of \(\pi_1\text{.}\) We know that \(\pi_1=i\neq 1\text{.}\) There are now two possible cases.

🔗

In the first case, \(\pi_i=1\text{.}\) Thus, the permutation \(\pi\) has a two-cycle of the form \((1,i)\text{.}\) There rest of the permutation is a derangement on \([n]\setminus \{1,i\}\text{,}\) and thus there are \((n-1)D_{n-2}\) possible derangements \(\pi\) with this structure, since there are \(n-1\) possible values of \(\pi_1\text{.}\)

🔗

In the second case, \(\pi_i\neq 1\text{.}\) Counting derangements satisfying \(\pi_1=i\neq 1\) and \(\pi_i\neq 1\) is equivalent to counting derangements in \(\ss_{n-1}\text{,}\) since this is the same as counting permutations satisfying \(\pi_1=1\) and \(\pi_j\neq j\) for all \(j>1\) (just switch the roles of \(1\) and \(i\)). Since there are \(n-1\) possible values of \(i\text{,}\) this gives \((n-1)D_{n-1}\) possible derangements \(\pi\) in this case.

🔗

Adding the number of possible derangements from the two cases gives the recursive formula in the theorem.

🔗

Checkpoint 2.6.11.

Discuss the above proof. Does it make sense? Why or why not?

🔗

Definition 2.6.12.

For integers \(n,k\geq 0\text{,}\) we denote by \(c(n,k)\) the number of permutations in \(\ss_n\) with exactly \(k\) cycles. The numbers \(c(n,k)\) are called (signless) Stirling numbers of the first kind. We define \(c(0,0)=1\) and \(c(0,k)=0\) for all \(k\gt 0\) and note that \(c(n,0)=0\) for all \(n\gt 0\text{.}\)

🔗

Checkpoint 2.6.13.

Explain why \(c(n,n-1)=\binom{n}{2}\text{.}\)

🔗

Theorem 2.6.14.

For \(k\gt 0\text{,}\) the Stirling numbers of the first kind satisfy the recursion

\begin{equation*} c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1) \, . \end{equation*}

🔗

Proof.

We express the permutations in \(\ss_{n}\) with exactly \(k\) cycles as \(A_n\uplus B_n\text{,}\) a disjoint union where \(B_n\) are the permutations with \(n\) contained in a cycle of length one, while \(A_n\) are those permutations where \(n\) is contained in a cycle of length at least two.

🔗

For each permutation in \(B_n\text{,}\) if we remove the one-cycle containing \(n\text{,}\) then what remains is a permutation in \(\ss_{n-1}\) with \(k-1\) cycles. This accounts for \(c(n-1,k-1)\) permutations, which is the second summand in our recursion.

🔗

For each permutation in \(A_n\text{,}\) if we remove \(n\) from the cycle containing it, we obtain a permutation \(\sigma\in\ss_{n-1}\) with \(k\) cycles. Each such \(\sigma\) can be obtained from \((n-1)\) different permutations in \(A_n\text{,}\) since there are \((n-1)\) positions in \(\sigma\) where \(n\) could be inserted to obtain an element of \(A_n\text{.}\) Thus, there are \((n-1)c(n,k-1)\) permutations in \(A_n\text{,}\) which is the first summand in our recursion.

🔗

Checkpoint 2.6.15.

Discuss the proof above, and clarify any points of confusion by verifying your understanding with small examples.

🔗

Checkpoint 2.6.16.

Use the recurrence for Stirling numbers of the first kind to create the first seven rows of a triangle, similar to the arithmetical triangle for binomial coefficients. Compare your triangle with the one given on the wikipedia page for Stirling numbers of the first kind.

en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Table_of_values

🔗

Prev Top Next