Permutare

Fiecare dintre cele șase linii este o permutare diferită de trei sfere distincte

O permutare este un mod de a ordona obiecte distincte succesiv , ca în anagrama unui cuvânt. În termeni matematici , o permutare a unui set $X$ ${\ displaystyle X}$ $X$ este definit ca o funcție bijectivă $p\colon X\rightarrow X$ ${\ displaystyle p \ colon X \ rightarrow X}$ ${\ displaystyle p \ colon X \ rightarrow X}$ .

Enumerați și numărați permutările

Numărul de permutări ale $n$ ${\ displaystyle n}$ $n$ obiecte este egal cu factorialul de $n$ ${\ displaystyle n}$ $n$ :

n!=n\cdot (n-1)\cdot (n-2)\cdots 1,

{\ displaystyle n! = n \ cdot (n-1) \ cdot (n-2) \ cdots 1,}

{\ displaystyle n! = n \ cdot (n-1) \ cdot (n-2) \ cdots 1,}

de fapt există $n$ ${\ displaystyle n}$ $n$ modalități de alegere a obiectului care ocupă prima poziție, pentru fiecare dintre ele există $n-1$ ${\ displaystyle n-1}$ $n-1$ modalități de a alege obiectul care ocupă a doua poziție, apoi pentru fiecare pereche de obiecte fixate în primele două poziții există $n-2$ ${\ displaystyle n-2}$ $n-2$ modalități de alegere a obiectului în a treia poziție și așa mai departe, până când toate pozițiile sunt ocupate.

De exemplu, posibilele permutări ale seriei de patru litere „ABCD” sunt 24 și apar ca:

ABCD BACD CABD DABC

ABDC BADC CADB DACB

ACBD BCAD CBAD DBAC

ACDB BCDA CBDA DBCA

ADBC BDAC CDAB DCAB

ADCB BDCA CDBA DCBA

Seturi cu repetări

Dacă există elemente repetate în setul de pornire, unele permutări dau aceeași secvență. De exemplu, permutările din seria de patru litere "ABAB" dau doar 6 rezultate distincte:

AABB ABAB ABBA

BBAA BABA BAAB

În general, dacă setul este alcătuit din $n$ ${\ displaystyle n}$ $n$ obiecte, dintre care $n_{1}$ ${\ displaystyle n_ {1}}$ $n_ {1}$ Sunt unic, $n_{2}$ ${\ displaystyle n_ {2}}$ $n_ {2}$ de alt tip etc. până la $n_{k}$ ${\ displaystyle n_ {k}}$ $n_ {k}$ , cu $n=n_{1}+n_{2}+\cdots +n_{k}$ ${\ displaystyle n = n_ {1} + n_ {2} + \ cdots + n_ {k}}$ $n = n_ {1} + n_ {2} + \ cdots + n_ {k}$ , numărul rezultatelor distincte este

{n \choose n_{1},\dots ,n_{k}}={\frac {n!}{n_{1}!\cdots n_{k}!}}

{\ displaystyle {n \ choose n_ {1}, \ dots, n_ {k}} = {\ frac {n!} {n_ {1}! \ cdots n_ {k}!}}}

{n \ alege n_ {1}, \ dots, n_ {k}} = {\ frac {n!} {n_ {1}! \ cdots n_ {k}!}}

care se numește coeficientul multinomial .

În exemplul prezentat, $n=4$ ${\ displaystyle n = 4}$ $n = 4$ Și $n_{1}=n_{2}=2$ ${\ displaystyle n_ {1} = n_ {2} = 2}$ $n_ {1} = n_ {2} = 2$ , și astfel obținem

{\frac {4!}{2!\,2!}}={\frac {24}{4}}=6.

{\ displaystyle {\ frac {4!} {2! \, 2!}} = {\ frac {24} {4}} = 6.}

{\ displaystyle {\ frac {4!} {2! \, 2!}} = {\ frac {24} {4}} = 6.}

Demonstrație

Puneți toate permutările simple ale $n$ ${\ displaystyle n}$ $n$ obiecte în care numai $k$ ${\ displaystyle k}$ $k$ se repetă tratându-le ca fiind diferite între ele astfel încât să aibă permutările literelor care nu sunt egale pe linii și permutările literelor egale pe coloane. Procedând în acest fel pe fiecare rând vor exista aceleași permutări, deci dacă calculăm produsul numărului de rânduri cu numărul de coloane obținem numărul de permutări:

\mathrm {righe} \times \mathrm {colonne} =P_{n}.

{\ displaystyle \ mathrm {rânduri} \ times \ mathrm {coloane} = P_ {n}.}

{\ displaystyle \ mathrm {rânduri} \ times \ mathrm {coloane} = P_ {n}.}

Prin urmare, vor exista atâtea rânduri cât permutări ale literelor repetate și la fel de multe coloane câte permutări cu repetare

k!\cdot P_{n;k}=P_{n}\quad \to \quad P_{n;k}={\frac {P_{n}}{k!}}.

{\ displaystyle k! \ cdot P_ {n; k} = P_ {n} \ quad \ to \ quad P_ {n; k} = {\ frac {P_ {n}} {k!}}.}

{\ displaystyle k! \ cdot P_ {n; k} = P_ {n} \ quad \ to \ quad P_ {n; k} = {\ frac {P_ {n}} {k!}}.}

Dacă obiectele care se repetă sunt de mai multe tipuri, atunci elementele unui tip sunt eliminate mai întâi tratându-le ca fiind diferite de cele de celălalt tip. Apoi aplicăm formula de mai sus obținând permutările simple ale obiectelor inclusiv cele de tipul rămas pe care va fi posibil să aplicăm din nou formula obținând permutările cu repetarea căutată. Generalizarea formulei se obține

P_{n;k_{1},k_{2},\cdots ,k_{n}}={\frac {P_{n}}{k_{1}!k_{2}!\cdots k_{n}!}}={n \choose k_{1},k_{2},\cdots ,k_{n}}.

{\ displaystyle P_ {n; k_ {1}, k_ {2}, \ cdots, k_ {n}} = {\ frac {P_ {n}} {k_ {1}! k_ {2}! \ cdots k_ { n}!}} = {n \ alege k_ {1}, k_ {2}, \ cdots, k_ {n}}.}

{\ displaystyle P_ {n; k_ {1}, k_ {2}, \ cdots, k_ {n}} = {\ frac {P_ {n}} {k_ {1}! k_ {2}! \ cdots k_ { n}!}} = {n \ alege k_ {1}, k_ {2}, \ cdots, k_ {n}}.}

Compoziţie

Același subiect în detaliu: Grup simetric .

O permutare este o funcție bijectivă $p\colon X\to X$ ${\ displaystyle p \ colon X \ to X}$ ${\ displaystyle p \ colon X \ to X}$ . Două permutări $p$ ${\ displaystyle p}$ $p$ Și $p^{'}$ ${\ displaystyle p '}$ $p '$ pot fi deci compuse și rezultatul este încă o permutare. Întregul $S(X)$ ${\ displaystyle S (X)}$ $S X)$ a permutărilor de $X$ ${\ displaystyle X}$ $X$ cu operația de compoziție formează un grup , numit grup simetric . Elementul neutru este permutarea care lasă toate elementele fixe.

Cicluri

Este $a_{1},\ldots ,a_{n}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n}}$ $a_ {1}, \ ldots, a_ {n}$ o succesiune de elemente distincte ale $X$ ${\ displaystyle X}$ $X$ . Ciclul

p=(a_{1},\ldots ,a_{n})

{\ displaystyle p = (a_ {1}, \ ldots, a_ {n})}

p = (a_ {1}, \ ldots, a_ {n})

permutarea este cea care le deplasează pe toate înainte cu una $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ și îi menține pe ceilalți fixați. Mai formal este definit astfel:

p(a_{1})=a_{2},p(a_{2})=a_{3},\ldots ,p(a_{n})=a_{1};

{\ displaystyle p (a_ {1}) = a_ {2}, p (a_ {2}) = a_ {3}, \ ldots, p (a_ {n}) = a_ {1};}

{\ displaystyle p (a_ {1}) = a_ {2}, p (a_ {2}) = a_ {3}, \ ldots, p (a_ {n}) = a_ {1};}

p(a)=a

{\ displaystyle p (a) = a}

{\ displaystyle p (a) = a}

pentru ceilalti

la .

{\ displaystyle a.}

{\ displaystyle a.}

Ordinea ciclului este numărul $n$ ${\ displaystyle n}$ $n$ . O transpunere este un ciclu $(a,b)$ ${\ displaystyle (a, b)}$ $(a, b)$ de ordinul 2: constă pur și simplu în schimbul elementelor $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ , lăsând toate celelalte fixate.

Două cicluri $(a_{1},\ldots ,a_{n})$ ${\ displaystyle (a_ {1}, \ ldots, a_ {n})}$ $(a_ {1}, \ ldots, a_ {n})$ Și $(b_{1},\ldots ,b_{m})$ ${\ displaystyle (b_ {1}, \ ldots, b_ {m})}$ $(b_ {1}, \ ldots, b_ {m})$ sunt independenți dacă $a_{i}\neq b_{j}$ ${\ displaystyle a_ {i} \ neq b_ {j}}$ $a_ {i} \ neq b_ {j}$ pentru fiecare $the$ ${\ displaystyle i}$ $the$ Și $j$ ${\ displaystyle j}$ $j$ . Două cicluri independente $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ se schimbă, adică $a*b=b*a$ ${\ displaystyle a * b = b * a}$ $a * b = b * a$ . Importanța ciclurilor constă în următoarea teoremă: Fiecare permutare este scrisă în mod unic ca produs al ciclurilor independente.

Deoarece ciclurile independente navighează, unicitatea trebuie înțeleasă dacă nu se schimbă ordinea ciclurilor.

În cele din urmă, observăm că notațiile $(a,b,c)$ ${\ displaystyle (a, b, c)}$ $(a, b, c)$ Și $(b,c,a)$ ${\ displaystyle (b, c, a)}$ ${\ displaystyle (b, c, a)}$ definiți același ciclu, în timp ce $(a,b,c)$ ${\ displaystyle (a, b, c)}$ $(a, b, c)$ Și $(b,a,c)$ ${\ displaystyle (b, a, c)}$ ${\ displaystyle (b, a, c)}$ sunt cicluri diferite.

Notaţie

Există două notații pentru scrierea unei permutări. De exemplu, luați în considerare o permutare a setului $\{1,2,3,4,5\}.$ ${\ displaystyle \ {1,2,3,4,5 \}.}$ ${\ displaystyle \ {1,2,3,4,5 \}.}$ Puteți scrie poziția în care este mutat sub fiecare număr:

{\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}.

{\ displaystyle {\ begin {bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {bmatrix}}.}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {bmatrix}}.}

Alternativ, aceeași permutare poate fi codificată folosind teorema enunțată mai sus, scriind-o ca produs al ciclurilor. În cazul de exemplu obținem $(125)(34).$ ${\ displaystyle (125) (34).}$ ${\ displaystyle (125) (34).}$

Cu notația ciclică se pot compune cu ușurință două permutări: de exemplu $(125)(34)$ ${\ displaystyle (125) (34)}$ ${\ displaystyle (125) (34)}$ Și $(123)$ ${\ displaystyle (123)}$ ${\ displaystyle (123)}$ dăuna $(125)(34)(123)=(15)(243).$ ${\ displaystyle (125) (34) (123) = (15) (243).}$ ${\ displaystyle (125) (34) (123) = (15) (243).}$ Rețineți că compoziția se face de la dreapta la stânga. De exemplu, pentru a vedea unde este trimis 1 din compoziție $(125)(34)(123)$ ${\ displaystyle (125) (34) (123)}$ ${\ displaystyle (125) (34) (123)}$ vezi asta $(123)$ ${\ displaystyle (123)}$ ${\ displaystyle (123)}$ îl trimite în 2, $(34)$ ${\ displaystyle (34)}$ ${\ displaystyle (34)}$ nu mișcă 2 și, în cele din urmă $(125)$ ${\ displaystyle (125)}$ ${\ displaystyle (125)}$ trimite 2 la 5. Deci 1 merge la 5.

Semnul unei permutări

Definiție

Fiecare ciclu este produsul transpunerilor. De fapt, întotdeauna cu compoziția de la dreapta la stânga, avem:

(a_{1},\ldots ,a_{n})=(a_{1},a_{n})(a_{1},a_{n-1})\cdots (a_{1},a_{2}).

{\ displaystyle (a_ {1}, \ ldots, a_ {n}) = (a_ {1}, a_ {n}) (a_ {1}, a_ {n-1}) \ cdots (a_ {1}, a_ {2}).}

(a_ {1}, \ ldots, a_ {n}) = (a_ {1}, a_ {n}) (a_ {1}, a_ {n-1}) \ cdots (a_ {1}, a_ {2 }).

Rezultă că fiecare permutare este produsul transpunerilor. Numărul acestor transpuneri nu este determinat în mod unic de permutare: de exemplu, transpunerea poate fi scrisă $(12)$ ${\ displaystyle (12)}$ $(12)$ de asemenea ca $(23)(13)(23)$ ${\ displaystyle (23) (13) (23)}$ ${\ displaystyle (23) (13) (23)}$ sau $(14)(23)(34)(23)(14)$ ${\ displaystyle (14) (23) (34) (23) (14)}$ ${\ displaystyle (14) (23) (34) (23) (14)}$ . Se poate arăta că dacă aceeași permutare $p$ ${\ displaystyle p}$ $p$ poate fi scris fie ca produs al $h$ ${\ displaystyle h}$ $h$ transpuneri, atât ca produs al $k$ ${\ displaystyle k}$ $k$ transpuneri, atunci $h$ ${\ displaystyle h}$ $h$ Și $k$ ${\ displaystyle k}$ $k$ au aceeași paritate , adică sunt ambele pare sau ambele impare.

O permutare $p$ ${\ displaystyle p}$ $p$ este numit chiar sau impar , în funcție de faptul dacă acesta poate fi obținut ca produs al unui număr par sau impar de transpoziții. Semnul $p$ ${\ displaystyle p}$ $p$ este definit ca +1 și respectiv -1.

Exemple

Toate transpunerile sunt ciudate.
Între $6=3!$ ${\ displaystyle 6 = 3!}$ ${\ displaystyle 6 = 3!}$ permutări ale elementelor $\{1,2,3\}$ ${\ displaystyle \ {1,2,3 \}}$ ${\ displaystyle \ {1,2,3 \}}$ Sunt:
$\mathrm {id} ,(123),(132)$ ${\ displaystyle \ mathrm {id}, (123), (132)}$ ${\ displaystyle \ mathrm {id}, (123), (132)}$ sunt egale;
$(12),(13),(23)$ ${\ displaystyle (12), (13), (23)}$ ${\ displaystyle (12), (13), (23)}$ sunt ciudate.

Proprietate

După ce am definit produsul a două permutări ca fiind compoziția lor, putem spune că funcția „semn” este multiplicativă , adică

\operatorname {segno} (\sigma _{1}\sigma _{2})=\operatorname {segno} (\sigma _{1})\cdot \operatorname {segno} (\sigma _{2}).

{\ displaystyle \ operatorname {sign} (\ sigma _ {1} \ sigma _ {2}) = \ operatorname {sign} (\ sigma _ {1}) \ cdot \ operatorname {sign} (\ sigma _ {2} ).}

\ operatorname {sign} (\ sigma _ {1} \ sigma _ {2}) = \ operatorname {sign} (\ sigma _ {1}) \ cdot \ operatorname {sign} (\ sigma _ {2}).

Grup alternativ

Jumătate din $n!$ ${\ displaystyle n!}$ $n!$ permutări ale unui set de $n$ ${\ displaystyle n}$ $n$ elementele sunt pare. Deoarece funcția de semn este multiplicativă, chiar permutările formează un subgrup normal al grupului simetric $S(X)$ ${\ displaystyle S (X)}$ $S X)$ a permutărilor de $X$ ${\ displaystyle X}$ $X$ din indexul doi, grupul alternativ menționat este indicat cu $A(X).$ ${\ displaystyle A (X).}$ ${\ displaystyle A (X).}$ Acesta este nucleul omomorfismului de grup

\operatorname {segno} \colon S(X)\to \{+1,-1\}.

{\ displaystyle \ operatorname {sign} \ colon S (X) \ to \ {+ 1, -1 \}.}

{\ displaystyle \ operatorname {sign} \ colon S (X) \ to \ {+ 1, -1 \}.}

Imaginea este un grup ciclic cu două elemente.

Formula pentru semn

Semnul unei permutări $\sigma$ ${\ displaystyle \ sigma}$ $\ sigma$ poate fi calculat folosind următoarea formulă:

\operatorname {segno} (\sigma )=\prod _{1\leq i<j\leq n}{\frac {\sigma (j)-\sigma (i)}{j-i}}=\prod _{i=1}^{n-1}\left(\prod _{j=i+1}^{n}{\frac {\sigma (j)-\sigma (i)}{j-i}}\right).

{\ displaystyle \ operatorname {sign} (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} = \ prod _ {i = 1} ^ {n-1} \ left (\ prod _ {j = i + 1} ^ {n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} \ dreapta).}

{\ displaystyle \ operatorname {sign} (\ sigma) = \ prod _ {1 \ leq i <j \ leq n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} = \ prod _ {i = 1} ^ {n-1} \ left (\ prod _ {j = i + 1} ^ {n} {\ frac {\ sigma (j) - \ sigma (i)} {ji}} \ dreapta).}

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere cu permutare

linkuri externe

( EN ) Permutation , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Controlul autorității	Tezaur BNCF 32734

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Combinatorial
Orientare generală	Combinatorică · Istoria combinatoriei · Matematică discretă · Secțiunea 05-XX din MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( Eulerian , Hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Grafic al fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal