Transcript: Noțiunea de permutare

Transmiterea informațiilor secrete a preocupat dintotdeauna omenirea.
Fiecare dintre noi a dorit, la un moment dat, să transmite mesaje pe care să le poată descifra doar anumite persoane.
Ce spuneți de următorul mesaj? Ce credeți că transmite?
Dacă folosim codul lui Cezar, care este una dintre cele mai simple și mai cunoscute tehnici decriptale,
fiecare litere din textul inițial îi corespunde o literă din alfabet decalată cu e în poziții, în cazul acesta cu 3.
Pentru decriptare folosim linia a doua a acestui tabel în corespondență cu linia întâi a acestui tabel,
iar pentru criptare folosim linia a doua în corespondență cu linia a treia.
Astfel, literei L din text îi corespunde litera I, literei P din text îi corespunde litera M și așa mai departe.
Ei, ce spuneți? Ați reușit să decodificați mesajul?
Cu câte poziții este decalat cifrul din imagine? Este vorba tot de cifrul lui Cezar.
Vă aștept răspunsurile în secțiunea comentarii.
Codificarea mesajelor are la bază o noțiune importantă și anume noțiunea de funcție bijectivă.
Cu ajutorul acesteia vom defini în această secțiune noțiunea de permutare.
Pentru a înțelege noțiunea de permutare avem nevoie să știm ce este o funcție,
ce înțelegem prin funcție bijectivă, ce reprezintă o mulțime ordonată
și ce înseamnă noțiunea de cardinal al unei mulțimi finite.
Ne reamintim că o funcție este o corespondență sau un procedeu
prin care fiecărui element dintr-o mulțime A, numită domeniu,
îi corespunde în mod unic un element dintr-o mulțime B, numită codomeniu.
Numim funcție bijectivă o funcție care este injectivă și sujectivă.
Astfel, cu alte cuvinte, două elemente distincte din domeniu au imagini diferite în codomeniu
și toate elementele din codomeniu sunt imagini ale unor elemente din domeniu.
Prin mulțime ordonată înțelegem o mulțime infinită A însestrată cu o ordine binedeterminată F
de dispunere a elementelor sale.
F este o funcție bijectivă definită pe mulțimea formată din elementele 1, 2, 3, respectiv N,
cu valori în A, unde A are N elemente.
Un exemplu de mulțime ordonată este mulțimea formată din elementele 1, 2, 3,
unde pe primul loc am așezat elementul 1, pe al doilea loc am așezat elementul 2
și pe al treilea loc am așezat elementul 3.
De asemenea, o altă mulțime ordonată este și mulțimea formată din elementele 3, 1, 2,
unde pe primul loc am așezat elementul 3, pe al doilea elementul 1 și pe al treilea elementul 2.
Un alt exemplu este și mulțimea formată din elementele A, C, D, B,
unde pe primul loc se află litera A, pe al doilea loc litera C, pe al treilea loc litera D
și pe al patulea loc litera B.
Atenție! Mulțimea ordonată nu se referă la așezarea în ordine crescătoare,
respectiv descrescătoare, a elementelor unei mulțimi.
Prin cardinalul unei mulțimi, înțelegem numărul de elemente al acelei mulțimi.
O problemă de numărare desîntâlnită este aceea de a determina câte numere de patru cifre distincte
se pot forma cu elemente din mulțimea 1, 2, 3, 4.
Un număr de patru cifre distincte se poate reprezenta sub forma A, B, C, D,
iar un exemplu de număr care satisface condițiile este 3124,
adică o mulțime ordonată formată din elementele acestei mulțimi.
A determina numărul acestor numere de patru cifre distincte
revine la a determina numărul funcțiilor bijective construite de la mulțimea formată din elementele A, B, C, D
cu valori în mulțimea formată din elementele 1, 2, 3, 4.
Funcții care trebuie să fie bijective deoarece cifrele trebuie să fie distincte.
Pentru exemplul dat, observăm corespondența.
F de A este egal cu 3, F de B este egal cu 1, F de C este egal cu 2, iar F de D este egal cu 4.
Putem reprezenta această funcție în forma următoare.
Lui A trei, lui B îi corespunde 1, lui C îi corespunde 2, iar lui D îi corespunde 4.
Dacă vom înlocui cifrele A, B, C, D cu poziția lor în cadrul numărului, putem obține următoarea reprezentare.
Cifra A ocupa poziția 1 în cadrul numărului și atunci lui 1 îi facem să-i corespundă 3.
B ocupa poziția 2, deci lui 2 o să-i corespundă 1.
C ocupa poziția 3, ceea ce înseamnă că lui 3 îi vom corespunde 2.
Evident, lui 4 îi corespunde 4.
În concluzie, numărul acestor numere este egal cu numărul funcțiilor bijective
ce se pot construi de la o mulțime cu 4 elemente la o mulțime cu 4 elemente,
adică 4 factorial numere, 1 înmulțit cu 2, înmulțit cu 3, înmulțit cu 4, 24 de numere.
Generalizând, putem considera mulțimea formată din elementele A1, A2, An,
unde n este un număr natural nenul.
Putem defini astfel permutarea ca fiind oricare mulțime ordonată formată cu elementele mulțimii A.
Fiind o mulțime ordonată, o permutare are următoarea expresie,
a i 1, a i 2, a i n,
unde i 1, i 2, i n
aparțin mulțimii formate din elementele 1, 2, i n
și oricare doi indici dintre acestea trebuie să fie diferiți.
Această ordonare a elementelor mulțimii A presupune, de fapt, definirea unei funcții bijective F
de la mulțimea A cu valori în mulțimea A,
prin relația FDAK egal cu A indice IK.
Iar acest K care intervine este un număr din mulțimea numelor naturale de la 1 până la n.
Funcție care poate fi reprezentată și sub forma următorului tablou.
Lui A1 îi corespunde a i 1,
lui A2 îi corespunde a i 2,
iar lui AN îi corespunde a i n.
În același timp se observă și următoarea corespundență.
Lui 1 îi corespunde i 1,
lui 2 îi corespunde i 2,
iar lui N îi corespunde i n.
Adică o funcție pe care o putem nota cu sigma
definită de la mulțimea numelor naturale 1, 2, n
cu valori în aceeași mulțime
descrisă de relația sigmaDK egal cu IK
iar K este un element al acestei mulțimii.
Funcție care la rândul ei poate fi scrisă sub următoarea formă.
Lui 1 îi corespunde i 1,
lui 2 îi corespunde i 2,
lui N îi corespunde i n.
Astfel, această permutare este bine descrisă
de această funcție bijectivă.
Din acest motiv, studiul permutărilor mulțimilor finite A
cu N elemente se poate face prin intermediul funcțiilor bijective sigma.
Putem defini acum permutarea de gradient
a mulțimii A formată din elementele 1, 2, N
ca fiind orice funcție bijectivă sigma
definită pe mulțimea A cu valori în mulțimea A.
Mulțimea permutărilor de gradient
se notează cu S indice N
iar elementele sale se notează cu litere grecești
α, β, γ, δ și așa mai departe.
Cardinalul lui SN
este egal cu N factorial,
adică este numărul permutărilor
unei mulțime ordonate cu N elemente.
Iar o permutare sigma se notează în acest mod.
Lui 1 îi corespunde sigma de 1, lui 2 îi corespunde sigma de 2
iar lui N îi corespunde sigma de N.
Să considerăm acum câteva situații
pentru N egal cu 1
Mulțimea A este formată dintr-un singur element
și atunci mulțimea permutărilor
va fi formată dintr-un singur element
permutarea în care lui 1 îi corespunde 1
iar S1 este egal cu 1 factorial, adică 1
Pentru N egal cu 2
mulțimea A va conține două elemente
și anume 1, 2
iar S2 va conține două permutări
Lui 1 îi corespunde 1, lui 2 îi corespunde 2
Cardinalul lui S2
este egal cu 2 factorial, adică 2
În cazul în care N este egal cu 3
mulțimea A este formată din elementele
1, 2, 3
iar S3 este formată din 6 permutări
descrise în felul următor
Permutarea care lasă neschimbat fiecare element
Acum lui 1 să-i corespundă tot 1
dar lui 2 îi corespunde 3
iar lui 3 îi corespunde 2
Lui 1 să-i corespundă tot 2
lui 2 să-i corespundă 1
iar lui 3 să-i corespundă 3
Lui 1 îi corespunde tot 2
lui 2 îi corespunde 3
iar lui 3 îi corespunde 1
Lui 1 îi corespunde 3
iar lui 3 îi corespunde 1
Cardinalul lui S3, așa cum spuneam, este
3 factorial, adică 6
Printre permutările de gradient există două permutări particulare
și anume o permutare care asocia
fiecărui element elementul însuși
pentru orice ca număr
din mulțimea formată din elementele 1, 2, n
Această permutare
reprezintă permutarea identică
notată astfel. Lui 1 îi corespunde 1
lui 2 îi corespunde 2 iar lui n îi corespunde n
și spuneam că se numește permutare
identică
Al doilea exemplu este
permutarea care asocia fiecărui element
k, elementul însuși
în situația în care acesta este diferit de i
respectiv este diferit de j
și elementului k îi asocia elementul i
dacă acest k este egal cu j
și îi asocia elementul j dacă acest k
este egal cu i. Permutarea obținută
se notează cu delta ij
și are următoarea structură. Lui 1 îi corespunde 1
lui 2 îi corespunde 2, lui i îi va corespunde
j, lui k îi va corespunde
k, lui j îi va corespunde
i, lui n îi corespunde
n. Dacă ar fi să considerăm transpoziția
1-3 în mulțimea permutărilor de ordin
3, delta 1-3 ar avea următoarea
formă. Lui 1 îi corespunde 3, lui
2 îi corespunde 2, iar lui 3 îi corespunde
1. O astfel de permutare poartă numele
de transpoziție și o mai puteți întâlni
și notată în acest mod.
În cazul acesta este transpoziția 1-3.
Observăm că transpoziția ij este
aceeași, este egală cu transpoziția ji.
În următorul videoclip vom vorbi despre
operațiile cu permutări, respectiv
proprietățile acestor operații.
Cifrul sau codul lui Cezar este o permutare
de ordin 26. Dacă doriți să transmiteți un mesaj
utilizând codul lui Cezar, dar cu pasul 2,
vă aștept în secțiunea comentarii.