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 $S$$S$ een eindige verzameling zijn en laat

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

verschillende elementen van $S$$S$ zijn. De uitdrukking

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

duidt de cykel σ aan. De groepsactie van σ is

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

Voor elke index i,

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

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

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

$(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}).\,$$(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 $()\,$$()\,$.

Permutatie als een product van cykels

Laat $\pi$$\pi$ een permutatie van $S$$S$ zijn en laat

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

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

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

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

$\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}).\,$$\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 $\{1,2,3,4\}$$\{1,2,3,4\}$. Deze kunnen geschreven worden in de cykelnotatie en gegroepeerd worden volgens hun conjugatieklassen:

$()\,$$()\,$

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

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

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

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

Zie ook

• Cyclische permutatie

Externe link

• (en) Cykelnotatie op PlanetMath