Ciclos

Um exemplo simples de uma permutação é obtido como segue: escolha quaisquer dois inteiros distintos entre $1$ e $k$ , digamos, $p$ e $q$ , e escreva

Tal permutação é chamada de transposição porque ele troca dois elementos.

Mais geralmente, seja $a_{1}, \dots, a_{k}$ ser $k$ distintos elementos de ${1, \dots, n}$ . Consideramos a permutação $σ$ definido por

Uma permutação como essa é chamado de k-ciclo ou um ciclo de comprimento k. Denotamos um ciclo por $(a_{1} a_{2} \dots a_{k})$ .

Note que $(a_{1} a_{2} \dots a_{k}) = (a_{2} a_{3} \dots a_{k} a_{1}) = \dots$ , então há múltiplas formas de escrever o mesmo ciclo.

Cada transposição é um 2-ciclo. O ciclo de identidade $σ (i) = i$ para todos $i$ é considerado um 1-ciclo.

Disjoint cycles commute. That is, if $(a_{1} \dots a_{k})$ and $(b_{1} \dots b_{m})$ are cycles with ${a_{1}, \dots, a_{k}} \cap {b_{1}, \dots, b_{m}} = \emptyset$ , then

Every permutation can be written as a product of disjoint cycles. This representation is unique up to the order in which we write the cycles.

Parity of a Permutation

A transposition changes the parity of a permutation. That is, if $σ$ is any permutation and $τ$ is a transposition, then the parity of $σ τ$ is opposite to the parity of $σ$ .

We can write any permutation as a product of transpositions. The parity of a permutation is well defined: it doesn't depend on how we write a permutation as a product of transpositions.

Even and Odd Permutations

A permutation with even parity is called an even permutation. A permutation with odd parity is called an odd permutation.