Permutare

Permutarea este un concept matematic, studiat în combinatorică, care se referă în mod uzual la una din posibilitățile de rearanjare a unei liste ordonate de valori sau obiecte. Cel mai simplu exemplu de permutare este dat de către o anagramă; de exemplu, literele cuvântului CARTE (toate distincte între ele) pot fi rearanjate formând cuvântul TRACE sau ECART.

Pentru a putea fi rearanjate în t r a c e, nu este necesar ca literele c a r t e să fie scrise în aceeași linie.

Cele 6 permutări a 3 bile. Bijecțiile sunt conținute într-o formă implicită. Pentru a explicita bijecțiile - tot 6 la număr - trebuie considerate câte două rânduri de bile

C A R T E

T R A C E

E C A R T

Așadar o permutare poate fi înțeleasă ca unul din n! moduri de a ordona liniar o mulțime, altfel spus este una din mulțimile ordonate ale unei mulțimi. Însă în general nu este necesar ca obiectele permutate să fie ordonate liniar. De pildă, într-o echipă de funcționari, aceștia pot schimba între ei locurile dintr-un birou, locuri care ar putea să nu fie dispuse în linie. Un alt exemplu este cel al unor bile diferit colorate, înșirate pe o sârmă închisă. Această situație va conduce la definiția noțiunii abstracte a permutării, în care nu mai sunt implicate proprietăți individuale ale subiecților permutați.

În cadrul combinatoricii conceptul poate fi extins prin conceptul de k-permutări sau aranjamente care arată numărul submulțimilor ordonate ale unei mulțimi date. Poate fi reprezentat printr-o matrice numită matrice permutare.

Conceptul de permutare este folosit în algebră abstractă în studiul structurilor algebrice cu operații n-are. Se construiește o structură algebrică pe mulțimea permutărilor unei mulțimi, structură de grup cu element neutru permutarea identică la compunerea permutărilor. Este folosită și în teoria probabilităților.

Definiție

O permutare a unei mulțimi este o corespondență biunivocă (element la element sau bijecție) între o mulțime M (finită) și ea însăși.

Notație

O permutare, fiind o funcție, poate fi notată ca un tabel în a cărei primă linie sunt trecute intrările, iar în a doua linie valorile corespondente.

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}$

În cazul notației prin tabele, există n! tabele echivalente care desemnează o aceeași permutare. De exemplu, pentru o permutare de cinci simboluri, există 120 de moduri echivalente de a nota aceeași permutare.

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}={\begin{pmatrix}2&1&3&4&5\\5&2&4&3&1\end{pmatrix}}=...={\begin{pmatrix}5&4&3&2&1\\1&3&4&5&2\end{pmatrix}}$

Deoarece o permutare are o unică descompunere ca produs (asociativ și comutativ) de cicluri, permutarea de mai sus poate fi notată și ca produs de cicluri:

${\begin{pmatrix}1&2&5\end{pmatrix}}{\begin{pmatrix}3&4\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}1&2&5\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}5&1&2\end{pmatrix}}.$

• În cazul anagramei CARTE --> TRACE, notația cu cicluri a permutării este ( C T ) ( A R ) ( E ). (Una din 24 de notații echivalente)
• În cazul anagramei TRACE ----> ECART, notația cu cicluri a permutării este ( E T ) ( C R ) ( A ). (Una din 24 de notații echivalente)

Dacă dispunem de două permutări putem obține prin operația de compunere a permutărilor o a treia permutare; în exemplul de aici, permutarea compusă va fi anagrama CARTE ---> ECART :

C --> T ----> E --> E ----> T --> C ----> R --> A ----> A --> R ----> merge la loc în C

adică ( C E T R A ), un ciclu de cinci litere care poate fi scris în alte patru forme echivalente : ( E T R A C), ( T R A C E ), ( R A C E T ) sau ( A C E T R ).

Pe scurt,

( C E T R A ) = ( E T ) ( C R ) ( A ) aplicată permutării ( C T ) ( A R ) ( E ).

Definiție combinatorică

O permutare este o mulțime de cicluri

„Une permutation est un ensemble de cycles.” (O permutare este un ansamblu de cicluri)

În teoria speciilor, această definiție se scrie :

Perm = Ens ( Cyc )

Pentru a afla direct din definiție numărul de permutări se trece la funcția generatoare exponențială :

perm (x) = exp ( log ( 1 / ( 1-x ) ) = 1 / ( 1-x ) ceea ce conduce la Șirul A000142 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

1, 1, 2, 6, 24, 120, 720,...

Număr de permutări

Numărul de permutări ale unei mulțimi de elemente este dat de produsul numerelor (de ordine ale elementelor) de la 1 la n, cunoscut ca factorial n!.

Pentru a obține acest număr, să considerăm o permutare reprezentată sub formă de tabel în care prima linie este completată, și să încercăm să completăm a doua linie a tabelului, din stânga către dreapta, folosind exact o singură dată numere din prima linie.

Pentru prima valoare avem n posibilități de completare. Pentru a doua valoare avem (n - 1) posibilități, ș.a.m.d.. Principiul multiplicativ afirmă că în total vor fi :

$n\cdot (n-1)\cdot (n-2)...2\cdot 1$

variante de a completa tabelul, adică de a defini o permutare pe o mulțime cu n elemente. Considerând că fiecare element are un număr de posibilități de poziționare egal cu numărul elementelor mulțimii (n) aparent ar rezulta că numărul total de permutări ar fi nⁿ însă datorită echivalenței unor poziționări când se parcurge mulțimea de la primul la ultimul element, numărul scade la $n\cdot (n-1)\cdot (n-2)...2\cdot 1$ în loc de : $n\cdot n\cdot n...n$.

Note

• Gluckman, Albert (1965), The group of permutations on 3 letters and the proper rotations of a 3-dimensional orthogonal frame, Greenbelt, Maryland: Goddard Space Flight Center 

Bibliografie

• Dixon, John D.; Mortimer, Brian (1996), Permutation groups, Graduate Texts in Mathematics, 163, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94599-6, MR 1409812 

Vezi și

• Combinare
• Definiție combinatorică
• Factorial
• Aranjament
• Multimulțime
• Paritatea unei permutări
• Permutare ciclică
• Partiție (matematică)
• Teorema multinomială
• Matrici permutare
• Probabilitate
• Prim permutabil
• Teoria lui Galois

Legături externe

• Anagrame în limba română