Utente:Grasso Luigi/sandbox4/Indice ciclico

In matematica combinatoria con il termine indice ciclo o indicatore ciclo s'intende un polinomio a più variabili che è strutturato in modo tale che l'informazione su come un gruppo di permutazione agisce su un insieme si ottiene dai coefficienti e dagli esponenti delle variabili. Questo modo compatto di descrivere le informazioni in forma algebrica è utilizzato in enumerazione combinatoria.

Ogni permutazione $\pi$ di un insieme finito di oggetti crea una sua partizione dell'insieme nella forma di ciclo; nel seguito definiamo un indice ciclo monomiale di $\pi$ come un monomio nelle variabili $x_{1},\ x_{2},\ \ldots ,\ x_{n}$ che denota il tipo di ciclo o struttura ciclica di questa partizione e viene utilizzato il simbolo :

$M_{g}\left(x_{1},\ x_{2},\ \ldots ,\ x_{n}\right)=M_{g}$

L'indice ciclo o polinomio indice ciclo di un gruppo di permutazione è la somma dei monomi indice ciclo dei suoi elementi e si denota con scritture equivalenti:

$P_{G}\left(x_{1},\ x_{2},\ \ldots ,\ x_{n}\right)=P\left(G;\ x_{1},\ x_{2},\ \ldots ,\ x_{n}\right)=P_{G}$

Conoscendo l'indice ciclo, possiamo conoscere il numero delle classi di equivalenza dell'insieme di oggetti su cui agisce il gruppo. Questo concetto è alla base del teorema di enumerazione di Pólya. Quindi le operazioni algebriche e differenziali formali su questi polinomi e l'interpretazione combinatoria dei risultati è al centro della teoria delle specie.

Gruppi di permutazioni e azioni

Una trasformazione biiettiva dall'insieme X a X viene detta permutazione di X, l'insieme di tutte le permutazioni di X forma un gruppo avente come operazione la composizionehe di tali trasformazioni, e viene detto gruppo simmetrico di X, e si denota frequentemente Sym(X). Quindi

$S_{x}=\varSigma _{x}={\mbox{Sym }}(X)=\{\pi \ |\pi :X\to X;\ {\mbox{Im }}\pi =X,\ {\mbox{ker }}\pi =\{id\}\}$

che forma un gruppo:

• operazione interna:

${\begin{aligned}\beta \circ \alpha \ :X&\to X\\x\ni X&\mapsto \beta \left(\alpha (x)\right)\in X\\\end{aligned}}$

• associativa

$\alpha \circ (\beta \circ \gamma )\ =\ (\alpha \circ \beta )\circ \gamma \quad \forall \alpha ,\beta ,\gamma \ \in {\mbox{Sym }}(X)$

• elemento neutro

${\begin{aligned}id:X&\to X\\x\ni X&\mapsto id\ (x)=x\quad \forall x\in X\\\end{aligned}}$

• elemento opposto

$\exists '\alpha ^{-1}\ :\alpha \circ \alpha ^{-1}=\alpha ^{-1}\circ \alpha =id\quad \forall \alpha \ \in {\mbox{Sym }}(X)$

Ogni sottogruppo di Sym(X) viene detto gruppo di permutazione di grado |X|. Sia G un gruppo astratto con un omomorfismo di gruppo φ da G a Sym(X). La sua immagine, φ(G), è un gruppo di permutazione. L'omomorfismo di gruppo può essere pensato come un mezzo per consentire al gruppo G di "agire" sull'insieme di oggetti X (utilizzando le permutazioni associate con gli elementi di G). Un tale omomorfismo di gruppo viene detto azione di gruppo e l'immagine di φ viene detta rappresentazione permutazione di G. Un dato gruppo può avere diverse rappresentazioni permutazioni, corrispondenti a diverse azioni.

Supponiamo che G agisce su X (cioè, esiste un'azione di gruppo). Nelle applicazioni combinatorie l'interesse è nel definire l'insieme X; per esempio, contare gli elementi in X e sapere quali strutture potrebbero essere lasciate invariate da G. In questo contesto si lavora con gruppi di permutazioni, quindi in queste applicazioni, il gruppo viene rappresentato da permutazioni ed è necessario specificare un'azione di gruppo. Gli algebristi, invece, sono più interessati al gruppo ed al kernel dell'azione del gruppo, che misura la differenza tra il gruppo in se stesso e la sua rappresentazione come gruppo di permutazione.

Rappresentazione a cicli digiunti

Le permutazioni finite vengono rappresentate come azioni di gruppo sull'insieme $X=\{1,\ 2,\ \ldots ,\ n\}$. Una permutazione ciclica perché "cicla" i numeri viene rappresentata nella notazione detta 2-linea come:

$\pi ={\begin{pmatrix}1&2&3&\ldots &n\\\pi (1)&\pi (2)&\pi (3)&\ldots &\pi (n)\end{pmatrix}}$

mentre nella notazione detta 1-linea come:

$\pi =\left[\pi (1)\ \pi (2)\ \pi (3)\ \ldots \ \pi (n)\right]$

e una terza notazione detta ciclica:

$\pi =\left(\pi (1)\ \pi (2)\ \pi (3)\ \ldots \ \pi (n)\right)$

Ad esempio

$\left({\begin{matrix}1&2&3&4&5\\2&3&4&5&1\end{matrix}}\right)=\left[2\ 3\ 4\ 5\ 1\right]=(1\ 2\ 3\ 4\ 5\ )$

corrisponde ad una bijezione su X = {1, 2, 3, 4, 5} del tipo 1 → 2, 2 → 3, 3 → 4, 4 → 5 and 5 → 1. Questo si può notare dalle colonne della notazione 2-linea. Quando la riga superiore contiene gli elementi di X in un certo ordine, è necessario scrivere solo la seconda riga con la notazione detta 1-linea. Infine in notazione ciclica ogni elemento viene inviato all'elemento alla sua destra, tranne l'ultimo elemento viene inviato al primo (si "cicla" all'inizio), non importa dove inizia un ciclo, quindi

$(1\ 2\ 3\ 4\ 5)=(2\ 3\ 4\ 5\ 1)=(3\ 4\ 5\ 1\ 2)=(4\ 5\ 1\ 2\ 3)=(5\ 1\ 2\ 3\ 4)$

rappresentano la stessa permutazione 5-ciclo. Vedremo che il tipo o struttura ciclica dell'esempio è $\left[5^{1}\right]$.

Non tutte le permutazioni sono cicliche, ma ogni permutazione si decompone in prodotti di cicli disgiunti (cioè che non hanno elementi comuni) in modo unico. Una permutazione può avere punti fissi (elementi che restano costanti nella trasformazione), e sono rappresentati da 1-ciclo. Generalizzando quanto detto all'inizio si ha la stessa notazione vista per la 2-linea e 1-linea mentre la notazione ciclica adesso diventa:

$\pi =\pi _{1}\,\pi _{2}\cdots \pi _{r}=\prod _{i=1}^{r}\,\pi _{i}\qquad$

dove

$\pi _{i}=({p_{1}}^{i}\ {p_{2}}^{i}\ldots {p_{l_{i}}}^{i})\quad i=1,2...r{\mbox{, }}\sum \limits _{i=1}^{r}\,1\ l_{i}=n$ è un generico l_i-ciclo

con l detta lunghezza di un ciclo indica il numero elementi da cui è composto il ciclo, si usa il termine l-ciclo. In questo caso il tipo o struttura ciclica di $\pi$ è $\left[{l_{1}}^{1}\,{l_{2}}^{1}\ldots {l_{r}}^{1}\right]$. Generalizzando a decomposizioni in k_i numero di l_i-cicli, i = 1...r, la notazione ciclica adesso diventa:

$\pi =(\pi _{11}\ \pi _{12}\cdots \pi _{1k_{1}})\,(\pi _{21}\ \pi _{22}\cdots \pi _{2k_{2}})\,\cdots (\pi _{r1}\ \pi _{r2}\cdots \pi _{rk_{r}})=\prod _{i=1}^{r}\,\prod _{j=1}^{k_{i}}\,\pi _{ij}$

dove

$\pi _{ij}=({p_{1}}^{ij}\ {p_{2}}^{ij}\ldots {p_{l_{i}}}^{ij})\quad i=1,2...r\quad j=1,2...k_{i}{\mbox{, }}\sum \limits _{i=1}^{r}\,k_{i}\ l_{i}=n$ è un generico l_i-ciclo con un'occorrenza di k_i volte

e la struttura ciclica di $\pi$ adesso è $\left[{l_{1}}^{k_{1}}\,{l_{2}}^{k_{2}}\ldots {l_{r}}^{k_{r}}\right]$.

Ad esempio:

$\left({\begin{matrix}1&2&3&4&5&6\\2&1&3&5&6&4\end{matrix}}\right)=(1\ 2)(3)(4\ 5\ 6).$

è una permutazione costituita dal prodotto di 3 cicli, un 2-ciclo, un 3-ciclo e un 1-ciclo (punto fisso). Gli elementi che formano i cicli sono sottoinsiemi disgiunti di X e formano una partizione di X. Allora il tipo è $\left[{l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\ {l_{3}}^{k_{3}}\right]=\left[1^{1}\,2^{1}\,3^{1}\right]$

Indice ciclo monomiale

La struttura ciclica di una permutazione si può codificare con un monomio algebrico con variabili dummy in diversi modi: è necessaria una variabile per ciascun l-ciclo distinto per tutti gli r cicli che compaiono nella decomposizione dell'elemento g. In genere usiamo la variabile x_l che corrisponde ad un l-ciclo. La variabile x_l viene elevata al termine k(g) che indica il numero di cicli che hanno lunghezza l. In altre parole l'esponente e l'indice $x_{l}^{k}$ indicano che vi sono un numero k di l-cicli. Allora l'indice ciclo monomiale ha la struttura seguente:

$M_{g}\ (x_{1},x_{2},\ldots ,x_{n})=x_{l_{1}}^{k1}\ x_{l_{2}}^{k2}\cdots x_{l_{r}}^{kr}=\prod _{i=1}^{r}\,x_{l_{i}}^{k_{i}(g)}$

Nell'esempio visto abbiamo 3 cicli di lunghezza differenti, quindi usiamo 3 differenti variabili x₁, x₂ e x₃. Avendo una struttura ciclica $\left[{l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\ {l_{3}}^{k_{3}}\right]=\left[1^{1}\ 2^{1}\ 3^{1}\right]$ allora il rispettivo indice ciclo monomiale associato diventa:

$M_{g}\ (x_{1},x_{2},x_{3})=\prod _{i=1}^{3}\,x_{l_{i}}^{k_{i}(g)}=x_{1}\ x_{2}\ x_{3}$

mentre se consideriamo una permutazione con più cicli come (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) con struttura ciclica [1¹ 2² 4²] si ha:

$M_{g}=x_{1}\ x_{2}^{2}\ x_{4}^{2}$

Definizione

L'indice ciclo di un gruppo di permutazione G abbiamo detto essere la somma degli indici ciclo monomiali di tutte le permutazioni di g in G.

Formalizzando, sia G un gruppo di permutazione di ordine $|G|=m$ e grado o numero di oggetti su cui agisce $|X|=n$. Ogni permutazione g in G ha una decomposizione unica in cicli disgiunti:

$g=\gamma _{1}\,\gamma _{2}\cdots =\prod _{c\in g}\,\gamma _{i}$

dove

$\gamma _{i}=({c_{1}}^{i}\ {c_{2}}^{i}\ldots {c_{|\gamma _{i}|}}^{i})$ è un generico |γ_i|-ciclo

Adesso sia k_i(g) il numero di cicli di g di lunghezza i, con le proprietà

• $\sum _{i=1}^{n}i\,k_{i}(g)\;=n$
• $0\leq k_{i}(g)\leq \lfloor n/i\rfloor$

Supponendo che il tipo g ammetta o-operazioni nel gruppo il generico monomio M_g diventa

$M_{g}\ (x_{1},\ x_{2},\ \ldots ,x_{n})=\prod _{\gamma \in g}\ o\ x_{|\gamma |}=\prod _{i=1}^{n}\ o\ x_{i}^{k_{i}(g)}$

possiamo definire l'indice ciclo P_G di G

$P_{G}\ (x_{1},\ x_{2},\ \ldots ,x_{n})={\frac {1}{|G|}}\sum _{g\in G}\ M_{g}={\frac {1}{|G|}}\sum _{g\in G}\ \left(\prod _{i=1}^{n}\ o_{i}\ x_{i}^{k_{i}(g)}\right)$

Esempi

Sia G il gruppo delle simmetrie di rotazione di un quadrato nel piano di Euclide. Tali simmetrie sono completamente determinate dalle immagini dei soli angoli del quadrato. Numerando con 1, 2, 3 e 4 tali angoli (consecutivamente andando in senso orario) rappresentiamo gli elementi di G come permutazioni dell'insieme X = {1,2,3,4}.

La rappresentazione di G tramite permutazione consiste degli elementi $(1\ 4\ 3\ 2),\ (1\ 3)(2\ 4),\ (1\ 2\ 3\ 4)$ con elemento neutro $e=(1)(2)(3)(4)$ che rappresentano le rotazioni antiorarie $\pi /2,\ 2\cdot \pi /2,\ 3\cdot \pi /2,4\cdot \pi /2$ rispetto al centro di simmetria del quadrato. Da notare che la permutazione identità ha tutti e 4 punti fissi. Come gruppo astratto, G è il gruppo ciclico C₄, e questa rappresentazione viene detta rappresentazione regolare. I monomi indice ciclo sono: x₄, x₂², x₄, x₁⁴. Dunque, l'indice ciclo del gruppo è:

$C_{4}=\ <(1\ 2\ 3\ 4)>\ =\{e,(1\ 2\ 3\ 4),(1\ 3)(2\ 4),(1\ 4\ 3\ 2)\}$

$P_{(C_{4})}\ (x_{1},\ x_{2}\,x_{3},\ x_{4})={\frac {1}{4}}\left(x_{1}^{4}+x_{2}^{2}+2\ x_{4}\right).$

Il gruppo C₄ agisce anche sulle coppie non ordinate di elementi di X in modo naturale. Adesso l'insieme X= {A, B, C, D, E, F} con A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3} ed F = {2,4}. Allora un elemento g trasforma la coppia {x,y} → {x^g, y^g} (dove x^g è l'immagine di x quando applico la permutazione g). Questi elementi possono essere pensati come i lati e le diagonali del quadrato. Se consideriamo come insieme X i lati del grafo completo K₄, allora G= { e, (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F)}, con elemento neutro e = (A)(B)(C)(D)(E)(F). In questo caso il polinomio indice ciclo diventa:

$P_{(C_{4})}\ (x_{1},\ x_{2}\,x_{3},\ x_{4})={\frac {1}{4}}\left(x_{1}^{6}+x_{1}^{2}\ x_{2}^{2}+2\ x_{2}\ x_{4}\right).$

Lo stesso gruppo agisce su coppie ordinate di elementi di X in modo naturale. Allora g trasforma la coppia (x,y) → (x^g, y^g) (in questo caso abbiamo anche coppie della forma (x, x)). Gli elementi di X potrebbero essere pensati come gli archi del digrafo completo D₄ (con anelli ad ogni vertice). L'indice ciclo diventa:

$P_{(C_{4})}\ (x_{1},x_{2},x_{3},x_{4})={\frac {1}{4}}\left(x_{1}^{16}+x_{2}^{8}+2\ x_{4}^{4}\right).$

Tipi di azioni

Come mostra l'esempio sopra, l'indice ciclo dipende dall'azione del gruppo e non dal gruppo astratto. Poiché esistono molte rappresentazioni di permutazioni di un gruppo astratto, è utile disporre di una terminologia per distinguerle. Quando un gruppo astratto è definito in termini di permutazioni, è un gruppo di permutazioni e l'azione del gruppo è l'omomorfismo identità. Questa viene definita “azione naturale”.

Il gruppo simmetrico S₃ nella sua azione naturale ha gli elementi

$S_{3}=\ <(1\ 2\ 3)>\ =\{e,(2\ 3),(1\ 2),(1\ 2\ 3),(1\ 3\ 2),(1\ 3)\}$

e quindi:

$P_{S_{3}}\ ={\frac {1}{6}}\left(x_{1}^{3}\ +3\ x_{1}x_{2}\ +2\ x_{3}\right).$

G-set X transitivo e regolare

Un gruppo di permutazione G-set X si dice transitivo se

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

cioè per ogni coppia di elementi x,y di X vi è almeno un g di G per cui si verifica y = x^g. In altre parole l'insieme X è partizionato da una sola orbita mediante l'azione di g. Allora si parla di un G-set X omogeneo.

Un gruppo transitivo dicesi regolare (o a volte si dice nettamente transitivo) se e solo se l'unica permutazione nel gruppo che ha 1-ciclo (punti fissi) è quella identica. Un gruppo di permutazione transitivo finito G-set X è regolare se e solo se |G| = |X|. Il teorema di Cayley afferma che ogni gruppo astratto ha una rappresentazione regolare descritta dal gruppo che agisce su se stesso (come se fosse l'insieme X) tramite l'operazione di composizione (destra).

Il gruppo ciclico $C_{6}\leq S_{6}$ nella rappresentazione regolare contiene le sei permutazioni:

$C_{6}=\ <(1\ 2\ 3\ 4\ 5\ 6)>\ =\{e,(1\ 2\ 3\ 4\ 5\ 6),(1\ 3\ 5)(2\ 4\ 6),(1\ 4)(2\ 5)(3\ 6)),(1\ 5\ 3)(2\ 6\ 4),(1\ 6\ 5\ 4\ 3\ 2)\}$

Il polinomio indice ciclo diventa:

$P_{C_{6}}\ (x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5},\ x_{6})={\frac {1}{6}}\left(x_{1}^{6}+x_{2}^{3}+2\ x_{3}^{2}+2\ x_{6}\right).$

Mentre se consideriamo il gruppo simmetrico $S_{6}$ si può vedere che ha 10+1 tipi differenti che corrispondono alle sue classi di coniugio, ottenendo:

$P_{S_{6}}\ (x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5},\ x_{6})={\frac {1}{6!}}\left(x_{1}^{6}+15\ x_{1}^{4}\ x_{2}+45\ x_{1}^{2}\ x_{2}^{2}+15\ x_{2}^{3}+40\ x_{1}^{3}\ x_{3}+120\ x_{1}\ x_{2}\ x_{3}+40\ x_{3}^{2}+90\ x_{1}^{2}\ x_{4}+90\ x_{2}\ x_{4}+144\ x_{1}\ x_{5}+120\ x_{6}\right).$

che contiene i sottogruppi di simmetria del cubo $O_{h}\leq S_{6}$ con indice ciclo:

$P_{O_{h}}\ (x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5},\ x_{6})={\frac {1}{24}}\left(x_{1}^{6}+3\ x_{1}^{4}\ x_{2}+9\ x_{1}^{2}\ x_{2}^{2}+7\ x_{2}^{3}+6\ x_{1}^{2}\ x_{4}+8\ x_{3}^{2}+6\ x_{2}\ x_{4}+8\ x_{6}\right).$

Spesso, quando un autore non desidera utilizzare il termine azione di gruppo, al gruppo di permutazione coinvolto viene assegnato un nome che implica quale sia l'azione. I tre esempi seguenti illustrano questo punto.

Gruppo permutazione archi (3v)

Identifichiamo il grafo completo K₃ con un triangolo equilatero nel piano di Euclide. Ciò ci permette di usare il linguaggio geometrico per descrivere talie permutazioni come simmetrie del triangolo equilatero. Ogni permutazione nel gruppo S₃ dei vertici (S₃ nella sua azione naturale, sopra riportata) induce una permutazione degli archi o lati. Gli elementi sono:

• Identità: non si permutano nè vertici e nè lati; il suo monomio è $M_{e}=x_{1}^{3}.$
• Tre riflessioni in an axis passing through a vertex and the midpoint of the opposite edge: fissano un lato (quello non incidente sui vertici) e scambia gli altri due; sono tre monomi per un totale $3\ x_{1}x_{2}.$
• Due rotazioni, oraria di 120°, antioraria di 120°: si crea un ciclo di tre archi; sono 2 monomi per un totale $2\ x_{3}.$

L'indice ciclo del gruppo G^E delle permutazioni lati indotto dalle permutazioni vertici (G^V) è

$P_{G}={\frac {1}{6}}\left(x_{1}^{3}\ +3\ x_{1}x_{2}\ +2\ x_{3}\right).$

In questo caso il grafo completo K₃ è isomorfo al proprio grafo lineare (duale vertice-arco) e quindi il gruppo di permutazione degli archi (G^E) indotto dal gruppo di permutazione dei vertici (G^V) è uguale al gruppo di permutazione dei vertici, cioè ad S₃ con indice ciclo P_(S3). Infatti il numero di archi coincide con il numero dei vertici:

$n_{E}={\binom {3}{2}}=n=n_{V}$

Questo non si verifica per grafi completi su più di tre vertici, poiché questi hanno strettamente più archi:

$n_{E}={\binom {n}{2}}\gg n=n_{V}$

Gruppo permutazione archi (4v)

Si ragiona come nel caso precedente. Il gruppo della permutazione dei vertici (S₄ con azione naturale) e il gruppo indotto delle permutazioni degli archi (S₄ con azione su coppie non ordinate):

• The identity: This permutation maps all vertices (and hence, edges) to themselves, il monomio è $M_{e}=x_{1}^{6}.$
• Six permutations that exchange two vertices: These permutations preserve the edge that connects the two vertices as well as the edge that connects the two vertices not exchanged. The remaining edges form two two-cycles and the contribution is $6\ x_{1}^{2}x_{2}^{2}.$
• Eight permutations that fix one vertex and produce a three-cycle for the three vertices not fixed: These permutations create two three-cycles of edges, one containing those not incident on the vertex, and another one containing those incident on the vertex; the contribution is $8\ x_{3}^{2}.$
• Three permutations that exchange two vertex pairs at the same time: These permutations preserve the two edges that connect the two pairs. The remaining edges form two two-cycles and the contribution is $3\ x_{1}^{2}x_{2}^{2}.$
• Six permutations that cycle the vertices in a four-cycle: These permutations create a four-cycle of edges (those that lie on the cycle) and exchange the remaining two edges; the contribution is $6\ x_{2}x_{4}.$

Possiamo visualizzare i tipi di permutazioni geometricamente come le simmetrie di un tetraedro regolare. Ottenendo la seguente descrizione dei tipi di permutazione.

• The identity. $x_{1}^{6}$
• Reflection in the plane that contains one edge and the midpoint of the edge opposing it. $6\ x_{2}x_{4}.$
• Rotation by 120 degrees about the axis passing through a vertex and the midpoint of the opposite face.$6\ x_{2}x_{4}.$
• Rotation by 180 degrees about the axis connecting the midpoints of two opposite edges.$6\ x_{2}x_{4}.$
• Six rotoreflections by 90 degrees.$6\ x_{2}x_{4}.$

L'indice ciclo del gruppo di permutazioni degli archi G^E di K₄ è:

$P_{G}={\frac {1}{24}}\left(x_{1}^{6}+9\ x_{1}^{2}x_{2}^{2}+8\ x_{3}^{2}+6\ x_{2}x_{4}\right)$

Gruppo permutazione facce (8v)

Numerazione delle facce di un cubo

Consideriamo un cubo ordinario nello spazio e il suo gruppo di simmetrie dirette (automorfismi), che denotiamo $O^{(R)}$. Queste corrispondono alle permutazioni delle 6 facce del cubo o a quello delle 4 diagonali. (In maniera equivalente si possono considerare le permutazioni dei 12 lati o degli 8 vertici). Abbiamo $|O^{(R)}|=24$ elementi od operazioni.

• Elemento neutro $(1)(2)(3)(4)(5)(6)$:

Quindi contribuisce per $x_{1}^{6}.$

• Rotazioni sui 3 assi principali (rette per i centri di due facce opposte) di pi/2, 3 pi/2 Due facce opposte restano fisse e si hanno 4-cicli and create a four-cycle of the faces parallel to the axis of rotation. The contribution is $2\ \cdot 3\ x_{1}^{2}\ x_{4}.$
• Three 180-degree face rotations:

We rotate about the same axis as in the previous case, but now there is no four cycle of the faces parallel to the axis, but rather two two-cycles. The contribution is $3x_{1}^{2}x_{2}^{2}.$

• Eight 120-degree vertex rotations:

This time we rotate about the axis passing through two opposite vertices (the endpoints of a main diagonal). This creates two three-cycles of faces (the faces incident on the same vertex form a cycle). The contribution is $8x_{3}^{2}.$

• Six 180-degree edge rotations:

These edge rotations rotate about the axis that passes through the midpoints of opposite edges not incident on the same face and parallel to each other and exchanges the two faces that are incident on the first edge, the two faces incident on the second edge, and the two faces that share two vertices but no edge with the two edges, i.e. there are three two-cycles and the contribution is $6x_{2}^{3}.$

In conclusione l'indice ciclico del gruppo $O^{(R)}$ è:

$P_{O^{(R)}}={\frac {1}{24}}\left(x_{1}^{6}\ +6\ x_{1}^{2}x_{4}\ +3\ x_{1}^{2}x_{2}^{2}\ +8\ x_{3}^{2}\ +6\ x_{2}^{3}\right)$

Consideriamo il suo gruppo di simmetrie inverse (automorfismi), che denotiamo $O^{(r)}$. Abbiamo $|O^{(r)}|=24$ elementi od operazioni.

• Elemento inversione puntuale rispetto al centro di simmetria $(1\ 2)(3\ 4)(5\ 6)$:

quindi ammette monomio $x_{2}^{3}.$

• Tre riflessioni rispetto ai piani, omettiamo i punti fissi, $(1\ 2),\ (3\ 4),\ (5\ 6)$:

quindi ammette monomio $3\ x_{1}^{4}x_{2}.$

• Sei riflessioni rispetto ai piani, omettiamo punti fissi, $(1\ 4)(2\ 3),\ (1\ 3)(2\ 4),\ (1\ 5)(2\ 6),\ (1\ 6)(2\ 5),\ (3\ 5)(6\ 4),\ (3\ 6)(4\ 5)$:

quindi ammette monomio $6\ x_{1}^{2}x_{2}^{2}.$

• Sei rotoriflessioni

• otto rotoriflessioni

In conclusione l'indice ciclico del gruppo $O^{(r)}$ è:

$P_{O^{(r)}}={\frac {1}{24}}\left(x_{2}^{3}\ +3x_{1}^{4}x_{2}\ +6x_{1}^{2}x_{2}^{2}\ +6x_{2}x_{4}\ +8x_{6}\right)$

ottenendo il gruppo ottaedrale delle 48 operazioni

$O_{h}\ =\ O^{(R)}\ +O^{(r)}$

Indice ciclo di gruppi noti

Gruppo identità E_n

Questo gruppo contiene una permutazione che fissa ogni elemento (questa dev'essere un'azione naturale).

$P_{E_{n}}=x_{1}^{n}.$

Gruppo ciclico C_n

Un gruppo ciclico, C_n è il gruppo delle rotazioni di un n-agono regolare, cioè, n elementi con distanze uguali attorno un cerchio. Il gruppo ha φ(p) elementi di ordine p per ogni divisore p di n, dove φ(p) è la φ-funzione di Eulero, che calcola il numero di numeri naturali minori di p che sono primi con p. Nella rappresentazione regolare di C_n, una permutazione di ordine p ha n/p p-cicli. Supponiamo che la fattorizzazione in numeri interi di $n$ e l'insieme dei divisori D siano:

$n=1^{k_{0}}\ p_{1}^{k_{1}}\ p_{2}^{k_{2}}\ \cdots \ p_{r}^{k_{r}}=\prod _{i=1}^{r}p_{i}^{k_{i}},\quad k_{i}\in \mathbb {Z} \,p_{i}\in \mathbf {P} \qquad D=\left\{1,\ p_{1},\ p_{1}^{2},\ldots ,p_{1}^{k_{1}},\ p_{1}p_{2},\ \ldots ,p_{2},\ \ldots ,\ p_{r},\ \ldots \ n\right\}\quad |D|=\prod _{i=1}^{r}\ (k_{i}+1)$

cioè, $p_{1},p_{2},\ldots ,p_{r}$ sono numeri primi distinti e diversi dall'unità. Applichiamo la funzione totiente di Eulero alla notazione usata:

$\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})=P_{C_{n}}={\frac {1}{n}}\sum _{p|n}\varphi (p)\ x_{p}^{n/p}={\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 C₆ ammette

$6=1^{1}\ 2^{1}\ 3^{1}\ \qquad D=\left\{1,\ 2,\ 3,\ 6\right\}\quad |D|=(k_{1}+1)(k_{2}+1)\ =(1+1)(1+1)\ =4\qquad \varphi (1)=1,\ \varphi (2)=1,\ \varphi (3)=2,\ \varphi (6)=2$

e quindi indice ciclo

$P_{C_{6}}={\frac {1}{6}}\left[\varphi (1)x_{1}^{6/1}\ +\varphi (2)x_{2}^{6/2}\ +\varphi (3)x_{3}^{6/3}\ +\varphi (6)x_{6}\right]={\frac {1}{6}}\left(x_{1}^{6}\ +x_{2}^{3}\ +2\ x_{3}^{2}\ +2\ x_{6}\right)$

Gruppo diedrale D_n

Il gruppo diedrale contiene il gruppo ciclico, ma include pure le operazioni di riflessione. Nell'azione naturale,

$P_{D_{n}}={\frac {1}{2}}P_{C_{n}}+{\begin{cases}{\frac {1}{2}}x_{1}x_{2}^{(n-1)/2},&n=2\ m+1\\{\frac {1}{4}}\left(x_{1}^{2}x_{2}^{(n-2)/2}+x_{2}^{n/2}\right),&n=2\ m\end{cases}}$

$P_{G}(x_{1},\ x_{2},\cdots ,\ x_{n})=P_{D_{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}}$

Gruppo simmetrico S_n

Sappiamo che il tipo di un elemento di $S_{n}$ è sinonimo di una classe di coniugio che denotiamo $Co(g)$, dove g viene detto il suo elemento rappresentativo. Dalla teoria il numero di classi di coniugio coincide con la funzione di partizione dell'intero n, che si denota $p(n)$. Allora l'insieme degli elementi rappresentativi è del tipo:

$\{g_{1},\ g_{2}\ldots ,g_{p(n)}\}\subseteq S_{n}$

inoltre il numero dei coniugati o dello stesso tipo $\left[{1}^{k_{1}}\,{2}^{k_{2}}\ldots {n}^{k_{n}}\right]$del rappresentante g è:

$|Co(g)|={\frac {n!}{\left(k_{1}!\ 1^{k_{1}}\right)\left(k_{2}!\ 2^{k_{2}}\right)\cdots \left(k_{n}!\ n^{k_{n}}\right)}}={\frac {n!}{\left(1^{k_{1}}\ 2^{k_{2}}\cdots \ n^{k_{n}}\right)\left(k_{1}!\ k_{2}!\ \cdots k_{n}!\ \right)}}=n!\,\prod _{i=1}^{n}\,{\frac {1}{i^{k_{i}(g)}\ k_{i}(g)!}}$

questo rappresenta il coefficiente del monomio indice ciclo che abbiamo già definito prima. Questa formula si ottiene partendo dall'insieme $X=\{1,2,\ldots ,n\}$ su cui agisce S_n come segue

• definiamo un insieme S delle possibili permutazioni dei numeri 1 2 ... n, che sappiamo essere di numero $n!$ con le relative parentesi per il tipo di ciclo che rappresentano
• partizioniamo l'insieme di n etichette in sottoinsiemi, dove ci sono $k_{i}$ sottoinsiemi di dimensione i.
• ciascun sottoinsieme genera $i!/i$ i-cicli.
• non distinguiamo cicli della stessa dimensione, ad esempio in S₄ cioè sono permutati da $S_{k_{i}}$. Ottenendo

${\frac {n!}{\prod _{i=1}^{n}(i!)^{k_{i}}}}\ \prod _{i=1}^{n}\left({\frac {i!}{i}}\right)^{k_{i}}\ \prod _{i=1}^{n}{\frac {1}{k_{i}!}}=n!\prod _{i=1}^{n}{\frac {(i!)^{k_{i}}}{(i!)^{k_{i}}\ i^{k_{i}}}}\ {\frac {1}{k_{i}!}}=n!\ \prod _{i=1}^{n}{\frac {1}{i^{k_{i}}k_{i}!}}.$

Quindi ogni singolo tipo ammette monomio indice ciclo:

$M_{g_{c}}(x_{1},x_{2},\ldots ,x_{n})=n!\,\left(\prod _{i=1}^{n}\,{\frac {1}{i^{k_{i}(g_{c})}\ k_{i}(g_{c})!}}\right)\,\prod _{j=1}^{n}\,{x_{j}}^{k_{j}(g_{c})}\quad c=1,2\ldots ,p(n)$

sommando su tutti i tipi o elementi rappresentativi, otteniamo l'indice ciclo del gruppo simmetrico S_n nell'azione naturale:

$P_{S_{n}}(x_{1},x_{2},\ldots ,x_{n})={\frac {1}{n!}}\left(M_{g_{1}}+M_{g_{2}}+\cdots +M_{g_{p(n)}}\right)={\frac {n!}{n!}}\ \sum _{c=1}^{p(n)}\ M_{g_{c}}(x_{1},x_{2},\ldots ,x_{n})=\sum _{c=1}^{p(n)}\ \left[\left(\prod _{i=1}^{n}\,{\frac {1}{i^{k_{i}(g_{c})}\ k_{i}(g_{c})!}}\right)\,\prod _{j=1}^{n}\,{x_{j}}^{k_{j}(g_{c})}\right]$

essendo valida la relazione $\sum _{i=1}^{n}i\ k_{i}(g_{c})=n\quad c=1,2\ldots ,p(n)$.

$P_{S_{n}}(x_{1},x_{2},\ldots ,x_{n})=\sum _{k_{1}+2k_{2}+3k_{3}+\cdots +nk_{n}=n}{\frac {1}{\prod _{j=1}^{n}j^{k_{j}}k_{j}!}}\prod _{j=1}^{n}x_{j}^{k_{j}}$

La formula può essere ulteriormente semplificata se sommiamo gli indici dei cicli su ogni $n$, utilizzando una variabile aggiuntiva $y$ per tenere traccia della dimensione totale dei cicli:

$\sum \limits _{n\geq 1}y^{n}P_{S_{n}}=\sum \limits _{n\geq 1}\sum _{k_{1}+2k_{2}+3k_{3}+\cdots +nk_{n}=n}\prod _{j=1}^{n}{\frac {x_{j}^{k_{j}}y^{jk_{j}}}{j^{k_{j}}k_{j}!}}=\prod \limits _{j\geq 1}\sum \limits _{k_{j}\geq 0}{\frac {(x_{j}y^{j})^{k_{j}}}{j^{k_{j}}k_{j}!}}=\prod \limits _{j\geq 1}\exp \left({\frac {x_{j}y^{j}}{j}}\right),$

ottenendo una forma semplificata per l'indice del ciclo di $S_{n}$:

${\begin{aligned}P_{S_{n}}&=[y^{n}]\prod \limits _{k\geq 1}\exp \left({\frac {x_{k}y^{k}}{k}}\right)\\&=[y^{n}]\exp \left(\sum \limits _{k\geq 1}{\frac {x_{k}y^{k}}{k}}\right)\\\end{aligned}}$

Forma di Bell dell'indice ciclo

Un'equazione equivalente tiene conto dei polinomi di Bell:

$P_{S_{n}}={\frac {B_{n}(0!\,x_{1},\ 1!\,x_{2},\dots ,(n-1)!\,x_{n})}{n!}}.$

Forma ricorsiva dell'indice ciclo

Definiamo $P_{S_{0}}=1$ e consideriamo l-ciclo che contiene n, dove ${\begin{matrix}1\leq l\leq n.\end{matrix}}$ Abbiamo ${\begin{matrix}{n-1 \choose l-1}\end{matrix}}$ modi per scegliere $l-1$ elementi del ciclo e ogni scelta del genere porta a ${\begin{matrix}{\frac {l!}{l}}=(l-1)!\end{matrix}}$ cicli diversi. Otteniamo:

$P_{S_{n}}={\frac {1}{n!}}\sum _{g\in S_{n}}\prod _{i=1}^{n}x_{i}^{k_{i}(g)}={\frac {1}{n!}}\sum _{l=1}^{n}{n-1 \choose l-1}\;(l-1)!\;x_{l}\;(n-l)!\;P_{S_{n-l}}={\frac {1}{n}}\sum _{l=1}^{n}x_{l}\;P_{S_{n-l}}$

ottenendo la definizione ricorsiva:

$P_{S_{n}}={\begin{cases}1,&n\ =0\\{\frac {1}{n}}\sum _{l=1}^{n}x_{l}\;P_{S_{n-l}}&n\geq 1\\\end{cases}}$

Gruppo alterno A_n

Il gruppo alterno è un sottogruppo normale di S_n e contiene solo le permutazioni pari che hanno la funzione segno $\epsilon (g)=+1$. Tenendo conto quanto detto all'inizio della sezione sull'insieme degli elementi rappresentativi delle classi di coniugio, occorre modificare l'indice ciclo di S_n in modo da annullare i tipi che sono dispari tenendo conto di |A_n|:

$2=1+(-1)^{k_{2}+k_{4}+\cdots }=1+(-1)^{\sum _{i=1}^{f(n)}k_{2i}}={\begin{cases}2,&\epsilon (g)=+1\\0,&\epsilon (g)=-1\end{cases}}\qquad f(n)={\begin{cases}n/2,&n{\text{ pari}}\\(n-1)/2,&n{\text{ dispari }}\end{cases}}$

$|A_{n}|={\frac {n!}{2}}={\frac {n!}{1+(-1)^{k_{2}+k_{4}+\cdots }}}$

fatta questa premessa, l'indice ciclo del gruppo alterno come azione naturale del gruppo di permutazione è:

$P_{A_{n}}={\frac {n!}{|A_{n}|}}\sum _{c=1}^{p(n)}\ \left[\left(\prod _{i=1}^{n}\,{\frac {1}{i^{k_{i}(g_{c})}\ k_{i}(g_{c})!}}\right)\,\prod _{j=1}^{n}\,{x_{j}}^{k_{j}(g_{c})}\right]=\sum _{c=1}^{p(n)}\ \left[\left({\frac {1+(-1)^{k_{2}(g_{c})+k_{4}(g_{c})+\cdots }}{\prod _{i=1}^{n}\ i^{k_{i}(g_{c})}\ k_{i}(g_{c})!}}\right)\,\prod _{j=1}^{n}\,{x_{j}}^{k_{j}(g_{c})}\right].$

Applicazioni

In questa sezione utilizziamo la notazione esplicita che include il gruppo di permutazione G e le variabili come segue:

$P_{G}=P(G;\ x_{1},x_{2},\ldots ,x_{n}).$

Sia dato un G-set X o un'azione di G su X. G induce un'azione sui k-sottoinsiemi di X e sulle k-tuple di elementi distinti di X (vedi l'esempio nel caso k = 2), con 1 ≤ k ≤ n. Denotiamo con f_k ed F_k il numero di orbite di G di tale induzione. Per convenzione abbiamo f₀ = F₀ = 1. Dalla teoria abbiamo i seguenti risultati:

a) La funzione generatrice ordinaria per f_k ha equazione:

$\sum _{k=0}^{n}f_{k}t^{k}=P(G;1+t,1+t^{2},\ldots ,1+t^{n}),$ and

b) La funzione generatrice esponenziale per F_k ha equazione:

$\sum _{k=0}^{n}F_{k}t^{k}/k!=P(G;1+t,1,1,\ldots ,1).$

Let G be a group acting on the set X and h a function from X to Y. For any g in G, h(x^g) is also a function from X to Y. Thus, G induces an action on the set Y^X of all functions from X to Y. The number of orbits of this action is Z(G; b, b, ...,b) where b = |Y|.

This result follows from the orbit counting lemma (also known as the Not Burnside's lemma, but traditionally called Burnside's lemma) and the weighted version of the result is Pólya's enumeration theorem.

The cycle index is a polynomial in several variables and the above results show that certain evaluations of this polynomial give combinatorially significant results. As polynomials they may also be formally added, subtracted, differentiated and integrated. The area of symbolic combinatorics provides combinatorial interpretations of the results of these formal operations.

The question of what the cycle structure of a random permutation looks like is an important question in the analysis of algorithms. An overview of the most important results may be found at random permutation statistics.

Note

Postille

Bibliografia

• (EN) Dixon John D.; Mortimer Brian, Permutation Groups, New York, Springer Publishing, 1996, ISBN 0-387-94599-7.
• (EN) Cameron Peter J., 15. Enumeration under group action, in Combinatorics:Topics, Techniques, Algorithms, Cambridge, CUP, 1994, pp. 245–256, ISBN 0-521-45761-0.
• (EN) Roberts Fred S.; Tesman Barry, Applied Combinatorics, 2ª ed., Boca Raton, CRC Press, 2009, ISBN 978-1-4200-9982-9.
• (EN) Dummit David S.; Foote Richard M., Abstract Algebra, 3ª ed., John Wiley & Sons, 2004, ISBN 0-471-43334-9.
• (EN) van Lint J.H.; Wilson R.M., 35.Pólya theory of counting, in A Course in Combinatorics, Cambridge, CUP, 1992, pp. 461–474, ISBN 0-521-42260-4.

Collegamenti esterni

• Marko Riedel, Pólya's enumeration theorem and the symbolic method
• Marko Riedel, Cycle indices of the set / multiset operator and the exponential formula
• Harald Fripertinger, Cycle indices of linear, affine and projective groups, in Linear Algebra and Its Applications, vol. 263, 1997, pp. 133–156, DOI:10.1016/S0024-3795(96)00530-7.
• Harald Fripertinger, Enumeration in Musical Theory, in Beiträge zur Elektronischen Musik, vol. 1, 1992.