Operații cu permutări- aplicații

256 vizualizări · 9 voturi

Concepte: Combinări, aranjamente, permutări

Test: Test de evaluare - operații cu permutăr...

Raportează o problemă

Descrie pe scurt problema sau sugestia ta. Vom primi automat și pagina de pe care scrii.

Mulțumim!

Mesajul tău a ajuns la noi. Vom analiza problema cât de curând.

Definiție. Compunerea sau produsul a două permutări de grad n este tot o permutare de grad n definită astfel

$(σ \circ δ) (k) = σ (δ (k)), \forall k \in A, σ, δ \in S_{n}, A = \{1, 2, . . ., n\}$

sau altfel scris

$σ δ = (\begin{matrix} 1 & 2 & . . . & n \\ σ (δ (1)) & σ (δ (2)) & . . . & σ (δ (n)) \end{matrix})$

Proprietăți ale compunerii permutărilor de grad n

1. Proprietatea de asociativitate

$(σ δ) θ = σ (δ θ), \forall σ, δ, θ \in S_{n}$

2. Proprietatea elementului neutru

$σ e = e σ = σ, \forall σ \in S_{n}$

3. Proprietatea elementului invers

$\forall σ \in S_{n}, \exists σ^{- 1} \in S_{n} a s t f e l î n c â t σ σ^{- 1} = σ^{- 1} σ = e$

Puterea unei permutări de grad n

$σ^{0} = e, σ^{1} = σ, σ^{2} = σ σ, σ^{3} = σ σ σ, . . ., σ^{n} = \underset{}{\underset{n}{\underset{⏟}{σ σ . . . σ}}, n \in ℕ, σ \in S_{n}}$

Proprietăți ale puterilor permutărilor de grad n

$σ^{m} σ^{n} = σ^{m + n}, \forall m, n \in ℕ, \forall σ \in S_{n}$

${(σ^{m})}^{n} = σ^{m n}, \forall m, n \in ℕ, \forall σ \in S_{n}$

Deschide pagina de teorie: Operații cu permutări- aplicații →

Pentru fixarea noțiunilor legate de operațiile cu permutări, ne propunem în acest videoclip rezolvarea următoarei probleme.

Date 3 permutări sigma, delta, teta de grad 4, dorim să rezolvăm ecuațiile sigma ori x egal cu delta, x ori sigma egal cu delta,

sigma ori x ori delta egal cu teta, să calculăm puterea 100, respectiv puterea 2017 a permutării sigma

și să determinăm cardinalul mulțimii m, formată din puterile lui sigma.

Să rezolvăm pentru început prima ecuație.

Sigma ori x este egal cu delta, cu mod ce permutare este inversabilă.

Putem înmulți la stânga aceste egalități cu inversa permutării sigma, obținând egalitatea sigma la minus 1 ori sigma ori x este egal cu sigma la minus 1 ori delta.

Cum sigma la minus 1 ori sigma era permutarea identică, avem egalitatea, e ori x egal cu sigma la minus 1 ori delta, dar permutarea ei era permutarea identică,

adică elementul neutru pentru produsul permutărilor, x este egal cu sigma la minus 1 ori delta.

Să înlocuim acum pe sigma la minus 1, respectiv pe delta.

Sigma la minus 1 este permutarea 1, 2, 3, 4, lui 1-ui corespunde 2, lui 2-ui corespunde 4, lui 3-ui corespunde 1, iar lui 4-ui corespunde 3, iar permutarea delta este 1, 2, 3, 4, 1, 3, 4, 2.

Produsul acestor două permutări este permutarea 1, 2, 3, 4, lui 1-ui corespunde 1, lui 1-ui corespunde 2, lui 2-ui corespunde 3, lui 3-ui corespunde 1, lui 3-ui corespunde 4, lui 4-ui corespunde 3, lui 4-ui corespunde 2, iar lui 2-ui corespunde 4.

Pentru cea de-a doua ecuație, procedăm în mod similar.

Pornim de la ecuația x ori sigma egal cu delta.

De data aceasta vom înmulți la dreapta cu permutarea inversa a lui sigma.

Obținând egalitatea, x ori sigma ori sigma la minus 1 este egal cu delta ori sigma la minus 1.

Permutarea sigma ori sigma la minus 1 este permutarea identică, așadar x ori e egal cu delta ori sigma la minus 1, adică x este egal cu delta ori sigma la minus 1.

Înlocuind, obținem permutările 1, 2, 3, 4, 1, 3, 4, 2, iar permutarea inversa a lui sigma 1, 2, 3, 4, 2, 4, 1, 3.

Rezultatul este permutarea 1, 2, 3, 4, lui 1-ui corespunde 2, lui 2-ui corespunde 3, lui 2-ui corespunde 4, lui 4-ui corespunde 2, lui 3-ui corespunde 1, lui 1-ui corespunde 1, iar lui 4-ui corespunde 3, iar 3 are corespondent 4.

Pentru cea de a treia ecuație, sigma x ori delta este egal cu theta, vom înmulți la stânga cu sigma la minus 1, iar la dreapta cu delta la minus 1.

Vom obține ecuația sigma la minus 1 ori sigma ori x ori delta ori delta la minus 1 este egal cu sigma la minus 1 ori theta ori delta la minus 1.

Sigma la minus 1 ori sigma este permutarea identică, delta ori delta la minus 1 este tot permutarea identică, adică e ori x ori e este egal cu sigma la minus 1 ori theta ori delta la minus 1, adică x este egal cu permutarea 1, 2, 3, 4, 2, 4, 1, 3

ori permutarea theta, adică permutarea 1, 2, 3, 4, 4, 1, 2, 3, și ori permutarea delta la minus 1, pe care o vom calcula acum, 1, 2, 3, 4, lui 1-ui corespunde 1, lui 2-ui corespunde 4, lui 3-ui corespunde 2, iar lui 4-ui corespunde 3.

Obținem permutarea 1, 2, 3, 4, lui 1-ui corespunde 1, lui 1-ui corespunde 4, iar lui 4-ui corespunde 3, lui 2-ui corespunde 4, lui 4-ui corespunde 3, iar lui 3-ui corespunde 1, lui 3-ui corespunde 2, lui 2-ui corespunde 1, lui 1-ui corespunde 2, lui 4-ui corespunde 3, lui 3-ui corespunde 2, iar lui 2-ui corespunde 4.

Ne propunem acum să calculăm sigma la puterea 100, respectiv sigma la puterea 2017.

Să calculăm pentru început câteva puteri ale lui sigma, și anume, sigma la puterea 2-a este egal cu

1, 2, 3, 4, 3, 1, 4, 2, 1, 2, 3, 4, 3, 1, 4, 2, adică permutarea 1, 2, 3, 4, lui 1-ui corespunde 3, lui 3-ui corespunde 4,

lui 2-ui corespunde 1, lui 1-ui corespunde 3, lui 3-ui corespunde 4, lui 4-ui corespunde 2, lui 4-ui corespunde 2, iar lui 2-ui corespunde 1.

Sigma la puterea 3-ea reprezintă sigma ori sigma la pătrat, adică permutarea 1, 2, 3, 4, 3, 1, 4, 2,

1, 2, 3, 4, 4, 3, 2, 1, egal cu permutarea 1, 2, 3, 4, lui 1-ui corespunde 4, lui 4-ui corespunde 2, lui 2-ui corespunde 3, iar lui 3-ui corespunde 4,

lui 3-ui corespunde 2, lui 2-ui corespunde 1, lui 4-ui corespunde 1, iar lui 1-ui corespunde 3. Sigma la puterea 4-ea reprezintă sigma ori sigma la puterea 3-ea, adică permutarea 1, 2, 3, 4, 3, 1, 4, 2,

înmulți cu permutarea 1, 2, 3, 4, 2, 4, 1, 3. Egal cu permutarea 1, 2, 3, 4, lui 1-ui corespunde 2, lui 2-ui corespunde 1, lui 2-ui corespunde 4, lui 4-ui corespunde 2,

lui 3-ui corespunde 1, lui 1-ui corespunde 3, lui 4-ui corespunde 3, lui 3-ui corespunde 4. Observăm că am obținut permutarea identică. Așadar, sigma la puterea 5-a

va fi sigma ori sigma la 4-a, adică sigma. Sigma la puterea 6-a va fi sigma ori sigma la 5-a, adică sigma ori sigma, sigma pătrat. Sigma la puterea 7-a

va fi sigma ori sigma la 6-a, sigma ori sigma la pătrat, sigma la puterea 3-a. Iar sigma la 8-a este sigma la 4-a totul la a doua, adică este permutarea

identică. Observăm că puterile lui sigma se repetă din 4 în 4. Sigma la puterea 4-a este egal cu sigma la puterea 8-a, sigma la puterea 5-a este egal cu sigma, sigma la puterea 6-a este

egal cu sigma la puterea 2-a, iar sigma la puterea 7-a este egal cu sigma la puterea 3-a. Pentru calculul lui sigma la puterea 100, îl vom împărți pe 100 la 4, obținând câtul 25. Sigma la puterea 100

îl putem scrie astfel, ca sigma la puterea 4-a totul la puterea 25, adică permutarea identică la puterea 25, adică permutarea identică. Pentru calculul lui sigma la puterea 2017, îl vom împărți pe

sigma la puterea 2017 la 4, obținând câtul 504, dar restul 1. Pe sigma la puterea 2017, îl vom scrie ca sigma la puterea 504 ori 4 plus 1. Această putere o putem scrie ca produsul a două puteri cu baza sigma, adică sigma la puterea 504 ori 4 ori sigma la puterea 1,

iar această putere o putem scrie ca sigma la 4-a totul la puterea 504 ori sigma la puterea 1. Obținem așadar e ori sigma, adică sigma.

Să determinăm acum cardinalul mulțimii m formată din elementele e, sigma, sigma la pătrat, sigma la puterea n. Fie sigma la puterea n o permutare care aparține aceste mulțimii. n este un număr natural.

Conform teoremia împărțirii cu rest, pe n îl putem scrie ca 4 ori q plus r de împărțitul, egal cu împărțitorul, oricâtul plus restul, unde restul trebuie să fie mai mic decât împărțitorul, adică mai mic decât 4.

Atunci, sigma la puterea n poate fi scris astfel, sigma la puterea 4 ori q plus r. Această permutare vom scrie ca produsul a două permutări cu aceeași bază, adică sigma la puterea 4q îmulțit cu sigma la puterea r,

sau sigma la puterea 4, totul la puterea q, ori sigma la puterea r. Dar sigma la puterea 4 am văzut că este permutarea identică, adică e la puterea q ori sigma la puterea r, adică sigma la puterea r.

Cum r este un număr mai mic decât 4, r poate fi unul din numerele 0, 1, 2 sau 3.

În concluzie, sigma la puterea r nu poate fi decât permutarea identică sigma, sigma la puterea a doua, respectiv sigma la puterea a treia.

Am arătat astfel că sigma la puterea n nu poate fi decât unul din cele patru elemente, permutarea identică sigma, sigma la puterea a doua sau sigma la puterea a treia.

Adică mulțimea m este formată doar din patru elemente distinte, permutarea identică sigma, sigma la a doua, respectiv sigma la a treia.

Obținând astfel, cardinalul acestei mulțimi m este egal cu 4.

Deschide transcriptul lecției: Operații cu permutări- aplicații →

Anterior

Operații cu permutări

Continuă cu testul

Test de evaluare - operații cu permutări

Comentarii (0)

Autentifică-te pentru a lăsa un comentariu.

Niciun comentariu încă.

Alte lecții din: Operații cu permutări

Operații cu permutări

Operații cu permutări