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)\}$.
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
In [2]:
print(count)
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.
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.
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 [ ]: