Permutare

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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

Permutarea este un concept matematic care se referă în mod uzual la numărul de posibilități de rearanjare al 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.

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. Î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 abstractă, matematică, a permutării, în care nu mai sunt implicate ordinea sau alte determinări ale subiecților permutați.

Conceptul este studiat în cadrul combinatoricii. Aici conceptul poate extins prin conceptul de k-permutări sau aranjamente care arată numărul submulțimilor ordonate ale unei mulțimi date.

Conceptul abstract de permutare este folosit în cadrul algebrei abstracte în studiul structurilor algebrice cu operații n-are.

Definiție[modificare | modificare sursă]

O permutare este o corespondență biunivocă (element la element sau bijecție) între o mulț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. Spe 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ă[modificare | modificare sursă]

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 în OEIS)
1, 1, 2, 6, 24, 120, 720,...

Număr de permutări[modificare | modificare sursă]

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.( n - 1 ).( n - 2 )...2.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 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.( n - 1 ).( n - 2 )...2.1 în loc de : n.n.n...n.

Note[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]

Vezi și[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]