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

$a_1,\ldots,a_k,\quad k\geq 2$

verschillende elementen van $S$ zijn. De uitdrukking

$(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.$

Voor elke index i,

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

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

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

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$ een permutatie van $S$ zijn en laat

$S_1,\ldots, S_k\subset S,\quad k\in\mathbb{N}$

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

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

Men kan nu $\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}).\,$

Voorbeeld

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

$( )\,$

$(1 2), \;(1 3),\; (1 4),\; (2 3),\; (2 4),\; (3 4)$ (transposities)

$(1 2 3),\; (1 3 2),\; (1 2 4),\; (1 4 2),\; (1 3 4),\; (1 4 3),\; (2 3 4),\; (2 4 3)$

$(1 2)(3 4),\;(1 3)(2 4),\; (1 4)(2 3)$

$(1 2 3 4),\; (1 2 4 3),\; (1 3 2 4),\; (1 3 4 2),\; (1 4 2 3),\; (1 4 3 2)$

Zie ook

• Cyclische permutatie

Externe link

• (en) Cykelnotatie op PlanetMath