Permutări

Fie mulţimea finită \displaystyle A=\left \{ 1,\: 2,\: 3,\: \cdots ,\: n \right \} , unde \displaystyle n\in \mathbb{N},\; n\geq 2 .

Se numeşte permutare de ordinul n o funcţie bijectivă \displaystyle \sigma :A\rightarrow A prezentată sub formă de tabel:

\displaystyle \sigma =\begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ \sigma \left ( 1 \right ) & \sigma \left ( 2 \right ) & \sigma \left ( 3 \right ) & \cdots & \sigma \left ( n \right ) \end{pmatrix}

Mulţimea \displaystyle S_{n} a tuturor permutărilor de ordinul \displaystyle n are \displaystyle n! elemente.

\displaystyle card\: S_{n}=n!

Compunerea permutărilor

Fie permutările \displaystyle \sigma =\begin{pmatrix} 1 & 2 & \cdots & n\\ \sigma \left ( 1 \right ) & \sigma \left ( 2 \right ) & \cdots & \sigma \left ( n \right ) \end{pmatrix} şi \displaystyle \tau =\begin{pmatrix} 1 & 2 & \cdots & n\\ \tau \left ( 1 \right ) & \tau \left ( 2 \right ) & \cdots & \tau \left ( n \right ) \end{pmatrix} .

Compusa permutărilor \displaystyle \sigma şi \displaystyle \tau este permutarea de acelaşi ordin

\displaystyle \sigma \circ \tau =\begin{pmatrix} 1 & 2 & \cdots & n\\ \sigma \left (\tau \left ( 1 \right ) \right ) & \sigma \left (\tau \left ( 2 \right ) \right ) & \cdots & \sigma \left (\tau \left ( n \right ) \right ) \end{pmatrix}


Exemplu:

Dacă \displaystyle \sigma =\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} , iar \displaystyle \tau =\begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 1 & 3 \end{pmatrix} , atunci

\displaystyle \sigma \circ \tau =\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 1 & 3 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 3 & 2 \end{pmatrix}

Reprezentată schematic, compunerea permutărilor se realizează astfel:


Proprietăţi ale compunerii permutărilor

\displaystyle 1^{\circ} Compunerea permutărilor este asociativă, dar nu este comutativă.

\displaystyle 2^{\circ} Compunerea permutărilor admite ca element neutru permutarea identică \displaystyle e=\begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ 1 & 2 & 3 & \cdots & n \end{pmatrix} , adică \displaystyle \sigma \circ e=e \circ \sigma =\sigma pentru orice permutare \displaystyle \sigma \in S_{n}

Inversa unei permutări

Pentru orice permutare \displaystyle \sigma \in S_{n} , există o unică permutare \displaystyle \sigma^{-1} \in S_{n} , astfel încât \displaystyle \sigma \circ \sigma ^{-1}=\sigma ^{-1}\circ \sigma =e .

Permutarea \displaystyle \sigma ^{-1} se numeşte inversa permutării \displaystyle \sigma .

Pentru a găsi inversa unei permutări, cele două linii ale permutării se inversează (linia a doua se scrie prima, iar prima linie se scrie dedesubt), apoi se ordonează coloanele astfel încât elementele de pe prima linie să fie în ordine crescătoare.


Exemplu:

Fie \displaystyle \sigma=\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} .

Se inversează cele două linii şi se obţine tabelul \displaystyle \begin{pmatrix} 3 & 4 & 2 & 1\\ 1 & 2 & 3 & 4 \end{pmatrix} .

Apoi se ordonează coloanele astfel încât elementele de pe prima linie să fie în ordine crescătoare şi se obţine

\displaystyle \sigma ^{-1}=\begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 1 & 2 \end{pmatrix}


Inversiunile unei permutări

O inversiune în permutarea \displaystyle \sigma este o pereche de numere naturale \displaystyle \left (\sigma\left ( i \right ),\: \sigma \left ( j \right ) \right ) cu proprietatea \displaystyle i<j şi \displaystyle \sigma \left ( i \right )>\sigma \left ( j \right ) .

Numărul de inversiuni al unei permutări se notează \displaystyle m\left ( \sigma \right ) .

Numărul \displaystyle \varepsilon \left ( \sigma \right )=\left ( -1 \right )^{m\left ( \sigma \right )} se numeşte signatura sau semnul permutării \displaystyle \sigma .

Spunem că permutarea este pară dacă \displaystyle m\left (\sigma \right ) este număr par şi \displaystyle \varepsilon \left (\sigma \right )=1 , respectiv permutarea este impară dacă \displaystyle m\left (\sigma \right ) este număr impar şi \displaystyle \varepsilon \left (\sigma \right )=-1 .


Exemplu:

Permutarea \displaystyle \sigma=\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} are inversiunile \displaystyle \left ( 3,2 \right );\: \left ( 3,1 \right );\: \left ( 4,2 \right );\: \left ( 4,1 \right );\: \left ( 2,1 \right ) .

Numărul de inversiuni \displaystyle m\left ( \sigma \right )=5 .

Semnul permutării este \displaystyle \varepsilon \left ( \sigma \right )=\left ( -1 \right )^{5}=-1 .

Permutarea \displaystyle \sigma este impară.


Transpoziţii

Se numeşte transpoziţie o permutare, notată \displaystyle \tau _{ij} , în care sunt interschimbate numai elementele \displaystyle i şi \displaystyle j din linia a doua a tabloului, restul elementelor rămânând neschimbate.

\displaystyle \tau _{ij}=\begin{pmatrix} 1 & 2 & 3 & \cdots & i & \cdots & j & \cdots & n\\ 1 & 2 & 3 & \cdots & j & \cdots & i & \cdots & n \end{pmatrix}

Proprietăţi:

\displaystyle 1^{\circ} Orice transpoziţie este o permutare impară: \displaystyle m\left ( \tau _{ij} \right )=1 , \displaystyle \varepsilon \left ( \tau _{ij} \right )=-1

\displaystyle 2^{\circ} \displaystyle \tau _{ij}^{-1}=\tau _{ij}

\displaystyle 3^{\circ} \displaystyle \tau _{ij}^{2}=e


Aplicaţie:

Să se scrie permutarea \displaystyle \sigma =\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} ca produs de transpoziţii.

Se observă, pe prima coloană a permutării \displaystyle \sigma , că lui \displaystyle 1 îi corespunde \displaystyle 3 şi se consideră transpoziţia

\displaystyle \tau _{13}=\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 2 & 1 & 4 \end{pmatrix}

Se efectuează

\displaystyle \tau _{13}\circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 2 & 1 & 4 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 4 & 2 & 3 \end{pmatrix}

La rezultatul obţinut se observă, pe coloana a doua, că lui \displaystyle 2 îi corespunde \displaystyle 4 şi se consideră transpoziţia

\displaystyle \tau _{24} = \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 4 & 3 & 2 \end{pmatrix}

Se efectuează

\displaystyle \tau _{24} \circ \tau _{13}\circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 4 & 3 & 2 \end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 4 & 2 & 3 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 2 & 4 & 3 \end{pmatrix}=\tau _{34}

S-a obţinut

\displaystyle \tau _{24} \circ \tau _{13}\circ \sigma =\tau _{34}

Se amplifică egalitatea la stânga cu \displaystyle \tau _{24}^{-1} :

\displaystyle \tau _{24}^{-1}\circ \tau _{24} \circ \tau _{13}\circ \sigma =\tau _{24}^{-1}\circ \tau _{34}

Ţinând seama că \displaystyle \tau _{24}^{-1}\circ \tau _{24}=e , iar \displaystyle \tau _{24}^{-1}=\tau _{24} , se obţine:

\displaystyle \tau _{13}\circ \sigma =\tau _{24}\circ \tau _{34}

Apoi se amplifică şi cu \displaystyle \tau _{13}^{-1} la stânga:

\displaystyle \tau _{13}^{-1}\circ \tau _{13}\circ \sigma =\tau _{13}^{-1}\circ \tau _{24}\circ \tau _{34}

Ţinând seama că\displaystyle \tau _{13}^{-1}\circ \tau _{13}=e , iar \displaystyle \tau _{13}^{-1}=\tau _{13} se obţine, în final:

\displaystyle \sigma =\tau _{13}\circ \tau _{24}\circ \tau _{34}