Cykelnotatie

In de combinatoriek, een deelgebied van de wiskunde, is de cykelnotatie een nuttige conventie voor het uitschrijven van een permutatie in termen van haar constituerende cykels

Definitie

Laat ${\displaystyle S}$ een eindige verzameling zijn en laat

${\displaystyle a_{1},\ldots ,a_{k},\quad k\geq 2}$

verschillende elementen van ${\displaystyle S}$ zijn. De uitdrukking

${\displaystyle (a_{1}\ \ldots \ a_{k})}$

duidt de cykel σ aan. De groepsactie van σ is

${\displaystyle a_{1}\mapsto a_{2}\mapsto a_{3}\ldots a_{k}\mapsto a_{1}.}$

Voor elke index i,

${\displaystyle \sigma (a_{i})=a_{i+1},}$

waar ${\displaystyle a_{k+1}}$ gelijk is aan ${\displaystyle a_{1}}$.

Er zijn ${\displaystyle k}$ verschillende uitdrukkingen voor dezelfde cykel; De onderstaande uitdrukkingen zijn allen een weergave van dezelfde cykel:

${\displaystyle (a_{1}\ a_{2}\ a_{3}\ \ldots \ a_{k})=(a_{2}\ a_{3}\ \ldots \ a_{k}\ a_{1})=\cdots =(a_{k}\ a_{1}\ a_{2}\ \ldots \ a_{k-1}).\,}$

Een 1-element cykel heeft dezelfde betekenis als de identiteitspermutatie en wordt daarom weggelaten. Het is gebruikelijk om de identiteitspermutatie simpelweg uit te drukken als ${\displaystyle ()\,}$.

Permutatie als product van disjuncte cykels

Laat ${\displaystyle \pi }$ een permutatie van ${\displaystyle S}$ zijn en laat

${\displaystyle S_{1},\ldots ,S_{k}\subset S,\quad k\in \mathbb {N} }$

de banen van ${\displaystyle \pi }$ zijn met meer dan 1 element. Voor elke ${\displaystyle j=1,\ldots ,k}$ laat ${\displaystyle n_{j}}$ de kardinaliteit van ${\displaystyle S_{j}}$ aanduiden. Kies dus een ${\displaystyle a_{1,j}\in S_{j}}$ en definieer

${\displaystyle a_{i+1,j}=\pi (a_{i,j}),\quad i\in \mathbb {N} .\,}$

Men kan nu ${\displaystyle \pi }$ uitdrukken als een product van disjuncte cykels, namelijk

${\displaystyle \pi =(a_{1,1}\ \ldots a_{n_{1},1})(a_{1,2}\ \ldots \ a_{n_{2},2})\ldots (a_{1,k}\ \ldots \ a_{n_{k},k}).\,}$

Voorbeeld

Er zijn 24 elementen in de symmetrische groep ${\displaystyle \{1,2,3,4\}}$. Deze kunnen geschreven worden in de cykelnotatie en gegroepeerd worden volgens hun conjugatieklassen:

${\displaystyle ()\,}$

${\displaystyle (12),\;(13),\;(14),\;(23),\;(24),\;(34)}$ (transposities)

${\displaystyle (123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)}$

${\displaystyle (12)(34),\;(13)(24),\;(14)(23)}$

${\displaystyle (1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)}$

Zie ook

• Cyclische permutatie

Externe link

• (en) https://planetmath.org/cyclenotation