Permutare ciclică

Nu confundați cu Deplasare circulară.

În matematică și în special în teoria grupurilor o permutare ciclică este o permutare a elementelor unei mulțimi X care aplică elementele unei submulțimi S din X pe ele înseși într-o manieră ciclică, în timp ce fixează (adică aplică pe ele însele) toate celelalte elemente ale lui X. Dacă S are k elemente, permutarea se numește k-ciclu. Adesea permutările sunt notate prin lista elementelor lor, încadrată de paranteze, în ordinea în care sunt permutate.

De exemplu, fie X = {1, 2, 3, 4}, Permutarea (1, 3, 2, 4), care trimite 1 la 3, 3 la 2, 2 la 4 și 4 la 1 (deci S = X) este o permutare ciclică de 4, permutarea (1, 3, 2) care trimite 1 la 3, 3 la 2, 2 la 1 și 4 la 4 (deci S = {1, 2, 3}, iar 4 este un element fix) este o permutare ciclică de 3. Pe de altă parte, permutarea care trimite 1 la 3, 3 la 1, 2 la 4 și 4 la 2 nu este o permutare ciclică, deoarece permută separat perechile {1, 3} și {2, 4}.

Mulțimea S se numește orbita permutării. Fiecare permutare pe un număr finit de elemente poate fi descompusă în permutări pe orbite disjuncte.

Părțile ciclice individuale ale unei permutări mai sunt numite și cicluri, astfel că al doilea exemplu este compus dintr-un 3-ciclu și un 1-ciclu (sau punct fix), iar al treilea este compus din două 2-cicluri și notat (1, 3) (2, 4).

Notă: Uneori termenii de permutare ciclică,^[1] sau permutare circulară^[2]^[3] sunt folosiți cu sensul de deplasare circulară, care din punct de vedere matematic este o subvariantă de permutare ciclică.

Definiție[modificare | modificare sursă]

Schema unei permutări ciclice cu două puncte fixe; un 6-ciclu și două 1-cicluri

O permutare se numește permutare ciclică dacă și numai dacă are un singur ciclu netrivial (un ciclu de lungime > 1).^[4]

De exemplu, permutarea, scrisă în notația pe două linii (în două moduri) și în notația ciclului,

{\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}=(1\ 4\ 6\ 8\ 3\ 7)(2)(5),

este un 6-ciclu; schema sa este cea din imaginea din dreapta.

Schema unei permutări fără cicluri triviale; un 8-ciclu

Unii autori restricționează definiția doar la acele permutări care constau dintr-un ciclu netrivial (adică nu sunt permise puncte fixe).^[5] De exemplu, permutarea

{\begin{pmatrix}1&2&3&4&5&6&7&8\\4&5&7&6&8&2&1&3\end{pmatrix}}={\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&5&8&3&7&1\end{pmatrix}}=(1\ 4\ 6\ 2\ 5\ 8\ 3\ 7)

este o permutare ciclică conform acestei definiții mai restrictive, în timp ce exemplul precedent nu este.

Mai formal, o permutare $\sigma$ a unei mulțimi X, privită ca o funcție bijectivă $\sigma :X\to X$ , este numit ciclu dacă acțiunea pe X a subgrupului generat de $\sigma$ are cel mult o orbită cu mai mult de un singur element.^[6] Această noțiune este folosită cel mai adesea atunci când X este o mulțime finită. Atunci cea mai mare orbită, S, este și ea finită. Fie $s_{0}$ un element oarecare din S și $s_{i}=\sigma ^{i}(s_{0})$ pentru orice $i\in \mathbf {Z}$ . Dacă S este finit, exisă un număr minim $k\geq 1$ pentru care $s_{k}=s_{0}$ . Atunci $S=\{s_{0},s_{1},\ldots ,s_{k-1}\}$ și $\sigma$ este permutarea definită de

\sigma (s_{i})=s_{i+1}

for 0 ≤ i < k

iar $\sigma (x)=x$ pentru orice element al $X\setminus S$ . Elementele care nu sunt fixe în $\sigma$ pot fi reprezentate prin

s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}

.

Un ciclu poate fi scris folosind notația compactă a ciclului $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ (în această notație nu există virgule între elemente pentru a evita confuzia cu un k-tuplu). Lungimea unui ciclu este numărul de elemente de pe cea mai mare orbită a acestuia. Un ciclu de lungime k se mai numește și k-ciclu.

Orbita unui 1-ciclu se numește punct fix al permutării, dar ca permutare fiecare 1-ciclu este permutarea identică.^[7] Când se utilizează notația compactă a ciclului, când nu este posibilă vreo confuzie 1-ciclurile sunt adesea suprimate.^[8]

Proprietăți fundamentale[modificare | modificare sursă]

Unul dintre rezultatele fundamentale ale grupurilor simetrice^⁠(d) este că orice permutare poate fi exprimată ca produs al ciclurilor disjuncte (mai precis: cicluri cu orbite disjuncte); astfel de cicluri comută între ele, iar expresia permutării este unică până la ordinea ciclurilor. (Notația ciclului nu este unică: fiecare k-ciclu poate fi scris în k moduri diferite, în funcție de alegerea lui $s_{0}$ pe orbita sa.) Multimulțimea lungimilor ciclurilor din această expresie (tipul ciclului) este prin urmare determinată în mod unic de permutare și atât semnătura, cât și clasa de conjugare^⁠(d) a permutării din grupul simetric sunt determinate de aceasta.^[9]

Numărul de k-cicluri din grupul simetric S_n este dat, pentru $1\leq k\leq n$ , prin următoarele formule echivalente:

{\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.

Un k-ciclu are semnătura (−1)^k − 1.

Inversa ciclului $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ este dată de inversarea ordinii intrărilor sale: $\sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})$ . În particular, deoarece $(a~b)=(b~a)$ , fiecare ciclu este propria sa inversă. Deoarece ciclurile disjuncte comută, inversa unui produs de cicluri disjuncte este rezultatul inversării fiecărui ciclu separat.

Transpoziții[modificare | modificare sursă]

Pentru transpunerea matricilor, vedeți matrice transpusă.

Un ciclu cu doar două elemente care schimbă locul între ele, restul fiind puncte fixe, se numește transpoziție. De exemplu, permutarea $\pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}$ care schimbă 2 cu 4.

Proprietăți[modificare | modificare sursă]

Orice permutare poate fi exprimată prin compunerea^⁠(d) (produsul) transpozițiilor — formal, acestea sunt generatorii grupului.^[10] De fapt, când mulțimea care este permutată este $(1, 2, ... , n)$ pentru un întreg oarecare n, atunci orice permutare poate fi exprimată ca produs al lui $(1~2),(2~3),(3~4),$ și așa mai departe. Aceasta se datorează faptului că o transpoziție arbitrară poate fi exprimată ca produs al transpozitiilor adiacente. Concret, se poate exprima transpoziția $(k~~l)$ unde $k<l$ prin mutarea k la l pas cu pas, apoi mutând l înapoi unde era k, care le interschimbă pe acestea două și nu face alte modificări:

(k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).

De exemplu, descompunerea unei permutări într-un produs de transpuneri se obține prin scrierea permutării ca produs al ciclurilor disjuncte și apoi divizarea iterativă a fiecărui ciclu cu lungimea 3 sau mai mare într-un produs al unei transpuneri și al unui ciclu cu lungimea mai mică cu 1:

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).

De fapt, grupul simetric este un grup Coxeter, adică este generat de elemente de ordinul 2 (transpunerile adiacente), iar toate relațiile sunt de o anumită formă.

Unul dintre principalele rezultate privind grupurile simetrice afirmă că fie toate descompunerile unei anumite permutări în transpuneri au un număr par de transpuneri, fie toate au un număr impar de transpuneri.^[11] Acest lucru permite ca paritatea unei permutări să fie un concept bine definit.

Note[modificare | modificare sursă]

^ Concurs mate-info aprilie 2016, Universitatea Babeș-Bolyai, 2016, accesat 2023-02-05
^ Cosmin Răzvan Pelea, Matematică Didactică: Syllabus, Universitatea Babeș-Bolyai, 2009, accesat 2023-02-05
^ Sortarea tablourilor unidimensionale in C++. Permutari circulare., Universitatea „Alexandru Ioan Cuza” din Iași, accesat 2023-02-05
^ en Bogart, Kenneth P. (1990), Introductory Combinatorics (ed. 2nd), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X
^ en Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall/CRC, p. 29, ISBN 978-1-58488-743-0
^ Fraleigh, 1993, p. 103
^ Rotman, 2006, p. 108
^ Sagan, 1991, p. 2
^ Rotman, 2006, p. 117, 121
^ Rotman, 2006, p. 118, prop. 2.35
^ Rotman, 2006, p. 122

Bibliografie[modificare | modificare sursă]

en Anderson, Marlow and Feil, Todd (2005), A First Course in Abstract Algebra, Chapman & Hall/CRC; 2nd edition. ISBN: 1-58488-515-7.
en Fraleigh, John (1993), A first course in abstract algebra (ed. 5th), Addison Wesley, ISBN 978-0-201-53467-2
en Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (ed. 3rd), Prentice-Hall, ISBN 978-0-13-186267-8
en Sagan, Bruce E. (1991), The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions, Wadsworth & Brooks/Cole, ISBN 978-0-534-15540-7

Portal Matematică

[1] Concurs mate-info aprilie 2016, Universitatea Babeș-Bolyai, 2016, accesat 2023-02-05

[2] Cosmin Răzvan Pelea, Matematică Didactică: Syllabus, Universitatea Babeș-Bolyai, 2009, accesat 2023-02-05

[3] Sortarea tablourilor unidimensionale in C++. Permutari circulare., Universitatea „Alexandru Ioan Cuza” din Iași, accesat 2023-02-05

[4] Bogart, Kenneth P. (1990), Introductory Combinatorics (ed. 2nd), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X

[5] Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall/CRC, p. 29, ISBN 978-1-58488-743-0

[6] Fraleigh, 1993, p. 103

[7] Rotman, 2006, p. 108

[8] Sagan, 1991, p. 2

[9] Rotman, 2006, p. 117, 121

[10] Rotman, 2006, p. 118, prop. 2.35

[11] Rotman, 2006, p. 122

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]