Permutace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. listopadu 2021; kontroly vyžadují 6 úprav .

Permutace v kombinatorice je uspořádaná množina bez opakování čísel , obvykle považována za bijekci na množině , která spojuje číslo s -tým prvkem z množiny. Číslo se nazývá délka permutace [1] . $1,\ 2,\ \ldots ,\ n,$ ${\displaystyle \{1,\;2,\;\ldots ,\;n\))$ $i$ $i$ $n$

V teorii grup znamená permutace libovolné množiny bijekci této množiny na sebe. Jako synonymum pro slovo „permutace“ v tomto smyslu někteří autoři používají slovo substituce . (Jiní autoři nazývají substituci vizuálním způsobem zápisu permutace. Podstatnější rozdíl je v tom, že substituce je funkce sama o sobě, zatímco permutace je výsledkem aplikace této funkce na prvky posloupnosti.)

Pojem „permutace“ vznikl proto, že se nejprve předměty braly, nějak uspořádávaly a jiné způsoby řazení vyžadovaly tyto předměty přeskupovat. [2] .

Permutace je množina sestávající ze stejného počtu prvků, lišících se pouze v pořadí prvků. [3]

Vlastnosti

Počet všech permutací prvků se rovná počtu umístění by , tedy faktoriálu [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

Kompozice definuje operaci součinu na permutacích stejné délky: S ohledem na tuto operaci tvoří množina permutací prvků grupu , která se nazývá symetrická a obvykle se označuje . $(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ $n$ $S_{n}$

Jakákoli konečná grupa prvků je izomorfní k nějaké podgrupě symetrické grupy ( Cayleyova věta ). V tomto případě je každý prvek spojen s permutací definovanou na prvcích identitou , kde je skupinová operace v . $n$ $S_{n}$ $v G$ $\pi _{a}$ $G$ $\pi _{a}(g)=a\circ g,$ $\circ$ $G$

Související definice

Nosič permutace je podmnožinou množinydefinované jako $\pi \dvojtečka X\to X$ $X$ $\operatorname {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.$

Pevný bod permutaceje libovolný pevný bod zobrazení, tedy prvek množinyMnožina všech pevných bodů permutaceje doplňkem její nosné v. $\pi$ $\pi \dvojtečka X\to X$ $\{x\in X\mid \pi (x)=x\}.$ $\pi$ $X$

Inverze v permutacije jakýkoli pár indexůtakový, žea. Parita počtu inverzí v permutaci určuje paritu permutace . $\pi$ $i,\j$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Speciální typy permutací

Identická permutace je permutace , kterou na sebe mapuje každý prvek: $E,$ $x\in X$ $e(x)=x.$
Involuce je permutace, která je inverzní sama k sobě, tzn. $\tau,$ $\tau \cdot \tau =e.$
Porucha je permutace bez pevných bodů .
Cyklus délkyje taková substituce, která je shodná v celé množiněkromě podmnožinyaznačí. $\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 }).$
Transpozice je permutace prvků množiny, která zaměňuje dva prvky. Transpozice je cyklus délky 2. $X$

Substituce

Permutaci množiny lze zapsat jako substituci , například: $\pi$ $X$

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

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

Cyklické produkty a permutační znak

Libovolnou permutaci lze rozložit na součin ( složení ) disjunktních cyklů délky , a to jedinečným způsobem až do pořadí cyklů v součinu. Například: $\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).

Často se také předpokládá, že pevné body permutace jsou nezávislé cykly délky 1 a doplňují jimi expanzi cyklu permutace. Pro výše uvedený příklad by takový rozšířený rozklad byl . Počet cyklů různých délek, konkrétně množina čísel , kde je počet cyklů délky , určuje cyklickou strukturu permutace. V tomto případě se hodnota rovná délce permutace a hodnota se rovná celkovému počtu cyklů. Počet permutací prvků s cykly je dán Stirlingovým číslem bez znaménka prvního druhu . $(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))$

Jakýkoli cyklus lze rozložit na součin (ne nutně disjunktních) transpozic . Cyklus délky 1 (což je v podstatě identická permutace ) lze v tomto případě reprezentovat jako prázdný součin transpozic nebo např. jako čtverec libovolné transpozice: Cyklus délky lze rozložit na součin transpozic takto: $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 })\tečky (x_{1},\;x_{2}).

Je třeba poznamenat, že rozklad cyklů na součin transpozic není jedinečný:

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

Každá permutace se tedy může rozložit na součin transpozic. Ačkoli to lze provést mnoha způsoby, parita počtu transpozic je ve všech takových expanzích stejná. To umožňuje, aby byl znak permutace ( permutační parita nebo permutační podpis ) definován jako: $\pi$

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

kde je počet transpozic v nějaké expanzi . V tomto případě volají sudou permutaci if , a lichou permutaci if . $t$ $\pi$ $\pi$ $\varepsilon _{\pi }=1$ $\varepsilon _{\pi }=-1$

Ekvivalentně je znaménko permutace určeno její strukturou cyklu: znaménko permutace prvků , sestávající z cyklů, je rovno $\pi$ $n$ $k$

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

Znaménko permutace lze také určit z hlediska počtu inverzí v : $\pi$ $N(\pi)$ $\pi$

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

Permutace s opakováním

Zvažte prvky různých typů a v každém typu jsou všechny prvky stejné. Pak se permutace všech těchto prvků až do řádu stejného typu prvků nazývají permutace s opakováním . Je-li počet prvků tého typu, pak počet možných permutací s opakováním je roven multinomickému koeficientu $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}!}}.$

Permutace s opakováními může být také chápána jako multisetová permutace mohutnosti . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Náhodná permutace

Náhodná permutace je náhodný vektor, jehož všechny prvky mají přirozené hodnoty od 1 do a pravděpodobnost, že se kterékoli dva prvky shodují, je 0. $\xi =(\xi _{1},\;\ldots ,\;\xi _{n}),$ $n,$

Nezávislá náhodná permutace je taková náhodná permutace , pro kterou: $\xi$

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

pro některé takové, že: $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.

Pokud zároveň nezávisí na , pak se permutace nazývá rovnoměrně rozložené . Pokud neexistuje žádná závislost na , to znamená, že se nazývá homogenní . $p_{{ij}}$ $i$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Viz také

Poznámky

↑ Jevgenij Vechtomov, Dmitrij Širokov. Matematika: logika, množiny, kombinatorika . Učebnice pro akademické bakaláře. - 2. vyd. - Litry, 2018-03-02. - S. 145-146. — 244 s. Archivováno 7. dubna 2022 na Wayback Machine
↑ Učebnice matematiky pro SPO / M. I. Bašmakov, ročníky 10-11. - str. 67
↑ Teorie pravděpodobnosti a prvky matematické statistiky Archivováno 1. února 2022 na Wayback Machine
↑ Vilenkin N.Ya. Kapitola III. Kombinatorika n-tic a množin. Alokace s opakováním // Populární kombinatorika . - M. : Nauka, 1975. - S. 80. - 208 s.
↑ Teorie konfigurace a teorie výčtu . Datum přístupu: 30. prosince 2009. Archivováno z originálu 23. ledna 2010. (neurčitý)
↑ Kapitola 3. Elements of Combinatorics Archivováno 4. ledna 2010 na Wayback Machine . // Přednášky z teorie pravděpodobnosti.
↑ Donald E. Knuth – Umění programování. Svazek 1. Základní algoritmy. 1.2.5. Permutace a faktoriály

Literatura

Donald Knuth . Umění počítačového programování, díl 3. Třídění a vyhledávání = The Art of Computer Programming, díl 3. Třídění a vyhledávání. - 2. vyd. - M .: "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Úvod do algebry. Základy algebry . - M .: Fizmatlit , 1994. - S. 59 -71. — 320 s. — ISBN 5-02-014644-7 .
Sergej Melnikov. Permutace, kombinace, umístění: odvození všech permutací // Delphi a Turbo Pascal se zábavnými příklady. - BHV-Petersburg, 2012. - 448 s. - ISBN 978-5-94157-886-3 .

Odkazy

Arangeman // Encyklopedický slovník Brockhause a Efrona : v 86 svazcích (82 svazcích a 4 dodatečné). - Petrohrad. , 1890-1907.