From Wikipedia, the free encyclopedia
Permutarea este o noțiune 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.
În acest exemplu obiectele matematice sunt simboluri dintr-un alfabet formal sau formalizat, literele respectivului alfabet.
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 obiectelor permutate.
Î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. Noțiunea de permutare este implicată în definirea noțiunii de determinant al unei matrice.
Conceptul de permutare este folosit în algebră abstractă în studiul structurilor algebrice cu operații n-are, constituind o structură algebrică pe mulțimea permutărilor unei mulțimi, structură de grup cu element neutru permutarea identică pentru compunerea permutărilor (similară compunerii funcțiilor). Este folosită și în teoria probabilităților.
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.
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.
Î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.
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:
Din două permutări se poate obține prin operația algebrică de compunere a permutărilor o a treia permutare; în exemplul de aici, permutarea compusă va fi anagrama CARTE ---> ECART :
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,
O permutare mai poate fi notată printr-o matrice pătrată cu număr de linii și coloane egal cu numărul de elemente ale permutării, matrice numită matrice permutare.
În teoria speciilor, această definiție se scrie :
Pentru a afla direct din definiție numărul de permutări se trece la funcția generatoare exponențială :
Numărul de permutări posibile 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, considerând o permutare reprezentată sub formă de tabel în care prima linie este completată, 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 există n posibilități de completare. Pentru a doua valoare (n - 1) posibilități, ș.a.m.d.. Principiul multiplicativ afirmă că în total vor fi :
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 nn î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 loc de : .
Este posibilă cel puțin o operație algebrică cu permutări. Operațiile se pot defini cu permutări de aceeași dimensiune sau de dimensiuni diferite. Un exemplu de operație este compunerea (produsul) permutărilor (echicardinale). Compunerea permutărilor este de fapt o compunere a corespondențelor (funcții) bijective definite pe o mulțime finită cu valori în ea însăși. Este asociativă, are element neutru și fiecare permutare are o permutare inversă.
Orice permutare poate fi scrisă ca produs al unor transpoziții (cicluri de lungime 2 ale unor permutări).
|title=
(ajutor)Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.