Permutaatio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13.11.2021 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Permutaatio kombinatoriikassa on järjestetty joukko ilman lukujen toistoja , yleensä sitä käsitellään joukossa bijektiona , joka yhdistää luvun joukon -: nnen elementin kanssa. Lukua kutsutaan permutaation pituudeksi [1] . ${\näyttötyyli 1,\ 2,\ \ldots ,\ n,}$ ${\displaystyle \{1,\;2,\;\ldots ,\;n\))$ $i$ $i$ $n$

Ryhmäteoriassa mielivaltaisen joukon permutaatio tarkoittaa tämän joukon bijektiota itseensä . Synonyyminä sanalle "permutaatio" tässä mielessä jotkut kirjoittajat käyttävät sanaa substituutio . (Toiset kirjoittajat kutsuvat substituutiota visuaalisena tapana kirjoittaa permutaatio. Merkittävämpi ero on, että substituutio on itse funktio, kun taas permutaatio on tulosta soveltamalla tätä funktiota sekvenssin elementteihin.)

Termi "permutaatio" syntyi, koska aluksi esineitä otettiin, järjestettiin jotenkin ja muut järjestystavat vaativat näiden objektien uudelleenjärjestelyä. [2] .

Permutaatio on joukko, joka koostuu samasta määrästä elementtejä, jotka eroavat vain elementtien järjestyksestä. [3]

Ominaisuudet

Kaikkien elementtien permutaatioiden määrä on yhtä suuri kuin by:n sijoittelujen lukumäärä , eli tekijä [ 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

Koostumus määrittää tuotteen toiminnan samanpituisilla permutaatioilla: Tämän operaation suhteen elementtien permutaatioiden joukko muodostaa ryhmän , jota kutsutaan symmetriseksi ja jota yleensä merkitään . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Mikä tahansa äärellinen elementtiryhmä on isomorfinen jollekin symmetrisen ryhmän alaryhmälle ( Cayleyn lause ). Tässä tapauksessa jokainen elementti liittyy permutaatioon , jonka elementeille määrittää identiteetti missä on ryhmäoperaatio . $n$ $S_{n}$ $a\in G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\circ g,$ $\circ$ $G$

Aiheeseen liittyvät määritelmät

Permutaation kantoaalto on joukon osajoukko, jokamääritellään nimellä $\pi \kaksoispiste X\-X$ $X$ $\operaattorinnimi {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.$

Permutaation kiinteä piste on mikä tahansakuvauksen kiinteä piste, eli joukon elementti.Permutaation kaikkien kiinteiden pisteiden joukkoonsen kantajan komplementti . $\pi$ $\pi \kaksoispiste X\-X$ $\{x\in X\mid \pi (x)=x\}.$ $\pi$ $X$

Inversio permutaatiossaon mikä tahansa indeksien parisiten, ettäja. Permutaation inversioiden lukumäärän pariteetti määrittää permutaation pariteetin . $\pi$ ${\näyttötyyli i,\j}$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Permutaatioiden erikoistyypit

Identtinen permutaatio on permutaatio, jonka jokainen elementti kuvaa itselleen: $e,$ $x\in X$ $e(x)=x.$
Involuutio on permutaatio, joka on itsensä käänteinen, ts. $\tau ,$ $\tau \cdot \tau =e.$
Häiriö on permutaatio ilman kiinteitä pisteitä .
Jakson pituus onsellainen korvaus, joka on identtinen koko joukossalukuun ottamatta osajoukkoajamerkitään. $\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 }).$
Transpositio on joukon elementtien permutaatio,joka vaihtaa kaksi elementtiä. Transponointi on sykli, jonka pituus on 2. $X$

Korvaus

Joukon permutaatio voidaan kirjoittaa substituutioksi , esimerkiksi: $\pi$ $X$

{\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\lpisteet &y_{n}\ end{pmatrix}},

missä ja . $\{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X$ $\pi (x_{i})=y_{i}$

Kierrä tuotteet ja permutaatiomerkki

Mikä tahansa permutaatio voidaan hajottaa pituisten epäyhtenäisten syklien tuotteeksi ( koostumukseksi ) ja ainutlaatuisella tavalla tuotteen syklien järjestykseen asti. Esimerkiksi: $\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).

Usein oletetaan myös, että permutaation kiinteät pisteet ovat itsenäisiä syklejä, joiden pituus on 1, ja ne täydentävät niillä permutaation syklilaajennusta. Yllä olevassa esimerkissä tällainen lisätty hajotus olisi . Eripituisten jaksojen lukumäärä, nimittäin lukujoukko , jossa on pituisten jaksojen lukumäärä , määrittää permutaation syklisen rakenteen . Tässä tapauksessa arvo on yhtä suuri kuin permutaation pituus ja arvo on yhtä suuri kuin jaksojen kokonaismäärä. Elementtien permutaatioiden lukumäärä jaksoilla saadaan ensimmäisen tyypin etumerkittömällä Stirling-luvulla . $(1,\;5,\;2)(3,\;6)(4)$ $(c_{1},\;c_{2},\;\ldots )$ ${\displaystyle 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))$

Mikä tahansa sykli voidaan hajottaa (ei välttämättä hajautettujen) transpositioiden tuloksi . Tässä tapauksessa sykli, jonka pituus on 1 (joka on olennaisesti identtinen permutaatio ) voidaan esittää transpositioiden tyhjänä tulona tai esimerkiksi minkä tahansa transponoinnin neliönä: Pituusjakso voidaan hajottaa transponoinnin tulos seuraavasti: $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 })\dots (x_{1},\;x_{2}).

On huomattava, että syklien hajoaminen transpositioiden tuloksi ei ole ainutlaatuinen:

{\näyttötyyli (1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\; 3)(2,\;4)(2,\;4)(1,\;2).}

Siten mikä tahansa permutaatio voidaan hajottaa transpositioiden tuloksi. Vaikka tämä voidaan tehdä monella tavalla, transponointien lukumäärän pariteetti on sama kaikissa tällaisissa hajotteluissa. Tämä mahdollistaa permutaation etumerkin ( permutaatiopariteetti tai permutaatioallekirjoitus ) määrittämisen seuraavasti: $\pi$

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

missä on transponointien määrä jossain laajennuksessa . Tässä tapauksessa he kutsuvat parillista permutaatiota if , ja paritonta permutaatiota jos . $t$ $\pi$ $\pi$ $\varepsilon _{\pi }=1$ $\varepsilon _{\pi }=-1$

Vastaavasti permutaation etumerkki määräytyy sen syklin rakenteesta: jaksoista koostuvan elementtien permutaation etumerkki on yhtä suuri kuin $\pi$ $n$ $k$

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

Permutaation etumerkki voidaan määrittää myös inversioiden lukumäärällä : $\pi$ $N(\pi )$ $\pi$

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

Permutaatiot toistolla

Harkitse erityyppisiä elementtejä , ja jokaisessa tyypissä kaikki elementit ovat samoja. Sitten kaikkien näiden elementtien permutaatioita samantyyppisten elementtien järjestykseen asti kutsutaan permutaatioiksi toistolla . Jos on th-tyypin elementtien lukumäärä, niin mahdollisten permutaatioiden määrä toistoilla on yhtä suuri kuin moninomikerroin $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}!}}.$

Permutaatiota, jossa on toistoja, voidaan pitää myös kardinaalisuuden monijoukkopermutaationa . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Satunnainen permutaatio

Satunnaispermutaatio on satunnaisvektori, jonka kaikki elementit saavat luonnolliset arvot 1:stä ja minkä tahansa kahden elementin yhteensopivuuden todennäköisyys on 0. $\xi =(\xi _{1},\;\ldots ,\;\xi _{n}),$ $n,$

Itsenäinen satunnaispermutaatio on sellainen satunnainen permutaatio , jolle: $\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)}}}}

joillekin sellaisille: $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.

Jos samaan aikaan eivät riipu , niin permutaatiota kutsutaan tasajakaiseksi . Jos ei ole riippuvuutta , eli sitä kutsutaan homogeeniseksi . $p_{{ij}}$ $i$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Katso myös

Muistiinpanot

↑ Jevgeni Vectomov, Dmitri Širokov. Matematiikka: Logiikka, joukot, kombinatoriikka . Oppikirja akateemiseen ylioppilastutkintoon. - 2. painos - litraa, 2018-03-02. - S. 145-146. — 244 s. Arkistoitu 7. huhtikuuta 2022 Wayback Machinessa
↑ Matematiikan oppikirja SPO:lle / M. I. Bashmakov, luokat 10-11. - s. 67
↑ Todennäköisyysteoria ja matemaattisten tilastojen elementit Arkistoitu 1. helmikuuta 2022 Wayback Machinessa
↑ Vilenkin N.Ya. III luku. Tuplejen ja joukkojen kombinatoriikka. Allokaatiot toistoilla // Suosittu kombinatoriikka . - M .: Nauka, 1975. - S. 80. - 208 s.
↑ Konfiguraatioteoria ja laskentateoria . Käyttöpäivä: 30. joulukuuta 2009. Arkistoitu alkuperäisestä 23. tammikuuta 2010. (määrätön)
↑ Luku 3. Kombinatoriikan elementit Arkistoitu 4. tammikuuta 2010 Wayback Machinessa . // Todennäköisyysteorian luentoja.
↑ Donald E. Knuth - Ohjelmoinnin taito. Volume 1. Perusalgoritmit. 1.2.5. Permutaatiot ja tekijät

Kirjallisuus

Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Lajittelu ja haku. - 2. painos - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Johdatus algebraan. Algebran perusteet . - M .: Fizmatlit , 1994. - S. 59 -71. – 320 s. — ISBN 5-02-014644-7 .
Sergei Melnikov. Permutaatiot, yhdistelmät, sijoittelut: kaikkien permutaatioiden johtaminen // Delphi ja Turbo Pascal hauskoilla esimerkeillä. - BHV-Petersburg, 2012. - 448 s. - ISBN 978-5-94157-886-3 .

Linkit

Arangeman // Encyclopedic Dictionary of Brockhaus and Efron : 86 nidettä (82 osaa ja 4 lisäosaa). - Pietari. , 1890-1907.