MathTeacherMeditații matematică
Meniu

CLASA A XI-A · ALGEBRĂ

Permutări — teorie de sinteză și exerciții rezolvate

Definiții · notații · cicluri · transpoziții · inversiuni · semn · ordin · ecuații

1Ce este o permutare?

  • O permutare a mulțimii {1,2,…,n}\{1,2,\ldots,n\} este o bijecție σ:{1,2,…,n}→{1,2,…,n}\sigma:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}.
  • Se notează σ∈Sn\sigma\in S_n, unde SnS_n este grupul simetric de grad nn.
  • Se poate scrie pe două rânduri sau ca produs de cicluri disjuncte.
  • Numărul permutărilor este ∣Sn∣=n!|S_n|=n!.
σ=(12⋯nσ(1)σ(2)⋯σ(n))\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}

Exemplu

σ=(1234523514)=(1 2 3 5 4)\sigma=\begin{pmatrix}1&2&3&4&5\\2&3&5&1&4\end{pmatrix}=(1\ 2\ 3\ 5\ 4)1→2→3→5→4→11\to2\to3\to5\to4\to1

Pe rândul de jos, fiecare valoare de la 1 la n apare exact o dată.

2Notații și convenții uzuale

  • Scriem σ(i)\sigma(i) pentru imaginea elementului ii.
  • În notația pe două rânduri, sus sunt elementele, iar jos sunt imaginile lor.
  • Compunerea se calculează de la dreapta la stânga: aplicăm mai întâi τ, apoi σ.
(στ)(i)=σ(τ(i))(\sigma\tau)(i)=\sigma(\tau(i))

Exemplu

id=(12⋯n12⋯n)\mathrm{id}=\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots&n\end{pmatrix}

Elementul neutru este identitatea: fiecare element rămâne pe loc.

3Cicluri și cicluri disjuncte

  • Un ciclu (a1 a2 … ak)(a_1\ a_2\ \ldots\ a_k) trimite a1→a2→⋯→ak→a1a_1\to a_2\to\cdots\to a_k\to a_1.
  • Descompunerea în cicluri disjuncte este unică până la ordinea ciclurilor și alegerea elementului de început în fiecare ciclu.
  • Ciclurile disjuncte comută. Punctele fixe pot fi omise.
αβ=βαpentru cicluri disjuncte\alpha\beta=\beta\alpha\quad\text{pentru cicluri disjuncte}

Exemplu

(1 2 3 5 4)=(2 3 5 4 1)(1\ 2\ 3\ 5\ 4)=(2\ 3\ 5\ 4\ 1)(1 2)(3 4)=(3 4)(1 2)(1\ 2)(3\ 4)=(3\ 4)(1\ 2)

Urmărești imaginile până revii la elementul de plecare.

4Inversa unei permutări

  • Pentru orice σ∈Sn\sigma\in S_n, există σ−1\sigma^{-1}, astfel încât σσ−1=σ−1σ=id\sigma\sigma^{-1}=\sigma^{-1}\sigma=\mathrm{id}.
  • În notația de ciclu păstrezi primul element și inversezi ordinea celorlalte.
(a1 a2 … ak)−1=(a1 ak … a2)(a_1\ a_2\ \ldots\ a_k)^{-1}=(a_1\ a_k\ \ldots\ a_2)

Exemplu

σ=(1 2 3 5 4)\sigma=(1\ 2\ 3\ 5\ 4)σ−1=(1 4 5 3 2)\sigma^{-1}=(1\ 4\ 5\ 3\ 2)σ−1=(1234541253)\sigma^{-1}=\begin{pmatrix}1&2&3&4&5\\4&1&2&5&3\end{pmatrix}

În notația pe două rânduri, schimbi rândurile între ele, apoi reordonezi coloanele după primul rând.

5Transpoziții

  • Transpoziția (i j)(i\ j) schimbă între ele două elemente și le lasă fixe pe celelalte.
  • Orice permutare se scrie ca produs de transpoziții, nu în mod unic.
  • Numărul minim de transpoziții este n−c(σ)n-c(\sigma), unde c(σ)c(\sigma) numără toate ciclurile, inclusiv punctele fixe.
(i j)=(j i),(i j)2=id(i\ j)=(j\ i),\qquad(i\ j)^2=\mathrm{id}

Exemplu

(1 2 3)=(1 3)(1 2)(1\ 2\ 3)=(1\ 3)(1\ 2)(1 2 3 5 4)=(1 4)(1 5)(1 3)(1 2)(1\ 2\ 3\ 5\ 4)=(1\ 4)(1\ 5)(1\ 3)(1\ 2)

Un ciclu de lungime k se descompune în k − 1 transpoziții.

6Inversiuni și semn

  • O inversiune este o pereche de poziții (i,j)(i,j), cu i<ji<j, pentru care σ(i)>σ(j)\sigma(i)>\sigma(j).
  • Notăm cu inv⁡(σ)\operatorname{inv}(\sigma) numărul inversiunilor.
  • Permutarea este pară dacă semnul este +1 și impară dacă semnul este −1.
sgn⁡(σ)=(−1)inv⁡(σ)∈{−1,1}\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}\in\{-1,1\}

Exemplu

σ=(1234531524)\sigma=\begin{pmatrix}1&2&3&4&5\\3&1&5&2&4\end{pmatrix}inv⁡(σ)=4,sgn⁡(σ)=+1\operatorname{inv}(\sigma)=4,\quad\operatorname{sgn}(\sigma)=+1

Inversiunile sunt (1, 2), (1, 4), (3, 4), (3, 5). Numărăm perechi de poziții, nu elemente.

7Ordinul unei permutări

  • Ordinul lui σ\sigma este cel mai mic număr m≥1m\ge1 pentru care σm=id\sigma^m=\mathrm{id}.
  • Un ciclu de lungime k are ordinul k.
  • Pentru un produs de cicluri disjuncte, ordinul este cel mai mic multiplu comun al lungimilor lor.
  • Pentru orice σ∈Sn\sigma\in S_n, ordinul lui σ\sigma divide n!n!.
ord⁡(σ)=cmmmc⁡(ℓ1,…,ℓr)\operatorname{ord}(\sigma)=\operatorname{cmmmc}(\ell_1,\ldots,\ell_r)

Exemplu

σ=(1 2 3)(4 5)\sigma=(1\ 2\ 3)(4\ 5)ord⁡(σ)=cmmmc⁡(3,2)=6\operatorname{ord}(\sigma)=\operatorname{cmmmc}(3,2)=6

Pentru calculul puterilor, reduci exponentul modulo ordinul permutării.

8Relații rapide în exerciții

  1. Ciclurile disjuncte comută.
  2. (i j) schimbă două elemente și le lasă fixe pe celelalte.
  3. Orice permutare se scrie ca produs de transpoziții.
  4. Semnul indică paritatea: pară sau impară.

9Probleme-tip · exerciții rezolvate

1Tip 1 — Scrierea ca produs de transpoziții

Scrie fiecare permutare ca produs de transpoziții.

  1. σ=(12342341)=(1 2 3 4)\sigma=\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}=(1\ 2\ 3\ 4).
  2. σ=(1234554321)=(1 5)(2 4)\sigma=\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}=(1\ 5)(2\ 4).
  3. σ=(123213)=(1 2)\sigma=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}=(1\ 2).

Rezolvare

  1. (1 2 3 4)=(1 4)(1 3)(1 2)(1\ 2\ 3\ 4)=(1\ 4)(1\ 3)(1\ 2).
  2. (1 5)(2 4)(1\ 5)(2\ 4) este deja un produs de două transpoziții; 3 rămâne fix.
  3. (1 2)(1\ 2) este deja o transpoziție.

2Tip 2 — Inversând o permutare compusă

Se consideră permutarea de mai jos. Scrie inversa în notație de cicluri, apoi calculează pătratul și ordinul.

σ=(123456634521)=(1 6)(2 3 4 5)\sigma=\begin{pmatrix}1&2&3&4&5&6\\6&3&4&5&2&1\end{pmatrix}=(1\ 6)(2\ 3\ 4\ 5)

Rezolvare

  1. σ−1=(1 6)(2 5 4 3)\sigma^{-1}=(1\ 6)(2\ 5\ 4\ 3) : transpoziția este propria inversă, iar ciclul de lungime 4 se parcurge în sens invers.
  2. σ2=(2 4)(3 5)\sigma^2=(2\ 4)(3\ 5), deoarece (1 6)2=id(1\ 6)^2=\mathrm{id}.
  3. ord⁡(σ)=cmmmc⁡(2,4)=4\operatorname{ord}(\sigma)=\operatorname{cmmmc}(2,4)=4. Pătratul are ordinul 2, fiind produsul a două transpoziții disjuncte.

3Tip 3 — Ecuații cu permutări

Determină necunoscuta din fiecare egalitate. La punctul a), x este un element; la b) și c), x este o permutare.

  1. (1234x241)=(12343241)\begin{pmatrix}1&2&3&4\\x&2&4&1\end{pmatrix}=\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}.
  2. (1 2)⋅x=(1 3 2)(1\ 2)\cdot x=(1\ 3\ 2).
  3. x⋅(1 2 3)=(1 3)x\cdot(1\ 2\ 3)=(1\ 3).

Rezolvare

  1. x=3x=3 : comparăm imaginile elementului 1.
  2. x=(1 2)(1 3 2)=(1 3)x=(1\ 2)(1\ 3\ 2)=(1\ 3). Înmulțim la stânga cu inversa lui (1 2).
  3. x=(1 3)(1 2 3)−1=(2 3)x=(1\ 3)(1\ 2\ 3)^{-1}=(2\ 3). Înmulțim la dreapta cu inversa lui (1 2 3).

4Tip 4 — Ecuații cu puteri, ordin și compoziții

Verifică egalitățile propuse și folosește ordinul sau semnul pentru a justifica răspunsul.

  1. Este σ2=id\sigma^2=\mathrm{id} pentru σ=(1 2 3 4 5)\sigma=(1\ 2\ 3\ 4\ 5)?
  2. Este σ3=id\sigma^3=\mathrm{id} pentru σ=(1 2)(3 4 5)\sigma=(1\ 2)(3\ 4\ 5)?
  3. Există o permutare xx cu x4=(1 2)x^4=(1\ 2)?

Rezolvare

  1. Nu. Ciclul are ordinul 5, iar σ2=(1 3 5 2 4)≠id\sigma^2=(1\ 3\ 5\ 2\ 4)\ne\mathrm{id}.
  2. Nu. σ3=(1 2)≠id\sigma^3=(1\ 2)\ne\mathrm{id}, deoarece ciclul de lungime 3 dispare, dar transpoziția rămâne. Ordinul lui σ este 6.
  3. Nu există soluții: sgn⁡(x4)=sgn⁡(x)4=+1\operatorname{sgn}(x^4)=\operatorname{sgn}(x)^4=+1, în timp ce sgn⁡((1 2))=−1\operatorname{sgn}((1\ 2))=-1.

5Tip 5 — Scrierea produsului de permutări

Calculează στ și τσ, scrie rezultatele în notație de cicluri și compară.

σ=(1234523154),τ=(1234515324)\sigma=\begin{pmatrix}1&2&3&4&5\\2&3&1&5&4\end{pmatrix},\quad\tau=\begin{pmatrix}1&2&3&4&5\\1&5&3&2&4\end{pmatrix}

Rezolvare

  1. Pentru στ\sigma\tau, aplicăm mai întâi τ, apoi σ. Imaginile sunt 2, 4, 1, 3, 5, deci στ=(1 2 4 3)\sigma\tau=(1\ 2\ 4\ 3).
  2. Pentru τσ\tau\sigma, aplicăm mai întâi σ, apoi τ. Imaginile sunt 5, 3, 1, 4, 2, deci τσ=(1 5 2 3)\tau\sigma=(1\ 5\ 2\ 3).
  3. Rezultă στ≠τσ\sigma\tau\ne\tau\sigma: compunerea permutărilor nu este, în general, comutativă.

De reținut

  • Permutările formează un grup cu element neutru și inversă pentru fiecare element.
  • Numărul permutărilor: ∣Sn∣=n!|S_n|=n!
  • Orice permutare se scrie ca produs de cicluri disjuncte.
  • Semnul este +1 pentru permutările pare și −1 pentru cele impare.
  • Ordinul unui ciclu este lungimea sa; pentru cicluri disjuncte folosim cmmmc.
  • n−c(σ)n-c(\sigma) este numărul minim de transpoziții, cu punctele fixe incluse în numărul ciclurilor.