Utente:Grasso Luigi/sandbox4/Lemma di Burnside

Il lemma di Burnside, a volte detto teorema del conteggio di Burnside, lemma di Cauchy–Frobenius, teorema del numero delle orbite, o lemma di Frobenius, è un risultato della teoria dei gruppi che è spesso utile nel tenere conto della simmetria quando si contano oggetti matematici. I suoi eponimi si basano sui matematici William Burnside, George Pólya, Augustin-Louis Cauchy e Ferdinand Georg Frobenius. Il risultato non è dovuto allo stesso Burnside, che si limita a citarlo nel suo libro On the Theory of Groups of Finite Order, attribuendolo invece a Frobenius.

Il lemma di Burnside conta le "orbite" dell'azione di un gruppo G su un insieme X, che è la stessa cosa che contare oggetti distinti tenendo conto di una simmetria. Altri modi per dirlo sono contare oggetti distinti rispetto una data relazione di equivalenza R, o contare gli oggetti che sono in forma canonica.

Punti fissi di un G-set X finito

Consideriamo un gruppo finito G - set ' 'X' '. In particolare un'azione sinistra su X:

$${\begin{alignedat}{4}\alpha :\;&&G\times X&&\;\to \;&X\\&&(g,\ x)&&\;\mapsto \;&g\cdot x\end{alignedat}}$$

con la relazione binaria naturale su X

$x\sim y\iff \exists g\in G:g\cdot x=y\,\,\forall x,y\in X$

che partiziona l'insieme X in insiemi digiunti ciascuno detto orbita di x, dove x è l'elemento rappresentativo. Da notare che tali classi di equivalenza sono dei sottoinsiemi e non dei sottogruppi di $G$. Nel seguito denotiamo con $n_{O}=\left|X/G\right|$ il numero di orbite distinte, e definiamo l'insieme degli elementi rappresentativi delle singole classi come:

$\{x_{1},\ x_{2}\ldots ,x_{n_{O}}\}\subseteq X$

Allora il corrispondente stabilizzatore di x, è il sottogruppo di tutti gli g che lasciano x invariato $g\cdot x=x\,\forall g\in G$. Se, per un certo x fissato, si verifica

$O_{G}(x)=\{x\}\quad |O_{G}(x)|=1$

$G_{x}=G\quad |G_{x}|=|G|$

diremo x punto fisso per G-set X. Data questa definizione ha senso definire l'insieme dei punti fissi dell'azione:

$Fix_{X}(\cdot G)=\{(g,\ x)\in G\times X|g\cdot x=x\}\subseteq X$

Fissiamo un elemento g di G, con il simbolo X^g denotiamo l'insieme degli elementi in X che sono fissati da g (anche detti essere invarianti a sinistra per g), riportiamo pure la definizione analoga degli g che sono fissati o invarianti a sinistra per x (sottogruppo stabilizzatore), cioè:

$X^{g}=Fix(g)=\{x\in X\ |\ g\cdot x=x,\ g\in G\}\subseteq X$

$G_{x}=Sta(x)=\{g\in G|\ g\cdot x=x,\ x\in X\}\}\leq G$

da notare la differenza tra l'insieme dei punti fissi di X rispetto ad un g dato e il sottogruppo stabilizzatore di G per un x dato, cioè gli elementi g di G che lasciano x invariato. Allora la cardinalita dell'insieme dei punti fissi si può esprimere con due espressioni equivalenti

$|Fix_{X}(\cdot G)|=\sum _{g\in G}|X^{g}|=\sum _{x\in X}|G_{x}|$.

Enunciato

Il lemma di Burnside consiste nella seguente formula per il numero di orbite, che abbiamo denotato |X/G|:

Lemma di Burnside (1897) - Frobenius (1887) — 

G-set X finito $\,\implies \,\left|X/G\right|\ =\ {\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.$

Quindi il numero di orbite (un numero naturale o +∞) è uguale alla media di punti fissati da un elemento g di G (con l'ordine di G che è anche un numero naturale o infinito). Se G è infinito, la divisione per |G| potrebbe non essere ben definita; in questi casi vale la seguente definizione in aritmetica cardinale:

$$|G||X/G|=\sum _{g\in G}|X^{g}|.$$

Dimostrazione

Il primo passo nella dimostrazione del lemma è già stato visto e consiste nell'esplicitare la somma sugli elementi del gruppo g ∈ G come somma equivalente sull'insieme degli elementi x ∈ X:

$\sum _{g\in G}|X^{g}|=\sum _{x\in X}|G_{x}|.$

Se consideriamo l'orbita $O_{G}(x)$ formata da $|O_{G}(x)|$ elementi di X, ogni suo punto $y\in O_{g}(x)$ è fissato dagli elementi g del suo stabilizzatore $G_{y}$. Il teorema orbita-stabilizzatore dice che esiste una biiezione naturale per ogni $x\in X$ tra l'orbita di x, $G\cdot x=O_{G}(x)=\{y\in X|g\cdot x=y,\ g\in G\}\subseteq X$, e l'insieme dei coset sx $G/\sim _{\cdot G_{x}}$ del suo sottogruppo stabilizzatore $G_{x}$ o in notazione $|O_{G}(x)|=[G\,:\,G_{x}]$. Allora si ha pure:

$g\cdot x=y\implies g\ G_{x}\ g^{-1}=G_{y}$

cioè sono sottogruppi coniugati con $|G_{x}|=|G_{y}|$ e con stesso indice $[G\,:\,G_{x}]=[G\,:\,G_{y}]$. Inoltre per il teorema di Lagrange fissato un elemento rappresentativo dell'orbita si ha:

$|G\cdot x|=|O_{G}(x)|=[G\,:\,G_{x}]=|G|/|G_{x}|\implies |G|=[O_{G}(x)||G_{x}|.$

Quindi ogni orbita dell'azione G su X ha $|G|$ punti fissi, per cui la sommatoria sull'insieme X può anche scriversi

$\sum _{x\in X}|G_{x}|=\sum _{i=1}^{n_{O}}\sum _{y\in O_{G}(x_{i})}|Gy|=\sum _{i=1}^{n_{O}}|O_{G}(x_{i})|\ |G_{x_{i}}|=\sum _{i=1}^{n_{O}}|G|=n_{O}\,|G|=|X/G|\,|G|$

ottenendo la tesi

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|={\frac {1}{|G|}}\sum _{g\in G}|Fix(g)|.$

Questa dimostrazione è essenzialmente anche la dimostrazione dell'equazione di classe, semplicemente considerando l'azione di coniugio di G su se stesso (X = G), g.x = gxg⁻¹, nel qual caso G_x dicesi centralizzatore di x in G.

Esempi di applicazioni

Colorare gli n-vertici di un poligono con q-colori distinti

D₃

Consideriamo una collana con tre perle di due colori diversi, oppure un vettore di tre bit (ogni bit può assumere solo i valori 0 ed 1). Vogliamo conoscere le configurazioni non equivalenti quando muoviamo la collana nello spazio o shiftiamo i bit a sinistra.

Teoricamente equivale a considerare il gruppo diedrale $D_{3}$ applicato ad un triangolo in cui i tre vertici sono punti con due colori diversi. Cioè analizziamo il semplice caso $q=2,\ n=3$.

Se consideriano il triangolo fisso, allora ogni punto dei 3 vertici può avere solo due distinti colori, rosso (r) e bianco (w) ad esempio. Per calcolare le configurazioni usiamo il calcolo combinatorio come si può notare dalla prima tabella che segue. Quindi le configurazioni fisse sono date dalle disposizioni con ripetizione di 2 oggetti di classe 3 cioè $q^{n}\ =\ 2^{3}\ =\ 8$, come si nota dall'immagine sulla destra. Adesso supponiamo di effettuare operazioni di movimento e notiamo che certe configurazioni sono indistinguibili. Tali operazioni sono quelle del gruppo $\color {Blue}S_{3}$ formato dai 6 elementi $\{\pi _{3},\pi _{3}^{2},\pi _{3}^{3},\sigma ',\sigma {''},\sigma {'''}\}$ che agiscono sull'insieme dei vertici $X=\{1,2,3\}$ del triangolo. Adesso vediamo come $S_{3}$ agisce sull'insieme delle configurazioni dei triangoli con vertici a due colori che denotiamo $S=\{C_{1},C_{2},C_{3},C_{4},C_{5},C_{6},C_{7},C_{8}\}$:

${\overline {\pi }}_{3}^{3}=id={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\end{pmatrix}}=(C_{1})(C_{2})(C_{3})(C_{4})(C_{5})(C_{6})(C_{7})(C_{8})$

quindi l'elemento neutro lascia tutte le configurazioni invariate, cioè $Fix\left({\overline {\pi }}_{3}^{3}\right)=8$.

${\overline {\pi }}_{3}={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{4}&C_{2}&C_{3}&C_{7}&C_{5}&C_{6}&C_{8}\end{pmatrix}}=(C_{1})(C_{2}\ C_{4}\ C_{3})(C_{5}\ C_{7}\ C_{6})(C_{8})$

come si nota tale operazione lascia due configurazioni invariate, cioè $Fix({\overline {\pi }}_{3})=2$. Idem per ${\overline {\pi }}_{3}^{2}$. Per le riflessioni si ottiene:

${\overline {\sigma }}'={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{3}&C_{2}&C_{4}&C_{7}&C_{6}&C_{5}&C_{8}\end{pmatrix}}=(C_{1})(C_{3}\ C_{2})(C_{4})(C_{5}\ C_{7})(C_{6})(C_{8})$

quindi restano 4 configurazioni invariate, cioè $Fix\left({\overline {\sigma }}'\right)=4$. Idem per ${\overline {\sigma }}{''},\ {\overline {\sigma }}{'''}$. Adesso applichiamo il lemma di Burnside per trovare il numero di classi di equivalenza (il numero delle orbite) in cui viene partizionato S dall'azione di G:

$\left|{\frac {S}{G}}\right|={\frac {1}{|G|}}\sum _{g\in G}|S^{g}|={\frac {Fix\left({\overline {\pi }}_{3}^{3}\right)\ +Fix\left({\overline {\pi }}_{3}\right)\ +Fix\left({\overline {\pi }}_{3}^{2}\right)\ +Fix\left({\overline {\sigma }}'\right)\ +Fix\left({\overline {\sigma }}{''}\right)\ +Fix\left({\overline {\sigma }}{'''}\right)}{6}}={\frac {8\ +2\ +2\ +4\ +4\ +4}{6}}={\frac {24}{6}}=4$

come si nota nell'immagine sulla destra ci sono esattamente 4 classi di equivalenza che partizionano l'insieme delle configurazioni possibili S.

Utilizzando la rappresentazione di ciascun elemento di $g\in G$ come cicli digiunti, possiamo costruire il polinomio indice ciclico $P_{G}(x_{1},\ x_{2},\ x_{3})$ per il gruppo $G$ delle permutazioni, come si nota dalla seconda tabella.

Pattern	$(r_{1}\ ,r_{2})$	${P^{'}}_{n,k}={\frac {k!}{r_{1}!\ r_{2}!}}$
$w\ w\ w$	$(3\ ,0)$	$1$
$w\ w\ r$	$(2\ ,1)$	$3$
$w\ r\ r$	$(1\ ,2)$	$3$
$r\ r\ r$	$(0\ ,3)$	$1$
	${\begin{alignedat}{2}{D^{'}}_{n,k}&=n^{k}=\sum _{i=0}^{{C^{'}}_{n,k}-1}={\frac {k!}{r_{{C^{'}}_{n,k}-1-i}!\ r_{i}!}}\\&=1\ +3\ +3\ +1=8=2^{3}\\\end{alignedat}}$

$g\in D_{3}$	$C_{i}\in S$ invarianti	rappresentazione algebrica di $g$
${\pi _{3}}^{3}=(1)(2)(3)$	$2^{3}:\ C_{1},\ldots ,C_{8}$	$x_{1}^{3}$
${\pi _{3}}=(1\ 2\ 3)$	$2:\ C_{1},C_{8}$	$x_{3}$
${\pi _{3}}^{2}=(1\ 3\ 2)$	$2:\ C_{1},C_{8}$	$x_{3}$
${\sigma }{'}=(1\ 2)(3)$	$2^{2}:\ C_{1},C_{4},C_{6},C_{8}$	$x_{2}\ x_{1}$
${\sigma }{''}=(1\ 3)(2)$	$2^{2}:\ C_{1},C_{2},C_{7},C_{8}$	$x_{2}\ x_{1}$
${\sigma }{'''}=(2\ 3)(1)$	$2^{2}:\ C_{1},C_{3},C_{5},C_{8}$	$x_{2}\ x_{1}$
	$P_{G}(x_{1},\ x_{2},\ x_{3})={\frac {x_{1}^{3}\ +3x_{2}x_{1}\ +2x_{3}}{|G|}}$

ricordo che la notazione $x_{l}^{k}$ indica la rappresentazione della struttura ciclica dell'elemento $g\in G$, cioè che vi sono un numero k di l-cicli. Ad esempio $g=(1)(2)(34)(56)(789)$ viene rappresentato algebricamente come $x_{1}^{2}\ x_{2}^{2}\ x_{3}$. Tale polinomio permette di generalizzare a q-colori di $S$ non equivalenti ottenendo:

$P_{G}(q,\ q,\ q)={\frac {q^{3}\ +3\cdot q\cdot q\ +2\cdot q}{6}}={\frac {q^{3}\ +3\ q^{2}\ +2\ q}{6}}=\left|{\frac {S}{G}}\right|$

ed applicandolo al caso di 2-colori si ottiene il risultato visto prima

$P_{G}(2,\ 2,\ 2)={\frac {2^{3}\ +3\cdot 2\cdot 2\ +2\cdot 2}{6}}={\frac {8\ +12\ +4}{6}}={\frac {24}{6}}=4.$

Ponendo il problema su 3-colori si ottiene $|S|=3^{3}=27$ possibili configurazioni che vengono partizionate in

$P_{G}(3,\ 3,\ 3)={\frac {3^{3}\ +3\cdot 3\cdot 3\ +2\cdot 3}{6}}={\frac {27\ +27\ +6}{6}}={\frac {60}{6}}=10.$

classi di equivalenza o numero di orbite.

Adesso possiamo rispondere ai quesiti iniziali: nel caso delle collane con 3 perle considerando le operazioni di rotazione e riflessione abbiamo le classi di equivalenza $cl_{1}=\{rrr\}$, $cl_{2}=\{rrw,rwr,wrr\}$, $cl_{3}=\{wwr,wrw,rww\}$ e $cl_{4}=\{www\}$. Nel caso dei vettori bit di lunghezza 3 considerando solo le operazioni di rotazione abbiamo le classi di equivalenza $cl_{1}=\{000\}$, $cl_{2}=\{001,100,010\}$, $cl_{3}=\{011,110,101\}$ e $cl_{4}=\{111\}$. Quindi stiamo considerando come gruppo $G=A_{3}\leq S_{3}$, e l'insieme $S=\{000,001,010,011,100,101,110,111\}$ su cui agisce shiftando i bit verso sinistra. G agisce su S tramite 3 rotazioni: 0-rotazione lascia tutti e 8 vettori di bit invariati, la 1-rotazione lascia 2 vettori fissi, la 2-rotazione lascia 2 vettori fissi. Allora otteniamo il numero di orbite o classi di equivalenza:

$\left|{\frac {S}{G}}\right|={\frac {1}{3}}(8+2+2)=4$

D₄

Consideriamo una collana con quattro perle con due colori distinti, oppure un vettore di quattro bit . Equivale a considerare il gruppo diedrale $D_{4}$ applicato ad un quadrato i cui i quattro vertici sono punti con due diversi colori.

Se consideriano il quadrato fisso, allora ogni punto dei 4 vertici può avere solo due distinti colori, rosso (r) e bianco (w) ad esempio. Quindi le configurazioni fisse sono $q^{n}\ =\ 2^{4}\ =\ 16$, come si nota dall'immagine sulla destra.

Utilizzando la rappresentazione di ciascun elemento di $g\in G$ come cicli digiunti, possiamo costruire il polinomio indice ciclico $P_{G}(x_{1},\ x_{2},\ x_{3})$ per il gruppo $G$ delle permutazioni:

Pattern	$(r_{1}\ ,r_{2})$	${P^{'}}_{n,k}={\frac {k!}{r_{1}!\ r_{2}!}}$
$w\ w\ w\ w$	$(4\ ,0)$	$1$
$w\ w\ w\ r$	$(3\ ,1)$	$4$
$w\ w\ r\ r$	$(2\ ,2)$	$6$
$w\ r\ r\ r$	$(1\ ,3)$	$4$
$r\ r\ r\ r$	$(0\ ,4)$	$1$
	${\begin{alignedat}{2}{D^{'}}_{n,k}&=n^{k}=\sum _{i=0}^{{C^{'}}_{n,k}-1}={\frac {k!}{r_{{C^{'}}_{n,k}-1-i}!\ r_{i}!}}\\&=1\ +4\ +6\ +4\ +1=16=2^{4}\\\end{alignedat}}$

$g\in D_{4}$	$C_{i}\in S$ invarianti	rappresentazione algebrica di $g$
${\pi _{4}}^{3}=(1)(2)(3)(4)$	$2^{4}:\ C_{1},\ldots ,C_{16}$	$x_{1}^{4}$
${\pi _{4}}=(1\ 2\ 3\ 4)$	$2:\ C_{1},C_{16}$	$x_{4}$
${\pi _{4}}^{2}=(1\ 3)(2\ 4)$	$2^{2}:\ C_{1},C_{10},C_{11},C_{16}$	$x_{2}^{2}$
${\pi _{4}}^{3}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${\sigma }^{1}=(1\ 4)(2\ 3)$	$2^{2}:\ C_{1},C_{7},C_{9},C_{16}$	$x_{2}^{2}$
${\sigma }^{2}=(1\ 2)(3\ 4)$	$2^{2}:\ C_{1},C_{6},C_{8},C_{16}$	$x_{2}^{2}$
${\sigma }^{3}=(1\ 3)(2)(4)$	$2^{3}:\ C_{1},C_{2},C_{4},C_{10},C_{11},C_{12},C_{15},C_{16}$	$x_{1}^{2}\ x_{2}$
${\sigma }^{4}=(1)(2\ 4)(3)$	$2^{3}:\ C_{1},C_{3},C_{5},C_{10},C_{11},C_{12},C_{14},C_{16}$	$x_{1}^{2}\ x_{2}$
	$P_{G}(x_{1},\ x_{2},\ x_{3},\ x_{4})={\frac {x_{1}^{4}\ +2x_{4}\ +3x_{2}^{2}\ +2x_{2}x_{1}^{2}}{|G|}}$

Tale polinomio permette di generalizzare a q-colori di $S$ non equivalenti ottenendo:

$P_{G}(q,\ q,\ q,\ q)={\frac {q^{4}\ +2\cdot q\ +3\cdot q^{2}\ +2\cdot q\cdot q^{2}}{8}}={\frac {q^{4}\ +2\ q^{3}\ +3\ q^{2}\ +2\ q}{8}}=\left|{\frac {S}{G}}\right|$

ed applicandolo al caso di 2-colori si ottiene il risultato visto prima

$P_{G}(2,\ 2,\ 2,\ 2)={\frac {2^{4}\ +2\cdot 2\ +3\cdot 2^{2}\ +2\cdot 2\cdot 2^{2}}{8}}={\frac {16\ +4\ +12\ +16}{8}}={\frac {48}{8}}=6.$

Quindi per vettori di 4 bit, abbiamo $2^{4}=16$ elementi di S; G agisce su S tramite 4 rotazioni; the null rotation leaves all 16 bit vectors unchanged; the 1-rotation and 3-rotation each leave two bit vectors unchanged (0000 and 1111); the 2-rotation leaves 4 bit vectors unchanged (0000, 0101, 1010, and 1111); giving $6={\frac {1}{4}}(16+2+4+2)$. The six distinct necklaces are represented by the strings 0000, 0001, 0011, 0101, 0111, and 1111.

D_n

Generalizzando ad n-vertici, q-colori, supponiamo che la fattorizzazione in numeri interi di $n$ sia:

$n=p_{1}^{k_{1}}\ p_{2}^{k_{2}}\ \cdots \ p_{r}^{k_{r}}\quad D=\left\{p_{1},p_{2},\ldots ,\ p_{r},\ n\right\}$

cioè, $p_{1},p_{2},\ldots ,p_{r}$ sono numeri primi distinti. Con D definiamo l'insieme dei divisori. Adesso richiamiamo la funzione totiente di Eulero

$\varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1)=\varphi (p_{1})\,\varphi (p_{2})\cdots \varphi (p_{r})=\prod _{i=1}^{r}\varphi (p_{i});\quad \varphi (p_{1})=\varphi (1)\,{\overset {def}{=}}\,1$

da notare la definizione di $\varphi (p_{1})$. Quindi una permutazione di ordine $p_{i}$ ammette un numero $n/p_{i}$ di cicli ognuno di lunghezza $p_{i}$. Allora il gruppo ciclico delle sole rotazioni $C_{n}$ ammette il polinomio indice ciclico seguente:

$P_{G}(x_{1},\ x_{2},\cdots ,\ x_{n})={\frac {1}{n}}\left[\varphi (p_{1})x_{p_{1}}^{n/p_{1}}\ +\varphi (p_{2})x_{p_{2}}^{n/p_{2}}\ +\cdots +\varphi (p_{r})x_{p_{r}}^{n/p_{r}}\ +\varphi (n)x_{n}\right]={\frac {1}{n}}\left[\sum _{i=1}^{r}\varphi (p_{i})\ x_{p_{i}}^{n/p_{i}}\ +\varphi (n)x_{n}\right]$

ad esempio $n=4=1\ 2^{2}$ ammette come divisori l'insieme $\{p_{1}^{k_{1}},\ p_{2}^{k_{2}},\ p_{3}^{k_{3}}\}=\{1,\ 2,\ 2^{2}\}$ e quindi il polinomio indice ciclico diventa:

$P_{G}(x_{1},\ x_{2},\ x_{3},\ x_{4})={\frac {1}{4}}\left[\varphi (1)x_{1}^{(4/1)}\ +\varphi (2)x_{2}^{(4/2)}\ +\varphi (2^{2})x_{4}\right]={\frac {1}{4}}\left[x_{1}^{4}\ +x_{2}^{2}\ +2x_{4}\right].$

o nella forma generalizzata q-colori:

$P_{G}(q,\ q,\ q,\ q)={\frac {q^{4}\ +q^{2}\ +2q}{4}}.$

Il gruppo diedrale è come il gruppo ciclico, ma include anche le operazioni di riflessione. Per cui

$P_{G}(x_{1},\ x_{2},\cdots ,\ x_{n})={\frac {1}{2n}}\sum _{i=1}^{r}\varphi (p_{i})\ x_{p_{i}}^{n/p_{i}}\ +{\frac {1}{2n}}\varphi (n)x_{n}+{\begin{cases}{\frac {1}{2n}}n\ x_{1}x_{2}^{(n-1)/2},&n{\mbox{ dispari, }}\\{\frac {1}{2n}}{\frac {n}{2}}\left(x_{1}^{2}x_{2}^{(n-2)/2}+x_{2}^{n/2}\right),&n{\mbox{ pari.}}\end{cases}}$

Ad esempio consideriamo una collana con 17 perle con due colori distinti. Equivale a considerare il gruppo diedrale $D_{17}$ applicato ad un n-agono i cui i 17 vertici sono punti con due diversi colori. Quindi la fattorizzazione e la funzione di eulero diventano:

$n=17=1\cdot 17\quad \varphi (17)=17^{1-1}\ (17-1)=16$

per cui l'insieme dei divisori diventa $\{1,\ 17\}$ ed otteniamo il polinomio

$P_{G}(x_{1},\ x_{2},\cdots ,\ x_{17})={\frac {1}{2\ 17}}\left[\varphi (1)\ x_{1}^{17/1}\ +\varphi (17)\ x_{17}+17\ x_{1}x_{2}^{(17-1)/2}\right]={\frac {x_{1}^{17}\ +16\ x_{17}\ +17\ x_{1}x_{2}^{8}}{34}}\,$

essendo n dispari. Per $n=17,q=2$ si ottengono

$P_{G}(q,\ q,\cdots ,\ q)={\frac {q^{17}\ +17\ q^{9}\ +16\ q}{34}}={\frac {2^{17}\ +17\ 2^{9}\ +16\ 2}{34}}={\frac {2^{16}\ +17\ 2^{8}\ +16}{17}}={\frac {65536\ +4352\ +16}{17}}={\frac {69904}{17}}=4112$

Colorare le 6-facce di un cubo con q-colori distinti

Supponendo di numerare le facce del cubo come nell'immagine accanto, a cui associamo un insieme del tipo $X=\{1,2,3,4,5,6\}$ e considerare l'azione del gruppo simmetrico $S_{6}$ su $X$.

Operazioni dirette o rotazioni

Sia $G^{(R)}\leq S_{6}$ il gruppo delle rotazioni del cubo. L'insieme $\{{C^{(1)}}_{4},\ {C^{(2)}}_{4},\ {C^{(3)}}_{4},\ {C^{(1)}}_{3},\ {C^{(2)}}_{3},\ {C^{(3)}}_{3},\ {C^{(4)}}_{3},\ {C^{(1)}}_{2},\ {C^{(2)}}_{2},\ {C^{(3)}}_{2},\ {C^{(4)}}_{2},\ {C^{(5)}}_{2},\ {C^{(6)}}_{2},\ \}$ sono i sottogruppi di tale gruppo: 3 sottogruppi ciclici di ordine 4, 4 sottogruppi ciclici di ordine 3 e 6 sottogruppi ciclici di ordine 2. Gli elementi sono quindi:

${C^{(1)}}_{4}=\{id,(3\ 5\ 4\ 6),(5\ 6)(3\ 4),(3\ 6\ 4\ 5)\}$

${C^{(2)}}_{4}=\{id,(1\ 6\ 2\ 5),(1\ 2)(5\ 6),(1\ 5\ 2\ 6)\}$

${C^{(3)}}_{4}=\{id,(1\ 3\ 2\ 4),(1\ 2)(3\ 4),(1\ 4\ 2\ 3)\}$

cioè abbiamo rotazioni delle facce di $\pi /2,\ 2\pi /2,\ 3\pi /2$ per un totale di $3\cdot 3=9$ operazioni + 1 operazione che è l'elemento neutro del gruppo,

${C^{(1)}}_{3}=\{id,(1\ 4\ 5)(2\ 3\ 6),(1\ 5\ 4)(2\ 6\ 3)\}$

${C^{(2)}}_{3}=\{id,(1\ 5\ 3)(2\ 6\ 4),(1\ 3\ 5)(2\ 4\ 6)\}$

${C^{(3)}}_{3}=\{id,(1\ 6\ 3)(2\ 5\ 4),(1\ 3\ 6)(2\ 4\ 5)\}$

${C^{(4)}}_{3}=\{id,(1\ 4\ 6)(2\ 3\ 5),(1\ 6\ 4)(2\ 5\ 3)\}$

cioè abbiamo rotazioni delle facce di $2\pi /3,\ 4\pi /3$ per un totale di $2\cdot 4=8$ operazioni.

${C^{(1)}}_{2}=\{id,(3\ 5\ 4\ 6),(5\ 6)(3\ 4),(3\ 6\ 4\ 5)\}$

${C^{(2)}}_{2}=\{id,(1\ 6\ 2\ 5),(1\ 2)(5\ 6),(1\ 5\ 2\ 6)\}$

${C^{(3)}}_{2}=\{id,(1\ 3\ 2\ 4),(1\ 2)(3\ 4),(1\ 4\ 2\ 3)\}$

${C^{(4)}}_{2}=\{id,(3\ 5\ 4\ 6),(5\ 6)(3\ 4),(3\ 6\ 4\ 5)\}$

${C^{(5)}}_{2}=\{id,(1\ 6\ 2\ 5),(1\ 2)(5\ 6),(1\ 5\ 2\ 6)\}$

${C^{(6)}}_{2}=\{id,(1\ 3\ 2\ 4),(1\ 2)(3\ 4),(1\ 4\ 2\ 3)\}$

cioè abbiamo rotazioni delle facce di $\pi$ per un totale di 6 operazioni.

Fatta questa premessa, ci poniamo il problema di conoscere il numero di configurazioni a 2-colori delle facce di un cubo distinte per operazioni di rotazioni.

Sia S l'insieme con $|S|=q^{f}=2^{6}=64$ elementi che sono cubi con facce a soli 2-colori in una particolare orientazione o configurazione, di cui la tabella seguente indica i particolari del calcolo.

Adesso vediamo come il gruppo delle rotazioni $G_{R}\leq S_{6}$ agisce sull'insieme delle configurazioni del cubo con facce a due colori che denotiamo $S=\{C_{1},\ C_{2},\ \ldots ,\ C_{64}\}$. Allora due elementi di S appartengono alla stessa orbita proprio quando l'uno è semplicemente una rotazione dell'altro. Il numero di colorazioni rotazionalmente distinte è quindi uguale al numero di orbite e può essere trovato contando le dimensioni degli set fisso per i 24 elementi di G.

l'dentità lascia tutti 2⁶ elementi di X uguali

• six 90-degree face rotations, each of which leaves 3³ of the elements of X unchanged
• three 180-degree face rotations, each of which leaves 3⁴ of the elements of X unchanged
• eight 120-degree vertex rotations, each of which leaves 3² of the elements of X unchanged
• six 180-degree edge rotations, each of which leaves 3³ of the elements of X unchanged

Pattern	$(r_{1}\ ,r_{2})$	${P^{'}}_{n,k}={\frac {k!}{r_{1}!\ r_{2}!}}$
$w\ w\ w\ w\ w\ w$	$(6\ ,0)$	$1$
$w\ w\ w\ w\ w\ r$	$(5\ ,1)$	$6$
$w\ w\ w\ w\ r\ r$	$(4\ ,2)$	$15$
$w\ w\ w\ r\ r\ r$	$(3\ ,3)$	$20$
$w\ w\ r\ r\ r\ r$	$(2\ ,4)$	$15$
$w\ r\ r\ r\ r\ r$	$(1\ 5)$	$6$
$r\ r\ r\ r\ r\ r$	$(0\ ,6)$	$1$
	${\begin{alignedat}{2}{D^{'}}_{n,k}&=n^{k}=\sum _{i=0}^{{C^{'}}_{n,k}-1}={\frac {k!}{r_{{C^{'}}_{n,k}-1-i}!\ r_{i}!}}\\&=1\ +6\ +15\ +20\ +15\ +6\ +1=64=2^{6}\\\end{alignedat}}$

$g\in D_{6}$	$C_{i}\in S$ invarianti	rappresentazione algebrica di $g$
$id=(1)(2)(3)(4)(5)(6)$	$2^{6}:\ C_{1},\ldots ,C_{64}$	$x_{1}^{6}$
$(3\ 5\ 4\ 6),(3\ 6\ 4\ 5)$	$2^{3}:\ C_{1},C_{16}$	$2x_{1}^{2}x_{4}$
$(1\ 6\ 2\ 5),(1\ 5\ 2\ 6)$	$2^{3}:\ C_{1},C_{16}$	$2x_{1}^{2}x_{4}$
$(1\ 3\ 2\ 4),(1\ 4\ 2\ 3)$	$2^{3}:\ C_{1},C_{16}$	$2x_{1}^{2}x_{4}$
$(3\ 4)(5\ 6),(1\ 2)(5\ 6),$ $(1\ 2)(3\ 4)$	$2^{3}:\ C_{1},C_{16}$	$3x_{1}^{2}x_{2}^{2}$
${C_{4}^{3}}^{3}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${C_{3}}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${C_{3}}^{2}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${C_{2}}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${\pi _{6}}^{5}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${\pi _{6}}^{4}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
${\pi _{6}}^{5}=(1\ 4\ 3\ 2)$	$2:\ C_{1},C_{16}$	$x_{4}$
	${\begin{alignedat}{2}P_{G}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})&=\\&={\frac {x_{1}^{6}\ +6x_{1}^{2}x_{4}\ +3x_{1}^{2}x_{2}^{2}\ +8x_{3}^{2}\ +6x_{2}^{3}}{|G|}}\\\end{alignedat}}$

Tale polinomio permette di generalizzare a q-colori di $S$ non equivalenti ottenendo:

$P_{G}(q,\ q,\ q,\ q,\ q,\ q)={\frac {q^{6}\ +6q^{2}q\ +3q^{2}q^{2}\ +8q^{2}\ +6q^{3}}{|G|}}\ =\ {\frac {1}{24}}\left(q^{6}\ +3\ q^{4}+12\ q^{3}+8\ q^{2}\right)=\left|{\frac {S}{G}}\right|$

Cubo con 3 facce con colori diversi

Nel caso a 3-colori, calcoliamo prima il numero di configurazioni dell'insieme S con $|S|=q^{f}=3^{6}=729$ elementi che rappresentano le facce a 3-colori di un cubo in una particolare orientazione (configurazioni), e sia G il gruppo delle rotazioni che agisce su S. A detailed examination of these automorphisms may be found here. facce di un cubo distinte per operazioni di rotazioni Applicando il lemma di Burnside si ottiene:

${\frac {1}{24}}\left(3^{6}\ +3\cdot 3^{4}\ +(6\cdot 3^{3}+6\cdot 3^{3})\ +8\cdot 3^{2}\ \right)=57.$

che indica 57 classi di equivalenza quando facciamo agire il gruppo G delle 24 rotazioni sull'insieme $S$ delle configurazioni delle facce di un cubo in tre colori.

Operazioni dirette (rotazioni) ed inverse (riflessioni e rotoriflessioni)

Con ragionamenti analoghi, possiamo ricavare i sottogruppi delle simmetrie inverse del cubo. Ottenendo il polinomio indice ciclico per tutte le 48 operazioni:

${\begin{alignedat}{2}P_{G}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})&=\\&={\frac {x_{1}^{6}\ +6x_{1}^{2}x_{4}\ +3x_{1}^{2}x_{2}^{2}\ +8x_{3}^{2}\ +6x_{2}^{3}}{|G|}}+{\frac {x_{2}^{3}\ +3x_{1}^{4}x_{2}\ +6x_{1}^{2}x_{2}^{2}\ +6x_{2}x_{4}\ +8x_{6}}{|G|}}\\&={\frac {x_{1}^{6}\ +6x_{1}^{2}x_{4}\ +3x_{1}^{4}x_{2}\ +9x_{1}^{2}x_{2}^{2}\ +7x_{2}^{3}\ +6x_{2}x_{4}\ +8x_{3}^{2}\ +8x_{6}}{|G|}}\\\end{alignedat}}$

e generalizzando:

$P_{G}(q,q,q,q,q,q)={\frac {q^{6}\ +3q^{5}\ +9q^{4}\ +13q^{3}\ +14q^{2}\ +8q}{|G|}}$

nel caso 2-colori si ottengono sempre

$P_{G}(2,2,2,2,2,2)={\frac {2^{6}\ +3\ 2^{5}\ +9\ 2^{4}\ +13\ 2^{3}\ +14\ 2^{2}\ +8\ 2}{48}}={\frac {20\ +18\ +22}{6}}={\frac {60}{6}}=10$

classi di equivalenza in cui viene partizionato $S$.

Metodo alternativo

Burnside's Lemma counts distinct objects, but it doesn't generate them. In general, combinatorial generation with isomorph rejection considers the same |G| actions, g, on the same |X| objects, x. But instead of checking that g.x=x, it checks that g.x has not already been generated. One way to accomplish this is by checking that g.x is not lexicographically less than x, using the lexicographically least member of each equivalence class as the class representative. Counting the objects generated with an isomorph-rejection technique such as this provides a way of checking that Burnside's Lemma was correctly applied.

Teorici del lemma

William Burnside stated and proved this lemma, attributing it to Frobenius, in his 1897 book on finite groups. But, even prior to Frobenius, the formula was known to Cauchy in 1845. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy. Consequently, this lemma is sometimes referred to as a lemma that is not Burnside's Misnaming lemmas and theorems is referred to as Stigler's law of eponymy.

Note

Riferimenti

Voci correlate

• Teorema di conteggio di Pólya
• Indice ciclico

Bibliografia

• (DE) Ferdinand Georg Frobenius, Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul, in Crelle's Journal, vol. 101, n. 4, Addison-Wesley, 1887, pp. 273-279, DOI:10.3931/e-rara-18804.
• (EN) William Burnside, Theory of Groups of Finite Order, 1ª ed., Cambridge University Press, 1897.
• (EN) Rotman Joseph, An introduction to the theory of groups, 4ª ed., Springer-Verla, 1995, ISBN 0-387-94285-8.