Efectueaza o cautare in website!

Informaţii, definiţii, teoreme, formule, exerciţii şi probleme rezolvate din matematica de liceu.

Data publicarii: 02 Noiembrie, 2010

TEORIE

Permutari. Definitii si proprietati:

Numim permutare de gradul n orice functie f bijectiva, definita pe A si cu valori in A,

unde A = {1, 2, 3, ..., n} si nЄN*

Multimea tuturor permutarilor de gradul n (numite si substitutii de gradul n)

se noteaza Sn si, evident, cardinalul acestei multimi este egal cu n!

O permutare oarecare σ se reprezinta sugestiv sub forma tabloului:

\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}.\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}.

Compunerea permutarilor:

Fiind date permutarile

\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix},\;\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix},\; \;\tau=\begin{pmatrix}1&2&\cdots&n\\\tau(1)&\tau(2)&\cdots&\tau(n)\end{pmatrix},\;\tau=\begin{pmatrix}1&2&\cdots&n\\\tau(1)&\tau(2)&\cdots&\tau(n)\end{pmatrix},

produsul (compunerea) lor este definit prin

(στ)(k) = (σ ο τ)(k) = σ(τ(k)), k = 1, 2, ..., n 

si rezultatul este o noua permutare, care se noteaza στ sau σ ο τ si anume:

\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix} \begin{pmatrix}1&2&\cdots&n\\\tau(1)&\tau(2)&\cdots&\tau(n)\end{pmatrix}=\begin{pmatrix}1&2&\cdots&n\\\tau(1)&\tau(2)&\cdots&\tau(n)\end{pmatrix}= \begin{pmatrix}1&2&\cdots&n\\\sigma(\tau(1))&\sigma(\tau(2))&\cdots&\sigma(\tau(n))\end{pmatrix}.\begin{pmatrix}1&2&\cdots&n\\\sigma(\tau(1))&\sigma(\tau(2))&\cdots&\sigma(\tau(n))\end{pmatrix}.

Grupul substitutiilor de gradul n:

Se verifica usor ca multimea substitutiilor de gradul n, impreuna cu operatia de

compunere, formeaza un grup (necomutativ), in care elementul neutru este

permutarea identica, anume

e=\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots&n\end{pmatrix},e=\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots&n\end{pmatrix},

iar simetricul {\sigma}^{-1}{\sigma}^{-1} este inversa permutarii σ,

(toate permutarile sunt inversabile, fiind functii bijective !)

Transpozitii:

Fie i si j, doua numere din multimea {1, 2, ... , n}, unde i < j; permutarea  

\tau_{ij}=\begin{pmatrix}1&2&\cdots&i&\cdots&j&\cdots&n\\1&2&\cdots&j&\cdots&i&\cdots&n\end{pmatrix}\tau_{ij}=\begin{pmatrix}1&2&\cdots&i&\cdots&j&\cdots&n\\1&2&\cdots&j&\cdots&i&\cdots&n\end{pmatrix}

(in linia a doua doar i si j si-au schimbat locurile) se numeste transpozitie de gradul n

si se noteaza sub forma (ij).

Se verifica usor ca:

(ij) = (ji), (ij)² = e,

(ij)^{-1}=(ij).(ij)^{-1}=(ij).

Teorema:

Orice permutare de gradul n se poate scrie ca un produs de transpozitii din Sn.

Inversiuni:

Semnul unei permutari. Definitii si proprietati:

Fie o permutare σЄSn, de forma

\sigma=\begin{pmatrix}1&2&\cdots&i&\cdots&j&\cdots&n\\\sigma{(1)}&\sigma{(2)}&\cdots&\sigma{(i)}&\cdots&\sigma{(j)}&\cdots&\sigma{(n)}\end{pmatrix}.\sigma=\begin{pmatrix}1&2&\cdots&i&\cdots&j&\cdots&n\\\sigma{(1)}&\sigma{(2)}&\cdots&\sigma{(i)}&\cdots&\sigma{(j)}&\cdots&\sigma{(n)}\end{pmatrix}.

Perechea (ij) se numeste inversiune a permutarii σ daca σ(i) > σ(j).

Numarul de inversiuni a permutarii σ se noteaza cu m(σ), iar numarul 

ε(σ) = (-1)^{m(\sigma)},(-1)^{m(\sigma)},

se numeste signatura (sau semnul) permutarii σ.

Permutarea σ se numeste permutare para sau impara, dupa cum ε(σ) = ±1.

Teorema:

Fie o permutare σЄSn. Atunci:

1)\;\epsilon(\sigma)=\prod_{{1}\le{i}\le{j}}{\frac{\sigma(j)-\sigma(i)}{j-i}};1)\;\epsilon(\sigma)=\prod_{{1}\le{i}\le{j}}{\frac{\sigma(j)-\sigma(i)}{j-i}};

2)\;\epsilon(\sigma\tau)={\epsilon(\sigma)}\cdot{\epsilon(\tau)},\;\forall{\sigma,\tau}\in{S_n}2)\;\epsilon(\sigma\tau)={\epsilon(\sigma)}\cdot{\epsilon(\tau)},\;\forall{\sigma,\tau}\in{S_n}

(semnul produsului este egal cu produsul semnelor);

3)\;\epsilon({\sigma}^{-1})=\epsilon(\sigma),\;3)\;\epsilon({\sigma}^{-1})=\epsilon(\sigma),\;'\forall{\sigma}\in{S_n}

(o permutare si inversa sa au acelasi semn).

Observatii:

Fie σ,τЄSn.

  • Permutarea στ este para sau impara, dupa cum cele doua permutari au acelasi semn, sau semne diferite. 
  • Orice permutare din Sn se poate scrie sub forma de produs de transpozitii, in numar par sau impar de factori, dupa cum permutarea este para sau impara.
  • Numarul N de permutari (de gradul n) pare este egal cu numarul de permutari impare si N = n!/2, pentru orice n natural, mai mare sau egal cu 2.

Adăugaţi un comentariu

Adăugaţi un comentariu
Introdu codul din imagine

Răspunsuri şi comentarii

Până acum, niciun comentariu nu a fost adăugat.

 

CATEGORII :


Arhiva blog-ului

 

 
Developed by Hagau Ioan