Permutações

Vamos começar estudando o conjunto das bijeções de um conjunto finito. Mais precisamente vamos tomar o conjunto finito $ E_n = \{1,2,\dots,n\} \subset \mathbb{N}$. Consideremos agora o conjunto de todas as funções bijetoras $ \sigma : E_n \to E_n$, ou seja $\mathbb{S}_n=\{\sigma: E_n \to E_n: (\forall k \in E_n \implies \exists l \sigma(l)=k) \wedge (\sigma(r)=\sigma(s) \implies r=s)\}$.

Notação de Cauchy

Uma forma de dar a função $\sigma$ pode ser:

$$ \sigma = \left(\begin{array}{cccc} 1 & 2& \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n)\end{array} \right)$$

que é chamada notação de Cauchy.

Por exemplo $$\sigma = \left(\begin{array}{ccccc} 1 & 2& 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4\end{array} \right)$$ representa a função tal que $\sigma(1)=3,$ $\sigma(2)=2$ etc. Como é a representação da inversa desta função?

Se convecionamos que na primeira linha teremos sempre os elementos ordenados, então a notação pode ser resumida $$ \sigma = \left[\begin{array}{cccc} 3 & 2& 1 & 5 & 4 \end{array} \right]$$


In [1]:
#Exemplo estas são as permutações em E_5
import itertools as it
s=[1, 2, 3, 4, 5]
SS= it.permutations(s)
count = 0
for x in SS:
    print(str(x))
    count+=1


(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 2, 4, 5, 3)
(1, 2, 5, 3, 4)
(1, 2, 5, 4, 3)
(1, 3, 2, 4, 5)
(1, 3, 2, 5, 4)
(1, 3, 4, 2, 5)
(1, 3, 4, 5, 2)
(1, 3, 5, 2, 4)
(1, 3, 5, 4, 2)
(1, 4, 2, 3, 5)
(1, 4, 2, 5, 3)
(1, 4, 3, 2, 5)
(1, 4, 3, 5, 2)
(1, 4, 5, 2, 3)
(1, 4, 5, 3, 2)
(1, 5, 2, 3, 4)
(1, 5, 2, 4, 3)
(1, 5, 3, 2, 4)
(1, 5, 3, 4, 2)
(1, 5, 4, 2, 3)
(1, 5, 4, 3, 2)
(2, 1, 3, 4, 5)
(2, 1, 3, 5, 4)
(2, 1, 4, 3, 5)
(2, 1, 4, 5, 3)
(2, 1, 5, 3, 4)
(2, 1, 5, 4, 3)
(2, 3, 1, 4, 5)
(2, 3, 1, 5, 4)
(2, 3, 4, 1, 5)
(2, 3, 4, 5, 1)
(2, 3, 5, 1, 4)
(2, 3, 5, 4, 1)
(2, 4, 1, 3, 5)
(2, 4, 1, 5, 3)
(2, 4, 3, 1, 5)
(2, 4, 3, 5, 1)
(2, 4, 5, 1, 3)
(2, 4, 5, 3, 1)
(2, 5, 1, 3, 4)
(2, 5, 1, 4, 3)
(2, 5, 3, 1, 4)
(2, 5, 3, 4, 1)
(2, 5, 4, 1, 3)
(2, 5, 4, 3, 1)
(3, 1, 2, 4, 5)
(3, 1, 2, 5, 4)
(3, 1, 4, 2, 5)
(3, 1, 4, 5, 2)
(3, 1, 5, 2, 4)
(3, 1, 5, 4, 2)
(3, 2, 1, 4, 5)
(3, 2, 1, 5, 4)
(3, 2, 4, 1, 5)
(3, 2, 4, 5, 1)
(3, 2, 5, 1, 4)
(3, 2, 5, 4, 1)
(3, 4, 1, 2, 5)
(3, 4, 1, 5, 2)
(3, 4, 2, 1, 5)
(3, 4, 2, 5, 1)
(3, 4, 5, 1, 2)
(3, 4, 5, 2, 1)
(3, 5, 1, 2, 4)
(3, 5, 1, 4, 2)
(3, 5, 2, 1, 4)
(3, 5, 2, 4, 1)
(3, 5, 4, 1, 2)
(3, 5, 4, 2, 1)
(4, 1, 2, 3, 5)
(4, 1, 2, 5, 3)
(4, 1, 3, 2, 5)
(4, 1, 3, 5, 2)
(4, 1, 5, 2, 3)
(4, 1, 5, 3, 2)
(4, 2, 1, 3, 5)
(4, 2, 1, 5, 3)
(4, 2, 3, 1, 5)
(4, 2, 3, 5, 1)
(4, 2, 5, 1, 3)
(4, 2, 5, 3, 1)
(4, 3, 1, 2, 5)
(4, 3, 1, 5, 2)
(4, 3, 2, 1, 5)
(4, 3, 2, 5, 1)
(4, 3, 5, 1, 2)
(4, 3, 5, 2, 1)
(4, 5, 1, 2, 3)
(4, 5, 1, 3, 2)
(4, 5, 2, 1, 3)
(4, 5, 2, 3, 1)
(4, 5, 3, 1, 2)
(4, 5, 3, 2, 1)
(5, 1, 2, 3, 4)
(5, 1, 2, 4, 3)
(5, 1, 3, 2, 4)
(5, 1, 3, 4, 2)
(5, 1, 4, 2, 3)
(5, 1, 4, 3, 2)
(5, 2, 1, 3, 4)
(5, 2, 1, 4, 3)
(5, 2, 3, 1, 4)
(5, 2, 3, 4, 1)
(5, 2, 4, 1, 3)
(5, 2, 4, 3, 1)
(5, 3, 1, 2, 4)
(5, 3, 1, 4, 2)
(5, 3, 2, 1, 4)
(5, 3, 2, 4, 1)
(5, 3, 4, 1, 2)
(5, 3, 4, 2, 1)
(5, 4, 1, 2, 3)
(5, 4, 1, 3, 2)
(5, 4, 2, 1, 3)
(5, 4, 2, 3, 1)
(5, 4, 3, 1, 2)
(5, 4, 3, 2, 1)

In [2]:
print(count)


120

Ciclos e transposições

Uma permutação $\sigma \in \mathbb{S}_n$ deixa um elemento $k \in E_n$ fixo se $\sigma(k)=k$. Um $r$-ciclo é uma permutação $\sigma$ que num subconjunto $\{x_1,\dots,x_r\} \in E_n$ satisfaz $\sigma(x_i) = x_{i+1}$ e $\sigma(x_r)=x_1$, e deixa os demais elementos fixos. Neste caso a notação \sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_r \end{pmatrix}$, é chamada notação em ciclos.

Exemplos

Em $E_5$ a permutação $\begin{pmatrix} 1 & 5 & 3 \end{pmatrix}$ =$\begin{pmatrix} 5 & 3 & 1 \end{pmatrix}$=$\begin{pmatrix} 3 & 1 & 5 \end{pmatrix}$ = $\begin{bmatrix} 5 & 2 & 1 & 4 & 3 \end{bmatrix}$

Um $2$-ciclo é chamado de transposição.

Representação matricial de uma permutação

Uma permutação é uma bijeção $\sigma: S_n \to S_n$, em particular é uma relação binária em $S_n \times S_n$, isto é, $i \in S_n$ está relacionado com $j\in S_n$ quando $\sigma(i)=j$, podemos identificar esta relação com uma matriz $n\times n$ com os coeficientes $a_{ij}=1$ se $\sigma(j)=i$ e $a_{ij} =0$ se $\sigma(i)\not =j$.

Por exemplo, a representação matricial de $$ \sigma = \left[\begin{array}{cccc} 3 & 2& 1 & 5 & 4 \end{array} \right]$$ é

$$ M_\sigma = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0&1&0&0&0 \\ 1 & 0 & 0 & 0 & 0 \\ 0&0&0&0&1 \\ 0&0&0&1&0 \end{pmatrix} $$

In [ ]: