Movatterモバイル変換

[0]ホーム

Sari la conținut

Permutare

Modifică legăturile

De la Wikipedia, enciclopedia liberă

Pentru a putea fi rearanjate înt r a c e, nu este necesar ca literelec 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

Permutarea este onoțiune matematică, studiată încombinatorică, care se referă în mod uzual la una din posibilitățile de rearanjare a unei liste ordonate devalori sauobiecte. Cel mai simplu exemplu de permutare este dat de către oanagramă; de exemplu, literele cuvântului CARTE (toatedistincte între ele) pot fi rearanjate formând cuvântul TRACE sau ECART.

C A R T E

T R A C E

E C A R T

În acest exemplu obiectele matematice sunt simboluri dintr-unalfabet formal sau formalizat, literele respectivului alfabet.

Așadar o permutare poate fi înțeleasă ca unul dinn! moduri de aordona liniar omulț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 cadrulcombinatoricii conceptul poate fi extins prin conceptul de k-permutări sauaranjamente care arată numărulsubmulțimilor ordonate ale unei mulțimi date. Poate fi reprezentat printr-o matrice numitămatrice permutare. Noțiunea de permutare este implicată în definireanoțiunii dedeterminant al uneimatrice.

Conceptul de permutare este folosit înalgebră abstractă în studiulstructurilor algebrice cuoperații n-are, constituind o structură algebrică pe mulțimea permutărilor unei mulțimi, structură degrup cuelement neutru permutarea identică pentru compunerea permutărilor (similară compunerii funcțiilor). Este folosită și înteoria probabilităților.

Definiție

[modificare |modificare sursă]

Opermutare a unei mulțimi este o corespondență biunivocă (element la element saubijecție) între omulțime M (finită) și ea însăși.

Notație

[modificare |modificare sursă]

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 șicomutativ) 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)

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 :

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

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 ).

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.

Definiție combinatorică

[modificare |modificare sursă]

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

Înteoria 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 ȘirulA000142 laEnciclopedia electronică a șirurilor de numere întregi (OEIS)

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

Număr de permutări

[modificare |modificare sursă]

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 cafactorialn!.

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 :

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$ .

Operații cu permutări

[modificare |modificare sursă]

Este posibilă cel puțin ooperaț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ă, areelement neutru și fiecare permutare are opermutare inversă.

Orice permutare poate fi scrisă ca produs al unor transpoziții (cicluri de lungime 2 ale unor permutări).