Permutáció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 13-án felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A kombinatorika permutációja egy számismétlődések nélküli rendezett halmaz , amelyet általában bijekcióként kezelnek a halmazon , amely a számot a halmaz -edik eleméhez társítja. A számot a permutáció hosszának nevezzük [1] . $1,\ 2,\ \ldots ,\ n,$ ${\displaystyle \{1,\;2,\;\ldots ,\;n\))$ $én$ $én$ $n$

A csoportelméletben egy tetszőleges halmaz permutációja ennek a halmaznak önmagára való bijekcióját jelenti. Az ebben az értelemben vett „permutáció” szó szinonimájaként egyes szerzők a helyettesítés szót használják . (Más szerzők a helyettesítést a permutáció írásának vizuális módjának nevezik. A jelentősebb különbség az, hogy a helyettesítés maga egy függvény, míg a permutáció annak eredménye, hogy ezt a függvényt egy sorozat elemeire alkalmazzuk.)

A „permutáció” kifejezés azért merült fel, mert eleinte tárgyakat vettek, valahogy elrendeztek, és a rendezés más módjai megkívánták az objektumok átrendezését. [2] .

A permutáció azonos számú elemből álló halmaz, amely csak az elemek sorrendjében tér el egymástól. [3]

Tulajdonságok

Az elemek összes permutációjának száma megegyezik a by elhelyezéseinek számával , vagyis a faktoriális [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

A kompozíció meghatározza a szorzat műveletét azonos hosszúságú permutációkra: Erre a műveletre vonatkozóan az elemek permutációinak halmaza egy csoportot alkot, amelyet szimmetrikusnak neveznek, és általában jelölik . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Bármely véges elemcsoport izomorf a szimmetrikus csoport valamely részcsoportjával ( Cayley tétele ). Ebben az esetben minden elem egy permutációhoz van társítva, amelyet az elemeken az azonosság határozza meg, ahol egy csoportművelet -ben . $n$ $S_{n}$ $a\in G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\circ g,$ $\circ$ $G$

Kapcsolódó definíciók

A permutáció hordozója a halmaz egy részhalmaza, amely így vandefiniálva $\pi \kettőspont X\-X$ $x$ $\operatorname {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.$

Egy permutáció fix pontja a leképezéstetszőleges, azaz a halmaz egy elemeEgy permutáció összes fix pontjának halmazaahordozójának komplementere a -ben . $\pi$ $\pi \kettőspont X\-X$ $\{x\in X\mid \pi (x)=x\}.$ $\pi$ $x$

A permutáció inverziója bármely olyan indexpár, amelyés. A permutációban lévő inverziók számának paritása határozza meg a permutáció paritását . $\pi$ $i,\j$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

A permutációk speciális típusai

Az azonos permutáció olyan permutáció, amelyet minden elem saját magára képez le: $e,$ $x\X-ben$ $e(x)=x.$
Az involúció olyan permutáció, amely önmagának az inverze, azaz. $\tau ,$ $\tau \cdot \tau =e.$
A zavar egy permutáció fix pontok nélkül .
A hosszúságú ciklus olyan helyettesítésa részhalmaz kivételévela teljes halmazon azonos,ésjelölése. $\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 }).$
A transzpozíció egy halmaz elemeinek permutációja,amely két elemet felcserél. Az átültetés egy 2 hosszúságú ciklus. $x$

Csere

Egy halmaz permutációja felírható helyettesítésként , például: $\pi$ $x$

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

hol és . $\{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X$ $\pi (x_{i})=y_{i}$

Ciklus a termékek és a permutációs jel

Bármely permutáció felbontható diszjunkt hosszúságú ciklusok szorzatára ( összetételére ) , és egyedi módon a szorzatban lévő ciklusok sorrendjéig. Például: $\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).

Gyakran azt is feltételezik, hogy egy permutáció fix pontjai független, 1 hosszúságú ciklusok, és ezekkel egészítik ki a permutáció cikluskiterjesztését. A fenti példában egy ilyen kiterjesztett dekompozíció a következő lenne . A permutáció ciklikus szerkezetét a különböző hosszúságú ciklusok száma, nevezetesen a számhalmaz , ahol a hosszúságú ciklusok száma határozza meg . Ebben az esetben az érték megegyezik a permutáció hosszával, és az érték egyenlő a ciklusok teljes számával. A ciklusos elemek permutációinak számát az első típusú előjel nélküli Stirling-szám adja meg . $(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))$

Bármely ciklus felbontható (nem feltétlenül diszjunkt) transzpozíciók szorzatára . Ebben az esetben egy 1 hosszúságú ciklus (ami lényegében azonos permutáció ) ábrázolható a transzpozíciók üres szorzataként , vagy például bármely transzpozíció négyzeteként: Egy hosszúságú ciklust fel lehet bontani a következő átültetések szorzata : $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}).

Meg kell jegyezni, hogy a ciklusok transzpozíciók szorzatává való felbomlása nem egyedi:

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

Így bármely permutáció felbontható transzpozíciók szorzatára. Bár ezt sokféleképpen meg lehet tenni, az átültetések számának paritása minden ilyen dekompozícióban azonos. Ez lehetővé teszi , hogy egy permutáció ( permutációs paritás vagy permutációs szignatúra ) előjelét a következőképpen határozzuk meg: $\pi$

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

ahol az átültetések száma a . Ebben az esetben páros permutációt hívnak , ha , és páratlan permutációt , ha . $t$ $\pi$ $\pi$ $\varepsilon _{\pi }=1$ $\varepsilon _{\pi }=-1$

Ezzel egyenértékűen a permutáció előjelét a ciklusszerkezete határozza meg: az elemek ciklusokból álló permutációjának előjele egyenlő $\pi$ $n$ $k$

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

A permutáció előjele az inverziók számából is meghatározható : $\pi$ $N(\pi )$ $\pi$

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

Permutációk ismétléssel

Vegye figyelembe a különböző típusú elemeket , és minden típusban minden elem azonos. Ekkor ezeknek az elemeknek a permutációit, az azonos típusú elemek sorrendjéig , ismétléses permutációknak nevezzük . Ha a th típusú elemek száma, akkor a lehetséges permutációk száma ismétlődésekkel egyenlő a multinomiális együtthatóval $n$ $m$ $k_i$ $én$ $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}!}}.$

Az ismétlődéseket tartalmazó permutációt sokhalmazos permutációnak is tekinthetjük . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Véletlenszerű permutáció

A véletlen permutáció egy véletlen vektor, amelynek minden eleme természetes értéket vesz fel 1-től, és bármely két elem egyezésének valószínűsége 0. $\xi =(\xi _{1},\;\ldots ,\;\xi _{n}),$ $n,$

A független véletlen permutáció olyan véletlenszerű permutáció , amelyre: $\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)}}}}

néhány ilyenre: $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.

Ha ugyanakkor nem függ től , akkor a permutációt egyenlő eloszlásúnak nevezzük . Ha nincs függőség -tól , akkor azt homogénnek nevezzük . $p_{{ij}}$ $én$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Lásd még

Jegyzetek

↑ Jevgenyij Vectomov, Dmitrij Shirokov. Matematika: Logika, Halmazok, Kombinatorika . Tankönyv az akadémiai érettségihez. - 2. kiadás - Liter, 2018-03-02. - S. 145-146. — 244 p. Archiválva : 2022. április 7. a Wayback Machine -nél
↑ Matematika tankönyv SPO-nak / M. I. Bashmakov, 10-11. osztály. - 67. o
↑ Valószínűségszámítás és a matematikai statisztika elemei Archiválva : 2022. február 1. a Wayback Machine -nél
↑ Vilenkin N.Ya. fejezet III. Sorok és halmazok kombinatorikája. Kiosztások ismétlődésekkel // Népszerű kombinatorika . - M. : Nauka, 1975. - S. 80. - 208 p.
↑ Konfigurációelmélet és felsoroláselmélet . Hozzáférés dátuma: 2009. december 30. Az eredetiből archiválva : 2010. január 23. (határozatlan)
↑ 3. fejezet. A kombinatorika elemei archiválva : 2010. január 4. a Wayback Machine -nél . // Előadások a valószínűségelméletről.
↑ Donald E. Knuth – A programozás művészete. 1. kötet. Alapvető algoritmusok. 1.2.5. Permutációk és faktoriálisok

Irodalom

Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Rendezés és keresés. - 2. kiadás - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Bevezetés az algebrába. Az algebra alapjai . - M .: Fizmatlit , 1994. - S. 59 -71. — 320 s. — ISBN 5-02-014644-7 .
Szergej Melnyikov. Permutációk, kombinációk, elhelyezések: az összes permutáció származtatása // Delphi és Turbo Pascal szórakoztató példákkal. - BHV-Pétervár, 2012. - 448 p. - ISBN 978-5-94157-886-3 .

Linkek

Arangeman // Brockhaus és Efron enciklopédikus szótára : 86 kötetben (82 kötet és további 4 kötet). - Szentpétervár. , 1890-1907.