Permutare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 noiembrie 2021; verificările necesită 6 modificări .

O permutare în combinatorică este o mulțime ordonată fără repetiții de numere , de obicei tratată ca o bijecție pe mulțime , care asociază numărul cu al -lea element din mulțime. Numărul se numește lungimea permutației [1] . $1,\ 2,\ \ldots ,\n,$ $\{1,\;2,\;\ldots ,\;n\)$ $i$ $i$ $n$

În teoria grupurilor , o permutare a unei mulțimi arbitrare înseamnă o bijecție a acestei mulțimi asupra ei însuși. Ca sinonim pentru cuvântul „permutare” în acest sens, unii autori folosesc cuvântul substituție . (Alți autori numesc substituția un mod vizual de a scrie o permutare. Diferența mai semnificativă este că o substituție este o funcție în sine, în timp ce o permutare este rezultatul aplicării acelei funcție la elementele unei secvențe.)

Termenul de „permutare” a apărut pentru că la început erau luate obiecte, aranjate cumva, iar alte moduri de ordonare necesitau rearanjarea acestor obiecte. [2] .

O permutare este o mulțime formată din același număr de elemente, care diferă doar în ordinea elementelor. [3]

Proprietăți

Numărul tuturor permutărilor elementelor este egal cu numărul de plasări ale lui by , adică factorialul [4] [5] [6] [7] : $n$ $n$ $n$

P_{n}=A_{n}^{n}={\frac {n!}{(nn)!}}={\frac {n!}{0!}}=n!=1\ cdot 2\cdot \ldots \cdot n

Compoziția definește funcționarea produsului pe permutări de aceeași lungime: În ceea ce privește această operație, mulțimea permutărilor elementelor formează un grup , care se numește simetric și este de obicei notat . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Orice grup finit de elemente este izomorf cu un subgrup al grupului simetric ( teorema lui Cayley ). În acest caz, fiecare element este asociat cu o permutare definită asupra elementelor prin identitatea unde este o operație de grup în . $n$ $S_{n}$ $a\în G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\circ g,$ $\circ$ $G$

Definiții înrudite

Purtătorul unei permutări este un subset al setuluidefinit ca $\pi \colon X\la X$ $X$ $\operatorname {supp} (\pi):=\{x\in X\mid \pi (x)\neq x\}.$

Un punct fix al unei permutărieste orice punct fix al mapării, adică un element al mulțimii. Mulțimea tuturor punctelor fixe ale unei permutărieste complementul purtătorului său în. $\pi$ $\pi \colon X\la X$ $\{x\in X\mid \pi (x)=x\}.$ $\pi$ $X$

O inversare într-o permutareeste orice pereche de indiciastfel încâtși. Paritatea numărului de inversiuni într-o permutare determină paritatea permutării . $\pi$ $i,\j$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Tipuri speciale de permutări

O permutare identică este o permutare pecare fiecare element o mapează la sine: $e,$ $x\în X$ $e(x)=x.$
O involuție este o permutarecare este inversa ei însăși, adică. $\tau ,$ $\tau \cdot \tau =e.$
Tulburarea este o permutare fără puncte fixe .
Un ciclu de lungimeeste o astfel de substituțiecare este identică pe întregul set,cu excepția submulțimiișinotat. $\ell$ $\pi ,$ $X,$ $\{x_{1},\;x_{2},\;\ldots ,\;x_{\ell }\}\subset X$ $\pi (x_{\ell })=x_{1},\\pi (x_{i})=x_{i+1}.$ $(x_{1},\;x_{2},\;\ldots ,\;x_{\ell }).$
O transpunere este o permutare a elementelor unui setcare schimbă două elemente. Transpunerea este un ciclu de lungime 2. $X$

Înlocuire

O permutare a unei multimi poate fi scrisa ca o substitutie , de exemplu: $\pi$ $X$

{\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\ sfârșit{pmatrix}},

unde si . $\{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X$ $\pi (x_{i})=y_{i}$

Produsele ciclului și semnul de permutare

Orice permutare poate fi descompusă într-un produs ( compoziție ) de cicluri disjunse de lungime și într-un mod unic până la ordinea ciclurilor din produs. De exemplu: $\pi$ $\ell \geqslant 2$

{\begin{pmatrix}1&2&3&4&5&6\\5&1&6&4&2&3\end{pmatrix}}=(1,\;5,\;2)(3,\;6).

De asemenea, se presupune adesea că punctele fixe ale unei permutări sunt cicluri independente de lungime 1 și completează extinderea ciclului permutării cu ele. Pentru exemplul de mai sus, o astfel de descompunere augmentată ar fi . Numărul de cicluri de lungimi diferite, și anume setul de numere , unde este numărul de cicluri de lungime , determină structura ciclică a permutației. În acest caz, valoarea este egală cu lungimea permutației, iar valoarea este egală cu numărul total de cicluri. Numărul de permutări ale elementelor cu cicluri este dat de numărul Stirling nesemnat de primul fel . $(1,\;5,\;2)(3,\;6)(4)$ $(c_{1},\;c_{2},\;\ldots )$ $c_{\ell )$ $\ell$ $1\cdot c_{1}+2\cdot c_{2}+\ldots$ $c_{1}+c_{2}+\ldots$ $n$ $k$ ${\begin{bmatrix}n\\k\end{bmatrix})$

Orice ciclu poate fi descompus într-un produs al transpozițiilor (nu neapărat disjunse) . În acest caz, un ciclu de lungime 1 (care este în esență o permutare identică ) poate fi reprezentat ca un produs gol al transpozițiilor sau, de exemplu, ca un pătrat al oricărei transpoziții: Un ciclu de lungime poate fi descompus într-un produsul transpozițiilor după cum urmează: $e$ $(1,\;2)(1,\;2)=(2,\;3)(2,\;3)=e.$ $\ell \geqslant 2$ $\ell -1$

(x_{1},\;\ldots ,\;x_{l})=(x_{1},\;x_{\ell })(x_{1},\;x_{\ell -1 })\puncte (x_{1},\;x_{2}).

Trebuie remarcat faptul că descompunerea ciclurilor într-un produs de transpoziții nu este unică:

(1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\; 3)(2,\;4)(2,\;4)(1,\;2).

Astfel, orice permutare poate fi descompusă într-un produs al transpozițiilor. Deși acest lucru se poate face în multe moduri, paritatea numărului de transpoziții este aceeași în toate astfel de extinderi. Acest lucru permite ca semnul unei permutări ( paritatea permutării sau semnătura permutării ) să fie definit ca: $\pi$

\varepsilon _{\pi }=(-1)^{t},

unde este numărul de transpuneri într-o anumită expansiune a . În acest caz, ei numesc o permutare pară dacă , și o permutare impară dacă . $t$ $\pi$ $\pi$ $\varepsilon _{\pi}=1$ $\varepsilon _{\pi}=-1$

În mod echivalent, semnul unei permutări este determinat de structura sa ciclului: semnul unei permutări de elemente, constând din cicluri, este egal cu $\pi$ $n$ $k$

\varepsilon _{\pi}=(-1)^{nk)

Semnul permutației poate fi determinat și în funcție de numărul de inversiuni în : $\pi$ $N(\pi )$ $\pi$

\varepsilon _{\pi}=(-1)^{N(\pi ))

Permutări cu repetare

Luați în considerare elemente de diferite tipuri și în fiecare tip toate elementele sunt aceleași. Apoi permutările tuturor acestor elemente, până la ordinea aceluiași tip de elemente, se numesc permutări cu repetare . Dacă este numărul de elemente de al treilea tip, atunci numărul de permutări posibile cu repetări este egal cu coeficientul multinomial $n$ $m$ $k_i$ $i$ $k_{1}+k_{2}+\ldots +k_{m}=n$ $\textstyle {\binom {n}{k_{1},\;k_{2},\;\ldots ,\;k_{m))}={\frac {n!}{k_{1} !k_{2}!\ldots k_{m}!}}.$

O permutare cu repetări poate fi, de asemenea, considerată ca o permutare multiset de cardinalitate . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Permutare aleatorie

O permutare aleatorie este un vector aleatoriu, ale cărui elemente iau valori naturale de la 1 la și probabilitatea ca oricare două elemente să se potrivească este 0. $\xi =(\xi _{1},\;\ldots,\;\xi _{n}),$ $n,$

O permutare aleatorie independentă este o astfel de permutare aleatoare , pentru care: $\xi$

P\{\xi =\sigma \}={\frac {p_{{1\sigma (1)}}\ldots p_{{n\sigma (n)))}{\sum \limits _{{\pi \in S_{n}}}p_{{1\pi (1)}}\ldots p_{{n\pi (n)}}}}

pentru unii astfel încât: $p_{{ij}},$

\forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1

\sum \limits _{{\pi \in S_{n}}}p_{{1\pi (1)))\ldots p_{{n\pi (n))))>0.

Dacă în același timp nu depind de , atunci permutarea se numește distribuit egal . Dacă nu există dependență de , adică se numește omogen . $p_{{ij}}$ $i$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Vezi și

Note

↑ Evgheni Vechtomov, Dmitri Shirokov. Matematică: logică, mulțimi, combinatorică . Manual pentru bacalaureat academic. - Ed. a II-a - Litri, 02-03-2018. - S. 145-146. — 244 p. Arhivat pe 7 aprilie 2022 la Wayback Machine
↑ Manual de matematică pentru SPO / M. I. Bashmakov, clasele 10-11. - p. 67
↑ Teoria probabilității și elemente de statistică matematică Arhivat la 1 februarie 2022 la Wayback Machine
↑ Vilenkin N.Ya. Capitolul III. Combinatorică de tupluri și mulțimi. Alocații cu repetiții // Combinatorică populară . - M. : Nauka, 1975. - S. 80. - 208 p.
↑ Teoria configurației și teoria enumerației . Data accesului: 30 decembrie 2009. Arhivat din original la 23 ianuarie 2010. (nedefinit)
↑ Capitolul 3. Elements of Combinatorics Arhivat la 4 ianuarie 2010 la Wayback Machine . // Prelegeri despre teoria probabilității.
↑ Donald E. Knuth - Arta programarii. Volumul 1. Algoritmi de bază. 1.2.5. Permutări și factoriali

Literatură

Donald Knuth . The Art of Computer Programming, Volumul 3. Sorting and Searching = The Art of Computer Programming, vol.3. Sortare și căutare. - Ed. a II-a. - M . : „Williams” , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Introducere în algebră. Fundamentele algebrei . - M .: Fizmatlit , 1994. - S. 59 -71. — 320 s. — ISBN 5-02-014644-7 .
Serghei Melnikov. Permutări, combinații, plasări: derivarea tuturor permutărilor // Delphi și Turbo Pascal cu exemple distractive. - BHV-Petersburg, 2012. - 448 p. - ISBN 978-5-94157-886-3 .

Link -uri

Arangeman // Dicționar enciclopedic al lui Brockhaus și Efron : în 86 de volume (82 de volume și 4 suplimentare). - Sankt Petersburg. , 1890-1907.