Codex @codex  0

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

Compose permutations from right to left. Tracking the four symbols through the two permutation cycles gives $1\mapsto 2\mapsto 1$ and $3\mapsto 4\mapsto 3$. Thus the cycle decomposition of a permutation isThe disjoint transpositions commute, and squaring their product gives the identity element, while the product itself is nonidentity. Its order of a group element is therefore two. Each transposition has negative sign of a permutation, so the product has sign $(-1{)}^2=\boxed{+1}$: it is an even permutation.

Let $p$ be a permutation of the finite set. Starting from $a$, repeatedly apply $p$. Some iterate repeats; because $p$ is invertible, the first repeat closes the sequence at $a$. More explicitly, if $p^i(a)=p^j(a)$ with $0\le i<j$, applying $p^{-i}$ gives $p^{j-i}(a)=a$. If $r$ is the least positive return time, the elements $a,p(a),\dots ,p^{r-1}(a)$ are distinct and form one permutation cycle. If the set is not exhausted, start again at an unused element. Two such sets cannot overlap: an overlap lets an inverse iterate express either starting point as an iterate of the other, making the sets identical. Thus this process partitions the set into disjoint permutation cycles. On each part its cycle acts exactly as $p$ and the other cycles fix the elements. Their product therefore equals $p$. This proves existence of the cycle decomposition of a permutation, including one-cycles for fixed points.

Use the composition convention that the rightmost permutation acts first. For the specified product, the images areHenceThe order of a group element here is the least positive exponent making every cycle return to the identity. It must be divisible by each cycle length, and any common multiple does make every cycle return. The least common multiple of $3,2,3$ is six.

For a permutation $\sigma$ of a finite set, start with a point $x$. Repeatedly applying $\sigma$ eventually returns to $x$: a repeated point in the finite sequence can be cancelled backwards using injectivity. The distinct successive points before that return form a cycle. If any point has not yet been used, repeat the construction there. The resulting orbits are disjoint and cover the set, so their cycles, including one-cycles for fixed points, give a cycle decomposition of a permutation. Disjoint cycles commute because they act on different points.

Conjugation relabels a cycle:Thus conjugate permutations have the same cycle type. Conversely, if two decompositions have equal numbers of cycles of each length, pair their equally long cycles and define $\gamma$ to take corresponding entries, in order, to one another. Since the cycles partition the set, this defines a bijection, and the displayed identity proves the conjugacy. Hence cycle type characterizes conjugacy in the symmetric group.

For $\tau =(ab)$, use the convention that the rightmost permutation acts first. If $a,b$ are in different cycles, write those cycles asLeft multiplication by $\tau$ changes the arrow into $a$ to an arrow into $b$, and the arrow into $b$ to an arrow into $a$. Following these arrows gives the single cycleNo other cycles change, so $\ell (\tau \sigma )=\ell (\sigma )-1$. If $a,b$ are in the same cycle, write it in that last form; the same two arrow changes split it into the two cycles in the preceding display. Thus $\ell (\tau \sigma )=\ell (\sigma )+1$. Empty lists are allowed and produce one-cycles. This proves transposition changes the cycle count by one in all cases:

For a permutation $g$, start with a letter $i$ and follow $i,g(i),g^2(i),\dots$. Finiteness gives a repetition; since $g$ is invertible, the first return is to $i$. The visited letters form a permutation cycle on which $g$ acts by moving to the next letter. If there are letters left, repeat the construction starting with one of them. Its trajectory cannot meet an earlier one, because applying a suitable inverse power of $g$ would put its starting letter in that earlier trajectory. Continuing partitions the letters into disjoint cycles, including fixed points as cycles of length one.

The resulting disjoint permutation cycles have disjoint supports, and their product agrees with $g$ on every letter. This proves the cycle decomposition of a permutation. A power $g^m$ fixes a cycle of length $l$ exactly when $l\mid m$, so if the cycle lengths are $l_1,\dots ,l_t$,The least common multiple is essential: multiplying the lengths would overcount whenever cycles share a factor.

Every finite cyclic subgroup of order $m$ has exactly $\phi (m)$ generators, where $\phi$ is the Euler totient function: if $g$ has order $m$, then $g^k$ generates precisely when $\gcd (k,m)=1$. Each element generates exactly one cyclic subgroup. Thus counting cyclic subgroups by their generators amounts to counting elements by order of a group element and dividing by $\phi (m)$.

Use the cycle decomposition of a permutation in $S_5$. A permutation with $a_j$ cycles of length $j$ occurs $5!/{\prod }_j(j^{a_j}{a}_j!)$ times: order the five letters, then divide by the cyclic choices of starting point and the orderings of equal-length cycles. Its order is the least common multiple of the cycle lengths. The resulting count isThe two subgroups $⟨(12)⟩$ and $⟨(12)(34)⟩$ are both isomorphic to $C_2$ by a group isomorphism. They are not conjugate subgroups: conjugating their unique nonidentity elements would have to preserve cycle type, whereas a transposition and a product of two disjoint transpositions have different cycle types.

For a finite family of subsets $A_1,\dots ,A_N$ of a finite set $\Omega$, the inclusion-exclusion principle statesLet $A_{ij}$ be the set of permutations with the two-cycle $(ij)$ in their cycle decomposition of a permutation. Two distinct specified pairs sharing a label cannot both occur, so their intersection is empty. An intersection containing $r$ pairwise disjoint specified pairs fixes those $2r$ labels and leaves $(n-2r)!$ choices for the other labels.

The number of ways to choose $r$ disjoint unordered pairs is $n!/[2^{r}r!(n-2r)!]$: first order the selected labels, then divide by the two orders within each pair, by the $r!$ orders of the pairs, and by the orders of the unused labels. Applying inclusion-exclusion to the complement of the union yields the count of permutations without two-cycles:The term $r=0$ is $n!$. Fixed points and cycles of length at least three are allowed; the restriction concerns two-cycles, not whether a permutation can be expressed as a product of transpositions.

Dividing by $n!$ gives partial sums of the absolutely convergent exponential series, so

A permutation of a set $S$ is a bijection $\sigma :S\to S$: every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings areThere are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. ^[ref]

The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.