Considerăm setul primelor numere naturale, pe care le denumește.
Definiția. Prin permutarea setului de elemente, numim orice aranjament al acestor elemente într-o anumită ordine. Numărul este numit ordinea permutării.
Exemplu 1. Luați în considerare. Permutările pentru articolele de la:
Se poate demonstra că numărul de permutări diferite pentru un set de elemente este egal cu.
Definiția. Numerele și formează o inversiune (încălcarea ordinii) în permutare. dacă și este situat în stânga.
Definiția. Numărul de inversiuni ale tuturor elementelor de permutare va fi numit numărul de inversiuni permutării și se va denota prin.
Pentru a număra numărul de inversiuni într-o permutare, este necesar să numărați pentru fiecare element al permutării câte elemente sunt în fața ei (sau câte elemente ale celor mai mici sunt în spatele ei) și adăugați toate aceste numere.
Exemplul 2. Se calculează numărul de inversiuni în permutare.
Cele trei inversiuni nu se formează, iar a patra, unitatea dă trei inversiuni. În consecință ,.
Definiția. O permutare este numită chiar (ciudată). dacă numărul de inversiuni din acesta este chiar (impare). Permutarea fără inversiuni este considerată chiar.
Proprietatea 1. Dacă oricare dintre cele două elemente este schimbată în permutare, atunci paritatea sa se va schimba.
Când interschimbate elementele adiacente, sau numărul de inversiuni per unitate crește dacă perechea de elemente de inversiune nu sunt formate, sau pe unitatea este redusă, în cazul în care perechea inițială de elemente formează o inversare. Ie numărul inițial de inversiuni se modifică cu unul, și, prin urmare, paritatea permutației se modifică.
Luați în considerare cazul elementelor care nu sunt învecinate.
Să presupunem că permutarea are forma. Schimbați locurile. Obținem o permutare. Pentru a obține o permutare de la permutare. traducem elementul în loc între. Pentru a face acest lucru, trebuie să faceți permutări. După aceea, deplasați elementul pe poziție. pentru care este necesar să se facă permutări. Deoarece paritatea se schimbă atunci când elementele adiacente sunt schimbate, atunci toate schimbările de paritate vor avea loc. și anume paritatea modificărilor permutării.
Proprietatea 2. Numărul de permutații par și impare pentru un set este egal cu.
Evident, fiecare permutare ciudată corespunde unei permutații ciudate și invers. În consecință, ambele sunt același număr. Și de atunci din toate permutările. atunci chiar și ciudat va fi pentru fiecare.
Exemplul 3. Alegeți numere astfel încât permutarea să fie uniformă.
Deoarece permutările sunt de ordinul al șaselea, ele pot lua valorile fie 2 sau 6.
În cazul în care obținem o permutare. Să numărăm numărul de inversiuni din ea :. și anume avem o permutare ciudată.
Rămâne să luăm în considerare cazul. Atunci obținem o permutare. .
Numărul de inversiuni nu poate fi calculat, ci să profite de faptul că ciudățenia rezultă imediat din paritatea permutării în conformitate cu proprietatea 1.
Exemplul 4. Care este numărul maxim de inversiuni într-o permutare?
Răspunsul la întrebare apare din tehnologia de calcul a numărului de permutări. Numărul de inversiuni în permutare va fi maxim dacă fiecare element de permutare ulterioară este mai mic decât cel precedent, adică ..
Exemplul 5. Câte inversiuni formează un număr 1 într-o permutare.
Inversiunile cu o unitate formează numai primele elemente de permutare, adică =.
Articole similare
Trimiteți-le prietenilor: