Permutare
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
O permutare este un mod de a ordona obiecte distincte succesiv , ca în anagrama unui cuvânt. În termeni matematici , o permutare a unui set este definit ca o funcție bijectivă .
Enumerați și numărați permutările
Numărul de permutări ale obiecte este egal cu factorialul de :
de fapt există modalități de alegere a obiectului care ocupă prima poziție, pentru fiecare dintre ele există modalități de a alege obiectul care ocupă a doua poziție, apoi pentru fiecare pereche de obiecte fixate în primele două poziții există modalități de alegere a obiectului în a treia poziție și așa mai departe, până când toate pozițiile sunt ocupate.
De exemplu, posibilele permutări ale seriei de patru litere „ABCD” sunt 24 și apar ca:
- ABCD BACD CABD DABC
- ABDC BADC CADB DACB
- ACBD BCAD CBAD DBAC
- ACDB BCDA CBDA DBCA
- ADBC BDAC CDAB DCAB
- ADCB BDCA CDBA DCBA
Seturi cu repetări
Dacă există elemente repetate în setul de pornire, unele permutări dau aceeași secvență. De exemplu, permutările din seria de patru litere „ABAB” dau doar 6 rezultate distincte:
- AABB ABAB ABBA
- BBAA BABA BAAB
În general, dacă setul este alcătuit din obiecte, dintre care Sunt unic, de alt tip etc. până la , cu , numărul rezultatelor distincte este
care se numește coeficientul multinomial .
În exemplul prezentat, Și , și astfel obținem
Demonstrație
Puneți toate permutările simple ale obiecte în care numai se repetă tratându-le ca fiind diferite între ele astfel încât să aibă permutările literelor care nu sunt egale pe linii și permutările acelorași litere pe coloane. Procedând în acest fel pe fiecare rând vor exista aceleași permutări, deci dacă calculăm produsul numărului de rânduri cu numărul de coloane obținem numărul de permutări:
Prin urmare, vor exista atâtea rânduri cât permutări ale literelor repetate și câte coloane câte permutări cu repetare
Dacă obiectele care se repetă sunt de mai multe tipuri, atunci elementele unui tip sunt eliminate mai întâi tratându-le ca fiind diferite de cele de celălalt tip. Apoi aplicăm formula de mai sus obținând permutările simple ale obiectelor inclusiv cele de tipul rămas pe care va fi posibil să aplicăm din nou formula obținând permutările cu repetarea căutată. Generalizarea formulei se obține
Compoziţie
O permutare este o funcție bijectivă . Două permutări Și pot fi deci compuse și rezultatul este încă o permutare. Întregul a permutărilor de cu operația de compoziție formează un grup , numit grup simetric . Elementul neutru este permutarea care lasă toate elementele fixe.
Cicluri
Este o succesiune de elemente distincte ale . Ciclul
permutarea este cea care le deplasează pe toate înainte cu una și îi menține pe ceilalți fixați. Mai formal este definit astfel:
- pentru ceilalti
Ordinea ciclului este numărul . O transpunere este un ciclu de ordinul 2: constă pur și simplu în schimbul elementelor Și , lăsând toate celelalte fixate.
Două cicluri Și sunt independenți dacă pentru fiecare Și . Două cicluri independente Și se schimbă, adică . Importanța ciclurilor constă în următoarea teoremă: Fiecare permutare este scrisă în mod unic ca produs al ciclurilor independente.
Deoarece ciclurile independente navighează, unicitatea trebuie înțeleasă dacă nu se schimbă ordinea ciclurilor.
În cele din urmă, observăm că notațiile Și definiți același ciclu, în timp ce Și sunt cicluri diferite.
Notaţie
Există două notații pentru scrierea unei permutări. De exemplu, luați în considerare o permutare a setului Puteți scrie poziția în care este mutat sub fiecare număr:
Alternativ, aceeași permutare poate fi codificată folosind teorema enunțată mai sus, scriind-o ca produs al ciclurilor. În cazul de exemplu obținem
Cu notația ciclică se pot compune cu ușurință două permutări: de exemplu Și dăuna Rețineți că compoziția se face de la dreapta la stânga. De exemplu, pentru a vedea unde este trimis 1 din compoziție vezi asta îl trimite în 2, nu mișcă 2 și, în cele din urmă trimite 2 la 5. Deci 1 merge la 5.
Semnul unei permutări
Definiție
Fiecare ciclu este produsul transpunerilor. De fapt, întotdeauna cu compoziția de la dreapta la stânga, avem:
Rezultă că fiecare permutare este produsul transpunerilor. Numărul acestor transpuneri nu este determinat în mod unic de permutare: de exemplu, transpunerea poate fi scrisă de asemenea ca sau . Se poate arăta că dacă aceeași permutare poate fi scris fie ca produs al transpuneri, atât ca produs al transpuneri, atunci Și au aceeași paritate , adică sunt ambele pare sau ambele impare.
O permutare este numit chiar sau impar , în funcție de faptul dacă acesta poate fi obținut ca produs al unui număr par sau impar de transpoziții. Semnul este definit ca +1 și respectiv -1.
Exemple
- Toate transpunerile sunt ciudate.
- Între permutări ale elementelor Sunt:
- sunt egale;
- sunt ciudate.
Proprietate
După ce am definit produsul a două permutări ca fiind compoziția lor, putem spune că funcția „semn” este multiplicativă , adică
Grup alternativ
Jumătate din permutări ale unui set de elementele sunt pare. Deoarece funcția de semn este multiplicativă, chiar permutările formează un subgrup normal al grupului simetric a permutărilor de din indexul doi, grupul alternativ menționat este indicat cu Acesta este nucleul omomorfismului de grup
Imaginea este un grup ciclic cu două elemente.
Formula pentru semn
Semnul unei permutări poate fi calculat folosind următoarea formulă:
Elemente conexe
Alte proiecte
- Wikimedia Commons conține imagini sau alte fișiere cu permutare
linkuri externe
- ( EN ) Permutation , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
Controlul autorității | Tezaur BNCF 32734 |
---|