Cykelnotatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

Externe link[bewerken]