Cyklická permutace

V teorii grup je cyklická permutace permutace prvků nějaké množiny X , která přeskupuje prvky nějaké podmnožiny S množiny X cyklickým způsobem a udržuje zbývající prvky X na místě (tj. mapuje je do sebe) . Například permutace {1, 2, 3, 4}, která trvá 1 až 3, 3 až 2, 2 až 4 a 4 až 1 je cyklická, zatímco permutace, která trvá 1 až 3, 3 až 1, 2 až 4 a 4 ve 2 není cyklický.

Cyklus v permutaci je podmnožina prvků, které jsou permutovány cyklickým způsobem. Množina S se nazývá dráha cyklu. Každá permutace konečné množiny prvků může být rozložena na spojení cyklů s neprotínajícími se drahami. V některých kontextech se cyklická permutace sama nazývá cyklus.

Definice

Permutace se nazývá cyklická právě tehdy, když se skládá z jediného netriviálního cyklu (tj. cyklu o délce větší než 1) [1] .

Příklad:

{\displaystyle {\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&p7}(1rix)\{5)

Někteří autoři omezují definici pouze na ty permutace, které mají právě jeden cyklus (tj. permutace, které mají pevné body, nejsou povoleny [2] .

Příklad:

{\displaystyle {\begin{pmatrix}1&2&3&4&5&6&7&8\\4&5&7&6&8&2&1&3\end{pmatrix}}={\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&5&8&3&837&1}=6

Formálněji se permutace množiny X , která je bijektivní funkcí , nazývá cyklická, pokud akce na X podgrupy s generátorem má nanejvýš jednu orbitu více než jednoho prvku [3] . Tento koncept se nejčastěji používá, když X je konečná množina. Pak je ovšem největší dráha S také konečná. Dovolit být libovolný prvek S , nastavit pro libovolný . Pokud je množina S konečná, pak existuje minimální číslo , pro které . Potom a je permutace definovaná vzorcem $\sigma :X\to X$ $\sigma$ ${\displaystyle s_{0))$ $s_{i}=\sigma ^{i}(s_{0})$ $i\in \mathbf {Z}$ $k\geqslant 1$ ${\displaystyle s_{k}=s_{0))$ ${\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\))$ $\sigma$

\sigma (s_{i})=s_{i+1}\quad

pro

0\leq i<k

a pro jakýkoli prvek . Prvky nezachycené na displeji mohou být reprezentovány jako $\sigma (x)=x$ $X\setminus S$ $\sigma$

{\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0))

Smyčku lze zapsat pomocí kompaktního zápisu smyčky (v takovém zápisu není mezi prvky žádná čárka, aby nedošlo k záměně s n-ticemi ). Délka cyklu je počet prvků na jeho největší oběžné dráze. V notaci smyček jsou smyčky délky 1 často vynechány, pokud to nezpůsobí zmatek [4] . $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$

Základní vlastnosti

Podle jedné z hlavních vlastností symetrických grup může být jakákoli permutace reprezentována jako součin neprotínajících se cyklů (přesněji cyklů s neprotínajícími se drahami). Takové cykly mohou být navzájem permutovány a výraz permutace je jedinečný až do pořadí cyklů (všimněte si, že cyklický zápis není jedinečný - každý k -cyklus samotný může být zapsán k různými způsoby, v závislosti na volbě v jeho oběžná dráha). Vícemnožina délek cyklů (typ cyklu) je jednoznačně určena permutací. ${\displaystyle s_{0))$

Počet různých cyklů délky k v symetrické skupině S n je dán následujícím vzorcem $1\leqslant k\leqslant n$

{\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n !}{(nk)!k}}

Cyklus délky k má paritu (−1) k − 1 .

Transpozice

Cyklus sestávající ze dvou prvků se nazývá transpozice . Například permutace {1, 4, 3, 2}, která trvá 1 až 1, 2 až 4, 3 až 3 a 4 až 2, je transpozice (jmenovitě transpozice, která zamění 2 a 4).

Jakoukoli permutaci lze reprezentovat jako složení (produkt) transpozic - formálně jde o generátory skupin [5] . Navíc libovolnou permutaci uspořádané množiny X = {1, 2, …, n } lze vyjádřit jako součin sousedních transpozic , tedy transpozic ve tvaru Jakákoli transpozice může být reprezentována jako součin sousedních transpozic. $(k~~k+1).$

Rozklad permutace na součin transpozic lze získat např. tak, že permutaci vypíšeme jako součin různých cyklů a cykly o délce 3 a více pak iterativně rozložíme na součin transpozice a cyklus o jeden kratší. :

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z)

Symetrická grupa je Coxeterova grupa v tom smyslu, že je generována prvky řádu 2 (sousední transpozice) a všechny vztahy mají určitou formu.

Jeden z hlavních výsledků elementární teorie symetrických grup tvrdí, že buď všechny rozklady dané permutace na transpozice mají sudý počet transpozic, nebo všechny rozklady mají lichý počet transpozic [6] . To umožňuje, aby parita permutace byla dobře definovanou funkcí.

Viz také

Loop sort je třídicí algoritmus založený na myšlence, že pole lze rozložit na smyčky, které lze jednotlivě procházet a získat setříděné pole.
Cykly a pevné body
Cyklické permutace celých čísel
Cyklické permutace v proteinech

Poznámka

↑ Bogart, 1990 , s. 486.
↑ Gross, 2008 , str. 29.
↑ Fraleigh, 1993 , s. 103.
↑ Sagan, 1991 , str. 2.
↑ Rotman, 2006 , s. 118, prop. 2.35.
↑ Rotman, 2006 , s. 122.

Literatura

Anderson M., Feil T. . První kurz abstraktní algebry. 2. vydání. — Boca Raton: Chapman & Hall/CRC, 2005. — 696 s. — ISBN 1-58488-515-7 .
Fraleigh J. První kurz abstraktní algebry. 5. vydání. - četba: Addison-Wesley, 1993. - 576 s. - ISBN 978-0-201-53467-2 .
Rotman J.J. První kurz abstraktní algebry s aplikacemi. 3. vydání. - Upper Saddle River: Prentice Hall, 2006. - 581 s. — ISBN 978-0-13-186267-8 .
Sagan B.E. Symetrická skupina: Reprezentace, kombinatorické algoritmy a symetrické funkce . - Belmont: Wadsworth, 1991. - 197 s. — ISBN 978-0-534-15540-7 .
Bogart K.P. Úvodní kombinatorika. 2. vydání. - San Diego: Harcourt, Brace, Jovanovich, 1990. - 622 s. — ISBN 0-15-541576-X .
Gross J.L. Kombinační metody s počítačovými aplikacemi. - Boca Raton: Chapman & Hall/CRC, 2008. - xvii + 644 s. — ISBN 978-1-58488-743-0 .

Odkazy

Permutace jako produkt transpozic