Olkoon $A$ äärellinen ei-tyhjä joukko.

• Jos $\alpha$ on $A$:n permutaatio niin $\alpha$:n radat ovat joukot $\set{\alpha^j(x)\mid j\in \Z}$ missä $x\in A$ eli ekvivalenssiluokat kun ekvivalenssirelaationa on $x\sim y$ jos ja vain jos $y=\alpha^j(x)$ jollain $j\in \Z$.
• Joukon $A$:n permutaatio $\alpha$ on sykli jos $\alpha(x_j)=x_{j+1}$, $j=1,2,\ldots,k-1$ ja $\alpha(x_k)=x_1$ missä $x_1,x_2,\ldots,x_k\in A$ (ja $x_i\neq x_j$ kun $i\neq j$) ja $\alpha(x)=x$ kaikilla $x\in A\setminus\{x_1,\ldots,x_k\}$. Syklimerkinnöillä kirjoitetaan $\alpha=\begin{pmatrix} x_1 & x_2 &\dots &x_k\end{pmatrix}$. Tällaisen syklin $\alpha$ pituus on $k$ ja sanotaan, että $\alpha$ on $k$-sykli. Syklin $\alpha$ radat ovat $\{x_1,x_2,\ldots,x_k\}$ ja joukot $\{x\}$ kaikilla $x\in A\setminus\{x_1,\ldots,x_k\}$.
• Jos $\alpha$ on permutaatio niin jokaista sen rataa vastaa sykli ja $\alpha$ voidaan esittää näiden syklien tulona (eli yhdistettynä funktiona) jolloin syklien järjestyksellä ei ole merkitystä ja $\circ$-merkkiä tavallisesti jätetään pois. (Tässä tapauksessa mikään alkio ei esiinny vähintään kahdessa syklissä ja jos näin olisi, niin silloin syklien järjestyksellä on väliä.)

Esimerkki: [+]

Olkoon $$\alpha= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 1 & 3 & 5 & 7 & 6 \end{pmatrix},$$ joukon $A=\{1,2,3,4,5,6,7\}$ permutaatio missä siis tämä merkintätapa tarkoittaa, että esim. $\alpha(1)=2$ ja $\alpha(2)=4$ jne.

Nyt näemme, että $1\mapsto 2 \mapsto 4 \mapsto 3 \mapsto 1$ (eli $\alpha(1)=2$, $\alpha(2)=4$ jne.) ja tästä saamme syklin $\begin{pmatrix} 1 & 2 & 4 & 3\end{pmatrix}$ joka siis on permutaatio $\beta_1$ jolle pätee $\beta_1(1)=2$, $\beta_1(2)=4$, $\beta_1(4)=3$, $\beta_1(3)=1$ ja $\beta(x)=x$ kaikilla $x\in \{5,6,7\}$. Koska $\alpha(5)=5$ saamme syklin $\beta_2=(5)$ jolle siis $\beta_2(x)=x$ kaikilla $x\in A$. Lopuksi näemme, että $6\mapsto 7\mapsto 6$ joten saamme syklin $\beta_3=\begin{pmatrix} 6 & 7\end{pmatrix}$.

Syklinotaatiolla voimme nyt kirjoittaa $$\alpha =\beta_1\beta_3=\begin{pmatrix} 1 & 2 & 4 & 3\end{pmatrix} \begin{pmatrix} 6& 7\end{pmatrix},$$ koska $\beta_2$ on identiteettifunktio. Mutta on myös muita esitystapoja syklien tuloina, esim. $\alpha= \begin{pmatrix} 7 & 6\end{pmatrix}\begin{pmatrix} 4 & 3 & 1 & 2\end{pmatrix}$ tai $\alpha =\begin{pmatrix} 1 &3 \end{pmatrix} \begin{pmatrix} 1 & 4\end{pmatrix} \begin{pmatrix} 1 & 2\end{pmatrix} \begin{pmatrix} 7 & 6\end{pmatrix}$.

Joukot $A_1=\{1,2,4,3\}$, $A_2=\{5\}$ ja $A_3=\{6,7\}$ ovat permutaation $\alpha$ radat.

Esimerkki: Permutaatioiden yhdistäminen [+]

Kun permutaatio $\alpha$ esitetään muodossa $\alpha=(4\; 3\; 2\; 1)(2\; 4)(1\; 2\; 3\; 4)$ niin järjestyksellä on merkitystä koska näillä sykleillä on yhteisiä elementtejä. Voimme esittää permutaation $(1\; 2\; 3\; 4)$ myös seuraavana verkkona:

0,0

1

2

3

4

1

2

3

4

(1 2 3 4)

Kun muodostamme yhdistetyn funktion $\alpha$ meidän täytyy muistaa, että määritelmästä $(f\circ g)(x)=f(g(x))$ seuraa, että meidän täytyy aloittaa oikealta ja saamme seuraavanlaisen verkon:

0,0

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

(1 2 3 4)

(2 4)

(4 3 2 1)

Tästä voimme päätellä, että $\alpha = (1\; 3)$ koska $\alpha\Bigl($ 1 2 3 4$\Bigr )$$= \quad.$

Parilliset ja parittomat permutaatiot [+]

• Jokainen sykli, jonka pituus on $k\geq 2$ voidaan kirjoittaa $k-1$:n $2$-syklin tulona koska $$( x_1 \; x_2 \;\ldots \; x_k)=( x_1 \; x_k) ( x_1 \; x_{k-1}) \ldots ( x_1 \; x_3)( x_1 \; x_2).$$
• Jokainen permutaatio voidaan kirjoittaa $2$-syklien tulona (kunhan perusjoukossa on ainakin kaksi alkiota).
• Jos permutaatio $\alpha$ on kirjoitettu sekä $r$:n että $r'$:n $2$-syklin tulona niin $(-1)^r=(-1)^{r'}$ ja permutaation merkki on $\textrm{sign}(\alpha)=(-1)^r$.
• Jos $\alpha$ on sykli, jonka pituus on $k$ niin $\textrm{sign}(\alpha)=(-1)^{k+1}$.
• Jos $\alpha$ on $n$-alkioisen joukon permutaatio ja $\alpha$:lla on $m$ rataa niin $\textrm{sign}(\alpha)= (-1)^{n-m}$.
• Permutaatio $\alpha$ sanotaan olevan parillinen jos $\textrm{sign}(\alpha)=1$ ja muuten pariton.
• Jos $\alpha$ ja $\beta$ ovat saman joukon permutaatioita niin $\textrm{sign}(\alpha\beta)= \textrm{sign}(\alpha)\textrm{sign}(\beta)$.

Jos $G$ (eli $[G,\bullet]$) on ryhmä niin joukon $G$ ei-tyhjä osajoukko $H$ on $G$:n aliryhmä jos seuraavat ehdot pätevät ja silloin $H$ (eli $[H,\bullet_{|H\times H}]$) on myös ryhmä:

• Jos $a$ ja $b\in H$ niin $a\bullet b\in H$.
• Jos $a\in H$ niin $a^{-1}\in H$.

jos $a\in H$ niin ensimmäisestä ehdosta saamme $a^m\in H$ kaikilla $m\geq 1$ ja koska lisäksi $\card{H}<\infty$ niin on olemassa luvut $j>k\geq 1$ siten, että $a^j=a^k$ (eli sama alkio toistuu) jolloin $a^{j-k}=e$ ja silloin $a^{-1}=a^{j-k-1}$. Jos $j-k-1>0$ niin $a^{-1}\in H$ koska $a^m\in H$ kun $m\geq 1$ ja jos $j-k-1=0$ niin $a^{-1}=e$ jolloin $a=e$ joten $a^{-1} \in H$ koska $a\in H$.

• Ryhmä $G$ on syklinen jos on olemassa $a\in G$ siten, että $G=\set{a^j\mid j\in \Z}$. Silloin sanotaan, että $G$ on $a$:n generoima syklinen ryhmä ja merkitään $G=\langle a\rangle$.
• Jos $G$ on ryhmä ja $a\in G$ niin $\langle a\rangle=\set{ a^{j}\mid j\in Z}$ on $a$:n generoima $G$:n syklinen aliryhmä.

Esimerkki [+]

Ryhmä $[\Z/17\Z \setminus\{[0]_{17}\}, \cdot]$ on syklinen ryhmä koska jos esimerkiksi $a=[3]_{17}$ niin $\set{a^j\mid j=1,2,\ldots,16}=\Z/17\Z \setminus\{[0]_{17}\}$. (Komento mod(3.^(1:16),17) antaa vastaukseksi kaikki luvut $1,\ldots,16$.) Jäännösluokka $[13]_{17}$ taas generoi syklisen aliryhmän $[\{[1]_{17}, [13]_{17}, [16]_{17}, [4]_{17}\} , \cdot]$.

Olkoot $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ kaksi ryhmää ja olkoon $\psi$ funktio: $G_1\to G_2$.

• $\psi$ on homomorfismi jos $\psi(a\bullet_1 b)=\psi(a)\bullet_2 \psi(b)$ kaikilla $a$ ja $b\in G_1$.
• $\psi$ on isomorfismi jos se on homomorfismi ja bijektio (jolloin myös $\psi^{-1}$ on homomorfismi ja siten isomorfismi: $G_2\to G_1$).
• Kaksi ryhmää $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ ovat isomorfiset jos on olemassa isomorfismi: $G_1\to G_2$.

Ryhmät ovat tässä epäolennaisia, oleellista on, että homomorfismi "säilyttää struktuurin"!

Isomorfismi: Esimerkkejä [+]

• Jos $\psi(x)=\log(x)$ niin $\psi:]0,\infty[\to \R$ on isomorfismi kun laskutoimitus joukossa $G_1=]0,\infty[$ on kertolasku ja laskutoimitus joukossa $G_2=\R$ on yhteenlasku, eli $[G_1,\bullet_1]= \bigl []0,\infty[,\cdot\bigr ]$ ja $[G_2,\bullet_2]= [\R,+]$.
• Jos $[G_1,\circ]$ on ryhmä, johon kuuluvat täsmälleen kaikki joukon $A_1$ permutaatiot ja $[G_2,\circ]$ on ryhmä, johon kuuluvat täsmälleen kaikki joukon $A_2$ permutaatiot ja $\card{A_1}=\card{A_2}=m$ niin $G_1$ ja $G_2$ ovat isomorfiset. och sådana grupper betecknas med $S_m$. Tällaiset ryhmät merkitään $S_m$:llä.
• Jokainen ryhmä $[G,\bullet]$ on isomorfinen jonkin joukon permutaatioiden aliryhmän kanssa koska joukoksi voidaan valita $G$ ja isomorfismiksi voidaan valita $\psi(a)(b) = a\bullet b$ mutta tästä ei seuraa että aina olisi hyödyllistä käsitellä ryhmää tällaisena permutaatioryhmänä.
• Jos $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ ovat kaksi syklistä ryhmää ja $\card{G_1}=\card{G_2}$ niin $G_1$ ja $G_2$ ovat isomorfiset eli on olemassa isomorfismi $\psi:G_1\to G_2$ ja tästä syystä syklistä ryhmää, jossa on $m$ alkiota merkitään $C_m$:llä.

Olkoon $G$ ryhmä, $H$ sen aliryhmä ja $a\in G$ (ja $a\bullet b$:n sijasta kirjoitetaan $ab$).

• Joukko $aH=\set{ ab\mid b\in H}$ on $H$:n vasen sivuluokka, joka sisältää $a$:n.
• Joukko $Ha=\set{ ba\mid b\in H}$ on $H$:n oikea sivuluokka, joka sisältää $a$:n.

Sivuluokilla on seuraavia ominaisuuksia (tässä ainoastaan vasemmat sivuluokat):

• $\card{aH}=\card{H}$ kaikilla $a\in G$.
• Jos $a$ ja $b\in G$ niin joko $aH=bH$ tai $aH\cap bH=\emptyset$.
• $\cup_{a\in G} aH= G$.
• Jos $a$ ja $b\in G$ ja $aH=bH$ niin pätee $b^{-1}a\in H$.
• $\card{G} =\card{H}\cdot \card{\set{aH\mid a\in G}}$ ja näin ollen luku $\card{H}$ jakaa luvun $\card {G}$ (kun nämä luvut ovat äärelliset).

Esimerkki [+]

Jos $G=\R^2=\set{(x,y)\mid x,y\in \R}$ ja laskutoimitus on yhteenlasku $(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$ niin $H=\set{(t,2\cdot t)\mid t\in \R}$ on ryhmän $[G,+]$ aliryhmä ja sen sivuluokat ovat joukot $\set{(u+t,v+2\cdot t)\mid t\in \R}$ missä $(u,v)\in G$ eli suoran $y=2x$ suuntaisten suorien pistejoukot.

0,0

H

(u,v)

(u,v)+H

Sivuluokat ekvivalenssiluokkina [+]

Olkoon $G$ ryhmä.

• Jos $G'$ on ryhmä, jonka neutraalialkio on $e'$ ja $\psi:G\to G'$ on homomorfismi niin $H=\set{a\in G\mid \psi(a)= e'}$ ($\psi$:n ydin) on $G$:n aliryhmä.
• $G$:n aliryhmä $H$ on muotoa $\set{a\in G\mid \psi(a)= e'}$ jollakin homomorfismilla $G\to G'$ jos ja vain jos $aH=Ha$ kaikilla $a\in G$ (tai yhtäpitävästi, $aba^{-1}\in H$ kaikilla $a\in G$ ja $b\in H$). Tässä tapauksessa sanotaan, että $H$ on $G$:n normaali aliryhmä.
• Jos $H$ on $G$:n normaali aliryhmä niin sivuluokat (vasen sama kuin oikea) muodostavat tekijäryhmän, jota merkitään $G/H$:lla ja jonka ryhmäoperaatio on $(aH)(bH)= (ab)H$, neutraalialkio $H$ ja käänteisalkio $(aH)^{-1}=a^{-1}H$. Funktio $\psi:G\to G/H$, jonka määritelmä on $\psi(a)= aH$ on homomorfismi, jonka ydin on $H$.

Jäännösluokat tekijäryhminä [+]

Kun $n> 1$ niin $n\Z=\set{n\cdot j\mid j\in \Z}$ on ryhmän $[\Z,+]$ aliryhmä ja koska yhteenlasku on kommutatiivinen laskutoimitus niin $n\Z$ on normaali aliryhmä. Aliryhmän $n\Z$ sivuluokat ovat jäännösluokat modulo $n$ ja ne muodostavat tekijäryhmän $\Z/n\Z$ missä laskutoimitus on yhteenlasku.

Olkoon $G$ ryhmä, joka muodostuu kaikista alla olevan verkon solmujen permutaatiosta $f$ siten, että jos solmujen $x$ ja $y$ välillä on kaari, niin myös solmujen $f(x)$ ja $f(y)$ välillä on kaari.

Koska ainoastaan solmuilla $3$ ja $4$ on $3$ naapuria niin joko $f(3)=3$ ja $f(4)=4$ tai $f(3)=4$ ja $f(4)=3$ (koska ehdosta, että naapurit pysyvät naapureina seuraa, että $x$:llä ja $f(x):llä on yhtä monta naapuria). Solmut$1$ja$2$kuvautuvat solmun$f(3)$naapureille ja samoin solmut$5$ja$6$kuvautuvat solmun$f(4)$ naapureille.

Näin ollen kyseiset permutaatiot ovat: $(1)$, $(1\; 2)$, $(5\; 6)$, $(1\; 2)(5\; 6)$, $(3\; 4)(1\; 5)(2\; 6)$, $(3\; 4)(1\; 6)(2\; 5)$, $(3\; 4)(1\; 5\; 2\; 6)$ ja $(3\; 4)(1\; 6\; 2\; 5)$.

Näytä permutaatio: (1) (1  2) (5  6) (1  2)(5  6) (3  4)(1  5)(2  6) (3  4)(1  6)(2  5) (3  4)(1  5   2  6) (3  4)(1  6   2   5)

Seuraavaksi on laskettava näiden permutaatioiden ratojen pituudet: $$\begin{align*} (1)&: \text{ $6$ rataa, joissa on $1$ alkio.}\\ (1\; 2) \text{ ja } (5\; 6)&: \text{ $4$ rataa, joissa on $1$ alkio, }\text{ $1$ rata, jossa on $2$ alkiota.} \\ (1\; 2)(5\; 6)&: \text{ $2$ rataa, joissa on $1$ alkio, }\text{ $2$ rataa, joissa on $2$ alkiota.}\\ (3\; 4)(1\; 5)(2\; 6) \text{ ja } (3\; 4)(1\; 6)(2\; 5) &: \text{ $3$ rataa, joissa on $2$ alkiota.}\\ (3\; 4)(1\; 5\; 2\; 6) \text{ ja } (3\; 4)(1\; 6\; 2\; 5)&: \text{ $1$ rata, jossa on $2$ alkiota, } \text{ $1$ rata, jossa on $4$ alkiota.} \end{align*}$$ Näin ollen sykli-indeksi tulee olemaan $$\zeta_{G,X}(t_1,t_2,t_3,t_4)=\frac 18\Bigl(t_1^6+t_1^2t_2^2+2t_1^4t_2+2t_2^3+2t_2t_4\Bigr ).$$

• Jos $x\in X$ niin sen rata $G$:n toiminnassa on joukko $Gx=\set{ax\mid a\in G}\subseteq X$.
• Jos $x\in X$ niin sen rata alkion $a\in G$ toiminnassa on joukko $\langle a\rangle$$x$ $=\set{a^jx\mid j\in \Z}\subseteq X$.
• Jos $x\in X$ niin sen kiinnittäjäaliryhmä $G$:n toiminnassa on aliryhmä $G_x=\set{a\in G\mid ax=x}\subseteq G$.
• Jos $a\in G$ niin sen kiintopistejoukko on $X$:n osajoukko $X_a=\set{x\in X\mid ax=x}\subseteq X$.
  (Tätä joukkoa merkitään joskus myös $X^a$:lla tai $F(a)$:lla.)
• Jokaisella $x\in X$ pätee $\abs{Gx}\cdot \abs{G_x} =\abs{G}$. Miksi [+]

  Oletamme, että $G$ on äärellinen ryhmä. Jos $H$ on $G$:n aliryhmä niin $\abs{H}\cdot m=\abs{G}$ missä $m$ on $H$:n (esim. vasempien) sivuluokkien lukumäärä (koska kaikissa sivuluokissa on yhtä monta alkiota kuin $H$:ssa ja niiden unioni on $G$). Koska $G_x$ on $G$:n aliryhmä niin valitsemme $H=G_x$ ja konstruoimme bijektion $\psi$ aliryhmän $G_x$ sivuluokkien joukosta rataan $Gx$ jolloin osoitamme, että $m=\abs{Gx}$ josta seuraa, että $\abs{G}=\abs{G_x}\cdot \abs{Gx}$.

  Määrittelemme $\psi(aG_x)= ax$. Jos $a_1G_x=a_2G_x$ niin pätee $a_2^{-1}a_1\in G_x$ joten $a_2^{-1}a_1x=x$ eli $a_1x=a_2x$ joten $\psi$ on hyvin määritelty.

  Jos $a_1x=a_2x$ niin pätee $a_2^{-1}a_1x=x$ joten $a_2^{-1}a_1\in G_x$, josta seuraa, että $a_1G_x=a_2G_x$ eli $\psi$ on injektio.

  Jos $y\in Gx$ niin on olemassa $a\in G$ siten, että $y=ax$ ja silloin $y=\psi(aG_x)$ josta seuraa, että $\psi$ on surjektio.

• Jos joukossa $X$ määritellään relaatio $\sim$ siten, että $x\sim y$ jos ja vain jos $x=ay$ jollakin $a\in G$ niin $\sim$ on ekvivalenssirelaatio ja ekvivalenssiluokat ovat radat $G$:n toiminnassa eli joukot $Gx$ missä $x\in X$.

Esimerkki: $G_x$, $Gx$ ja $X_a$ [+]

Olkoon $X=\{1,2,3,4\}$ ja $G$ seuraava joukon $X$ permutaatioryhmä: $G=\{(1),(1\;2),(3\; 4),(1\;2)(3\; 4)\}$. Jos nyt $x$ on alkio $3$ niin sen kiinnittäjäaliryhmä $$G_3=\set{a\in G\mid a3=3} = \{(1),(1\; 2)\},$$ ja sen rata $$G3=\{3,3,4,4\}=\{3,4\},$$ Jos lisäksi $a$ on permutaatio $(1\; 2)$ niin sen kiintopistejoukko on $$X_a=\set{x\in X\mid ax=x} = \{3,4\}.$$ Tässä tapauksessa tulos $\card{G}=\card{Gx}\cdot \card{G_x}$ ei sano muuta kuin, että $4=2\cdot 2$.

Permutaation generoima syklinen ryhmä [+]

Olkoon $\alpha= \beta_1\beta_2 \ldots \beta_k$ joukon $X$ permutaatio, missä sykleillä $\beta_j$, $j=1,\ldots k$ ei ole yhteisiä alkoita ja missä syklin $\beta_j$ pituus on $b_j$ ja olkoon $G$ permutaation $\alpha$ generoima syklinen ryhmä. Silloin

• $\beta_j^{r}$ on identiteetti funktio jos ja vain jos $b_j\,|\, r$.
• $\alpha$:n generoiman syklisen ryhmän alkioiden lukumäärä $\card{G}$ on lukujen $b_1,b_2, \ldots,b_k$ pienin yhteinen jaettava koska $\card{G}$ on pienin positiivinen luku $q$ siten, että $\alpha^q$ on identiteettifunktio (eli sama kuin $\alpha^0$).
• Jos $\beta_j=(x_1\; x_2\; \ldots \; x_{b_j})$ ja $1\leq i \leq b_j$ niin $\beta_j^mx_i=\alpha^mx_i=x_i$ kun $0 \leq m<\card{G}$ jos ja vain jos $b_j\,|\, m$, josta seuraa, että kiinnittäjäaliryhmä $G_{x_i}$ on $$G_{x_i}=\set{ \alpha^m\mid m=0,b_j,2\cdot b_j,\ldots,\left (\tfrac{\card{G}}{b_j}-1\right)\cdot b_j}.$$

Ratojen lukumäärä ryhmän toiminnassa (Burnsiden lemma) [+]

Olkoon $G$ (äärellinen) ryhmä, joka toimii joukossa $X$. Silloin ratojen lukumäärä ryhmän $G$ toiminnassa joukossa $X$ on $$\frac 1{\abs{G}}\sum_{a\in G} \abs{X_a}.$$ Miksi? [+]

Olkoon $E=\set{[a,x]\in G\times X\mid ax=x}$. Summeerausjärjestystä vaihtamalla saamme $$\abs{E}= \sum_{a\in G}\card{\set{x\in X\mid ax=x}}= \sum_{x\in X}\card{\set{a\in G\mid ax=x}},$$ joten $\sum_{a\in G}\abs{X_a}= \sum_{x\in X} \abs{G_x}$.
Merkitsemme ratojen joukkoa $X/G$:llä ja ne ovat ekvivalenssiluokkia kun ekvivalenssirelaatio $\sim$ on $x\sim y$ jos ja vain jos $x=ay$ jollain $a\in G$. Eri radoilla ei ole yhteisiä alkioita ja ratojen unioni on $X$ eli $X=\cup_{R\in X/G}R$. Koska $\abs{G_x}= \frac {\abs{G}}{\abs{Gx}}$ ja $Gx$ on rata, johon alkio $x$ kuuluu niin saamme väitteemme seuraavan laskun avulla: $$\sum_{a\in G}\card{X_a}= \sum_{x\in X}\card{G_x}= \sum_{R\in X/G}\,\sum_{x\in R}\card{G_x}= \sum_{R\in X/G}\,\sum_{x\in R} \frac {\card{G}}{\card{Gx}} \\ = \card{G} \sum_{R\in X/G}\, \sum_{x\in R} \frac 1{\card{R}}= \card{G} \sum_{R\in X/G} \frac 1{\card{R}} \sum_{x\in R} 1= \card{G} \sum_{R\in X/G} 1= \card{G}\cdot \card{X/G}.$$         

    

• Joukon $X$ väritys on funktio $\omega:X\to K$ missä $K$ on joukko ''värejä''.
• Jos ryhmä $G$ toimii joukossa $X$, erityisesti jos $G$:n alkiot ovat $X$:n permutaatioita, niin se toimii kaikkien väritysten joukossa $K^X$ siten, että $(a\omega)(x)= \omega(a^{-1}x)$, $a\in G$, $x\in X$.
• Tämä on vasen toiminta koska $$(a(b \omega))(y)= (b\omega)(a^{-1}y)=\omega(b^{-1}a^{-1}y)= \omega((ab)^{-1}y)= ((ab)\omega)(y).$$
• Jos $\Omega\subseteq K^X$ on $X$:n väritysten osajoukko niin $G$ toimii joukossa $\Omega$ mikäli $G\Omega=\Omega$.
• Ryhmän $G$ toiminta väritysten joukossa $\Omega$ määrittelee ekvivalenssirelaation $\Omega$:ssa siten, että $\omega \sim \eta$ jos ja vain jos $\omega =a\eta$ jollakin $a\in G$ ja silloin näitä värityksiä pidetään "samoina".
• Näin ollen $G$:n toiminnan suhteen "erilaisten" väritysten lukumäärä on sama kuin ekvivalenssiluokkien. lukumäärä ja siten sama kuin ratojen lukumäärä $G$:n toiminnassa väritysten joukossa.

Ratojen lukumäärä ryhmän toiminnassa värityksillä [+]

Jos $G$ joukon $X$ permutaatioita ja $G$ toimii joukon $X$ väritysten joukolla $\Omega$, niin G:n toiminnan suhteen ”erilaisten” väritysten lukumäärä eli ratojen lukumäärä on (Burnsiden lemman mukaan) $$\frac 1{\card{G}}\sum_{a\in G} \card{\Omega_a},$$ missä $\Omega_a=\set{\omega\in \Omega\mid a\omega=\omega}$ on niiden väritysten joukko, jotka ovat invariantteja, eli kiintopisteitä, $a$:n toiminnassa.

Jos $a\in G$ ja $a$:n radat ovat $R_{a,1},R_{a,2},\ldots,R_{a,m_a}$ ja jos $\omega$ on $X$:n väritys (eli funktio: $X\to K$ missä $K$ on joukko värejä) niin $a\omega =\omega$ jos ja vain jos $\omega$ on vakio jokaisella radalla $R_{a,j}$, $j=1,\ldots,m_a$. Miksi? [+]

Koska $a\omega=\omega$ niin pätee $a^j\omega=\omega$ kaikilla $j\in \Z$. Jos nyt $x$ ja $y$ kuuluvat samaan $a$:n rataan niin on olemassa luku $j$ siten, että $a^jx=y$ eli $a^{-j}y=x$. Ottaen huomioon miten alkion $a\in G$ toiminta värityksillä on määritelty ja koska $a^j\omega=\omega$ saamme $$\omega(y) = (a^j\omega)(y)= \omega(a^{-j}y) = \omega(x).$$ Jos taas $\omega$ on vakio jokaisella radalla niin $\omega(x)=\omega(a^{-1}x)$ kaikilla $x\in X$. Tästä seuraa, että $\omega(x)=(a\omega)(x)$ kaikilla $x$, eli $\omega = a\omega$.            

     

Olkoon $G$ ryhmä joukon $X$ permutaatioita ja $\zeta_{G,X}(t_1,t_2,\ldots,t_n)$ sen sykli-indeksi. Olkoon $K=\{v_1,v_2,\ldots,v_r\}$ joukko "värejä", joilla $X$:n alkioita väritetään.

Silloin termin $$v_1^{i_1}\cdot v_2^{i_2}\cdot \ldots \cdot v_r^{i_r},$$ kerroin polynomissa $$\zeta_{G,X}(v_1^1+\ldots+v_r^1,v_1^2+\ldots+ v_r^2,\ldots,v_1^n+\ldots +v_r^n)$$ on niiden $X$:n väritysten lukumäärä, joissa väriä $v_j$ käytetään täsmälleen $i_j$ kertaa (eli $\card{\set{x\in X\mid \omega(x)=v_j}}=i_j$) ja jotka eivät ole ekvivalentteja $G$:n toiminnassa.

Jos käytetään $r$ väriä mutta muita rajoituksia ei ole niin $G$:n toiminnassa ei-ekvivalenttien väritysten lukumäärä on $$\zeta_{G,X}(r,r,\ldots,r).$$

Olkoon $X=\{0,1,2,3\}$. Koska joukossa $X$ on $4$ alkiota niin on olemassa $4!=24$ joukon $X$ permutaatiota. Mutta jos $X$:n alkiot ovat vasemmalla olevan verkon solmut ja jos vaadimme permutaatiolta $a$, että jos $x$ ja $y$ ovat naapureita, eli niiden välillä on kaari, niin myös $a(x)$ ja $a(y)$ ovat naapureita (eli vaadimme, että $a$ on verkko-isomorfismi) niin tilanne muuttuu.

Tässä tapauksessa $0$ voi kuvautua mille tahansa solmulle $0$, $1$, $2$ tai $3$. Mutta $a(1)$:n on oltava $a(0)$:n naapuri josta seuraa, että $a(1)=\Mod(a(0)+1,4)$ tai $\Mod(a(0)-1,4)$. Koska $a(2)$ ei saa olla $a(0)$:n naapuri niin $a(2)=\Mod(a(0)+2,4)$ ja samoin $a(3)=\Mod(a(1)+2,4)$.

Toisella tavalla: Verkkoa voi pyörittää "keskipisteen" ympäri $0$, $90$, $180$ tai $270$ astetta tai peilata $x$-akselin, $y$-akselin, suoran $y=x$ tai suoran $y=-x$ suhteen (kun ''keskipiste valitaan origoksi).

Meillä on siis seuraavat permutaatiot syklinotaatiolla: $(0)$, $(1\; 3)$, $(0\; 1\; 2\; 3)$, $(0\; 1)(2\; 3)$, $(0\; 2)(1\; 3)$, $(0\; 2)$, $(0\;3\;2\;1)$ ja $(0\; 3)(1\; 2)$ joista siis $(0)$, $(0\; 1\; 2\; 3)$, $(0\; 2)(1\; 3)$ ja $(0\;3\;2\;1)$ ovat rotaatioita ja $(1\; 3)$, $(0\; 1)(2\; 3)$, $(0\; 2)$ ja $(0\; 3)(1\; 2)$ peilauksia.

Näytä permutaatio: (0) (1  3) (0  1   2  3) (0  1)(2  3) (0  2)(1  3) (0  2) (0    3   2   1) (0  3)(1  2)

Näiden permutaatioiden muodostama ryhmä on ns. diedriryhmä ja sitä merkitään $D_4$:llä (tai $D_{8}$:lla).

Seuraavaksi käytämme Pólyan lausetta laskemaan monellako tavalla voimme värittää solmut niin, että yksi on musta, yksi valkoinen ja kaksi punaista. Lisäksi pidämme kaksi väritystä samanlaisina jos rotaatiolla ja/tai peilauksella saadaan toinen toisesta. (Tähän ei Pólyan lausetta varsinaisesti tarvita koska on vain kaksi vaihtoehtoa: Punaiset solmut ovat joko vierekkäin tai vastakkain.)

Tätä varten meidän pitää ensin laskea ryhmän $D_4$ sykli-indeksi joka saadaan permutaatioiden sykli-indeksien keskiarvona ja permutaation sykli-indeksi on $t_1^{j_1}t_2^{j_1}\ldots t_n^{j_n}$ jos permutaatiolla on $j_k$ rataa, joiden pituus on $k$, $k=1,2,\ldots,n$. Tässä tapauksessa sykli-indeksiksi tulee $$\zeta_{D_4,X}(t_1,t_2,t_3,t_4) = \frac 18\Bigl (t_1^4+t_1^2t_2+t_4+t_2^2+t_2^2+t_1^2t_2+t_4+t_2^2\bigr ).$$ Erilaisten väritysten lukumäärä on nyt termin $mvp^2$ kerroin polynomissa $$\zeta_{D_4,X}(m+v+p,m^2+v^2+p^2, m^3+v^3+p^3,m^4+v^4+p^4),$$ eli polynomissa $$\frac 18(m+v+p)^4+ \frac 14 (m+v+p)^2(m^2+v^2+p^2)\\ +\frac 38(m^2+v^2+p^2)^2+ \frac 14(m^4+v^4+p^4)$$ ja se on $$\frac 18 \cdot \frac{4!}{1!\cdot 1!\cdot 2!} + \frac 14 \cdot 2+0+0=2.$$

Meillä on $3\times 3$-ruudukko ja olemme kirjoittaneet $2$:een ruutuun $\B x$:n, $2$:een $\B o$:n ja $5$ ruutua ovat tyhjinä. Tämä on tehtävissä $\binom 9{2,2,5} =756$:lla eri tavalla jos paperi pidetään paikallaan. Mutta jos voimme kiertää paperia kulman $0$, $\frac \pi 2$, $\pi$ tai $\frac {3\pi}2$ verran keskipisteen ympäri niin näiden vaihtoehtojen lukumäärä pienenee ja jotta voisimme systemaattisella tavalla selvittää montako vaihtoehtoa meillä silloin on niin meidän pitää ensin selvittää miten $\frac \pi 2$ kulman rotaation generoima ryhmä toimii ruudukolla ja erityisesti mikä on tämän toiminnan sykli-indeksi. Eli meidän pitää määrittää erilaisten ratojen pituudet. Tulokset ovat seuraavanlaiset:

• Identiteettifunktiolla (rotaatio $0$) on $9$ rataa, joihin kaikkiin kuuluu $1$ ruutu.
• Kierrolla kulman $\frac \pi 2$ verran on $2$ rataa, joilla molemmilla on $4$ ruutua (toinen sisältää kulmaruudut, toinen niiden välillä olevat ruudut) ja $1$ rata johon kuuluu $1$ ruutu (ruutu keskellä). Sama pätee jos kierretään kulman $\frac {3\pi}2$ verran.
• Jos kiertokulma on $\pi$ niin saamme $4$ rataa, joilla molemmilla on $2$ ruutua (vastakkaiset kulmat ja vastakkaiset ruudut niiden välillä) sekä $1$ rata johon kuuluu $1$ ruutu.

Sykli-indeksiksi saamme näin ollen $$\begin{equation*} \zeta_{G,X}(t_1,t_2,\ldots ,t_9) = \frac 14 \left (t_1^9 +2t_1t_4^2+t_1t_2^4\right ). \end{equation*}$$

Jotta voisimme laskea ei-ekvivalenttien ''väritysten'' lukumäärää korvaamme muuttujan $t_j$ lausekkeella $x^j+o^j+t^j$ ja silloin termin $x^2o^2t^5$ kerroin on ei-ekvivalenttien ''väritysten'' lukumäärä kun meillä $2$ kappaletta $\B x$, $2$ kappaletta $\B o$, ja $5$ kappaletta $\B t$. Termin $x^2o^2t^5$ kerroin lausekkeessa $(x+o+t)^9$ on $\dbinom{9}{2,2,5}$, lausekkeesta $2(x+o+t)(x^4+o^4+t^4)^2$ ei tule yhtään $x^2o^2t^5$-termiä ja termin $x^2o^2t^5$ kerroin lausekkeessa $(x+o+t)(x^2+o^2+t^2)^2$ on termin $x^2o^2t^4$ kerroin lausekkeessa $(x^2+o^2+t^2)^2$ eli $\dbinom 4{1,1,2}$. Vaihtoehtojen lukumääräksi tulee siis $$\frac 14\left(\binom{9}{2,2,5} +0+ \binom 4{1,1,2}\right) = \frac 14\left(756+12\right )=192.$$

Alla olevan verkon solmut on väritetty värityksellä $\omega$ missä $\omega(1)=p$, $\omega(2)=v$, $\omega(3)=p$, $\omega(4)=v$, $\omega(5)=v$ ja $\omega(6)=p$:

Tämän verkon solmujen permutaatiot $a$, jotka ovat sellaisia, että jos solmujen $x$ ja $y$ välillä on kaari, niin myös solmujen $a(x)$ ja $a(y)$ välillä on kaari ovat $(1)$, $(1\; 2)$, $(5\; 6)$, $(1\; 2)(5\; 6)$, $(3\; 4)(1\; 5)(2\; 6)$, $(3\; 4)(1\; 6)(2\; 5)$, $(3\; 4)(1\; 5\; 2\; 6)$ ja $(3\; 4)(1\; 6\; 2\; 5)$. Nämä permutaatiot ovat siis solmujen permutaatioita mutta ne toimivat värityksillä siten, että $a\omega(y)=\omega(a^{-1}y)$.

Näytä väritys $a\omega$ kun $a=$ (1) (1  2) (5  6) (1  2)(5  6) (3  4)(1  5)(2  6) (3  4)(1  6)(2  5) (3  4)(1  5   2  6) (3  4)(1  6   2   5)

Tässä tapauksessa ei ole kovin hankalaa löytää kaikki ne $5$ väritystä, jotka eivät ole ekvivalentteja näiden permutaatioiden toiminnassa ja joissa on $3$ punaista ja $3$ vihreätä solmua mutta seuraavaksi määritämme tämän lukumäärän toisella tavalla:

Burnsiden lemman nojalla ratojen lukumäärä ryhmän $G$ toiminnassa joukossa $\Omega$ on $\frac 1{\card{G}}\sum_{a\in G}\card{\Omega_a}$ missä $\Omega_a=\set{\omega \in \Omega\mid a\omega=\omega}$. Tässä tapauksessa $\Omega$ on verkon solmujen väritykset $\omega$, jotka värittävät kolme solmua punaiseksi ja kolme vihreiksi.

Jos nyt $a$ on esimerkiksi permutaatio $(3\; 4)(1\; 5\; 2\; 6)$ niin $\Omega_a=\emptyset$ koska ehdosta $a\omega=\omega$ seuraa, että $\omega$ saa saman arvon radan $\{3,4\}$ solmuilla ja saman arvon radan $\{1,5,2,6\}$ solmuilla ja tämä on mahdotonta jos vaaditaan, että solmuista kolme ovat punaisia ja kolme vihreitä. Tämän permutaation sykli-indeksi on $t_2t_4$ ja jos $t_2$:n paikalle sijoitetaan $p^2+v^2$ ja $t_4$:n paikalle $p^4+t^4$ saadaan polynomi $(p^2+v^2)(p^4+t^4)$ ja tässä polynomissa ei ole yhtään $p^3v^3$-termiä eli $p^3v^3$:n kerroin on $0$.

Jos sen sijaan tarkastelemme permutaatiota $a^2=(1\; 2)(6\; 5)$ niin silloin seuraavat väritykset muodostavat joukon $\Omega_{a^2}$ koska vaatimus on nyt, että kaikki alkiot samalla radalla saavat saman värin ja tässä tapauksessa radat ovat $\{1,2\}$, $\{5,6\}$, $\{3\}$ ja $\{4\}$:

Permutaation $a^2$ sykli-indeksi on $t_1^2t_2^2$ joten tässäkin tapauksessa $\card{\Omega_{a^2}}$ tulee olemaan termin $p^3v^3$ kerroin polynomissa $$(p+v)^2\cdot (p^2+v^2)^2=v^6+2\cdot p\cdot v^5+3\cdot p^2\cdot v^4+4\cdot p^3\cdot v^3 \\ +3\cdot p^4\cdot v^2+2\cdot p^5\cdot v+p^6.$$

Ryhmän $G$ sykli-indeksi on $\zeta_{G,V}(t_1,t_2,t_4)=\frac 18\Bigl(t_1^6+t_1^2t_2^2+2t_1^4t_2+2t_2^3+2t_2t_4 \Bigr )$ ja termin $p^3v^3$ kerroin polynomissa $\zeta_{G,V}(p+v,p^2+v^2,p^4+v^4)$ on $$\frac 18\left (\frac {6!}{3!\cdot 3!}+ 2\cdot 2 + 2\cdot \left (\frac {4!}{3!\cdot 1!}\cdot 1 + \frac {4!}{3!\cdot 1!}\cdot 1\right )+ 2\cdot 0+ 2\cdot 0\right )= \frac {40}{8}=5.$$