Il teorema di Polya ed alcune generalizzazioni - uz.sns.ituz.sns.it/~fvenez/tesi.pdf · ro di...

UNIVERSITA DEGLI STUDI DI PISA

FACOLTA DI SCIENZE MATEMATICHE, FISICHE E NATURALI

CORSO DI LAUREA IN MATEMATICA

TESI DI LAUREA2005

Il teorema di Polya ed alcune

generalizzazioni

Candidato

Francesco Veneziano

Relatore

Prof. Roberto Dvornicich

Universita di Pisa

Controrelatore

Prof. Dario Andrea Bini

Universita di Pisa

ANNO ACCADEMICO 2004/2005

Introduzione

In questa tesi presenteremo il teorema di Polya, uno dei primi risultati dellacombinatoria moderna che ha contribuito alla transizione di questa mate-ria da semplice insieme di trucchi ad hoc a rispettabile campo di ricerca conimportanti applicazioni all’informatica. Il contesto del teorema e quellodelle azioni di gruppi, in particolare si studia l’azione di un gruppo fini-to sulle colorazioni di un insieme finito, intendendo con questo terminele funzioni dall’insieme che associano ad ogni elemento un colore sceltotra un numero finito di possibilita; il teorema stabilisce un’uguaglianza tradue polinomi legati uno al gruppo e l’altro al modo in cui esso agisce sul-le colorazioni, e consente di ottenere numerose informazioni sulle orbitedell’azione esclusivamente dalla conoscenza del gruppo.

Dopo essere stato introdotto nella prima meta del ’900 per risolvere pro-blemi di teoria dei grafi ed essere stato generalizzato in piu direzioni neglianni seguenti, il teorema di Polya ha vissuto una seconda giovinezza deglianni ’70, quando l’avvento dei calcolatori ne ha messo in luce il caratterecomputazionale. Usando il teorema di Polya infatti, nel calcolo del nume-ro di orbite per un’azione di gruppo la difficolta di costruire esplicitamen-te un sistema di rappresentanti viene aggirata ed il problema si riduce adeffettuare manipolazioni algebriche su polinomi.

Nel primo capitolo viene richiamata la terminologia delle azioni di gruppoe viene dimostrato il lemma di Burnside, che e alla base del lavoro di Polyae la cui dimostrazione contiene l’idea combinatoria del teorema. Per po-ter enunciare il risultato principale introdurremo alcuni polinomi utili perlo studio dell’azione di un gruppo su una colorazione, ed applicando piuvolte il lemma di Burnside giungeremo alla dimostrazione del teorema diPolya, che illustreremo con qualche esempio.

Il secondo capitolo espone le generalizzazioni del teorema di Polya dovu-te a Williamson, ottenute usando il formalismo dell’algebra multilineare efinalizzate ad estendere il tipo di problemi che si possono risolvere. Rica-veremo alcune formule che permettono di affrontare colorazioni non omo-genee, nelle quali l’insieme di colori ammessi non e lo stesso ma varia ele-

iii

iv

mento per elemento, e mostreremo qualche loro applicazione all’esempiodel registro con shift.

Nel terzo capitolo viene sfruttato piu a fondo il carattere non discreto dellageneralizzazione di Williamson per ottenere un analogo probabilistico deirisultati classici della teoria di Polya. Presenteremo alcuni risultati di Wil-liamson eWhite per il calcolo dei momenti di opportune variabili aleatorielegate a distribuzioni di probabilita sulle colorazioni e porteremo avantil’esempio del registro con shift per mostrare qualche altra applicazione.

Nell’appendice useremo il teorema di Polya per dimostrare un lemma uti-le in numerosi problemi di combinatoria legati all’enumerazione di grafi,e grazie ad esso troveremo un’espressione semplice della funzione gene-ratrice per gli alberi tetravalenti. Questo tipo di applicazione, originatoda un problema di chimica quale determinare il numero dei possibili iso-meri di struttura degli alcani, e un esempio tipico del genere di problemiper i quali il teorema e stato originariamente sviluppato ed ai quali e statoampiamente applicato.

Indice

1 Il teorema di Polya 11.1 Azioni di gruppi . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Il teorema di Polya . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Generalizzazioni multilineari 7

2.1 I risultati di De Bruijn . . . . . . . . . . . . . . . . . . . . . . . 72.2 La generalizzazione di Williamson . . . . . . . . . . . . . . . 112.3 Il registro di shift . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Versione probabilistica 19

3.1 I momenti di una variabile aleatoria . . . . . . . . . . . . . . 193.2 La formula di Marcus . . . . . . . . . . . . . . . . . . . . . . . 21

A L’enumerazione degli alcani 23

A.1 Un’applicazione tipica . . . . . . . . . . . . . . . . . . . . . . 23

B Notazioni e definizioni 27

v

Capitolo 1

Il teorema di Polya

1.1 Azioni di gruppi

Cominciamo richiamando il concetto di azione di un gruppo, essenzialeper poter enunciare il teorema oggetto di questa tesi.

Definizione (Azione di gruppo). Un’azione di un gruppo G su un insieme Xe un omomorfismo ψ : G −→ S(X) da G nel gruppo delle permutazioni di X.L’azione e detta fedele se kerψ = 0.L’orbita di un elemento x ∈ X e l’insieme

Ox = {σx | al variare di σ ∈ G} ⊂ X

Lo stabilizzatore di un elemento x ∈ X e il sottogruppo

Stabx = {σ ∈ G | σx = x} < G

I punti fissi di un elemento σ ∈ G sono gli elementi di

Fixσ = {x ∈ X | σx = x} ⊂ X

Il concetto di azione di gruppo e molto generale e quando gli oggetti coin-volti hanno cardinalita finita si presta ad essere usato in combinatoria gra-zie alla seguente

Proposizione 1.1. Se G e X sono finiti, vale la relazione

|G| = |Ox||Stabx |.

1

IL TEOREMA DI POLYA ED ALCUNE GENERALIZZAZIONI

I problemi di combinatoria si presentano spesso sotto forma di conteggi,e quando ad essere contato e l’insieme delle orbite di un’azione la pro-posizione precedente ci permette di ricavare una formula che puo fornireparecchie informazioni ed e alla base del teorema di Polya.

Teorema 1.2 (Lemma di Burnside). Indicando con ∆ un insieme di rappresen-tati per le orbite dell’azione, vale l’uguaglianza

|∆| =1

|G|

∑

σ∈G

|Fixσ |.

Dimostrazione. Considerando l’insieme delle coppie (σ, x) ∈ G×X tali cheσx = x otteniamo che la sua cardinalita e pari a

∑

σ∈G

|Fixσ | =∑

x∈X

|Stabx | = |G|∑

x∈X

1

|Ox|= |G|

∑

x∈∆

1 = |G||∆|

e da questa catena di uguaglianze segue immediatamente la tesi.

1.2 Il teorema di Polya

Il teorema di Polya si occupa di una vasta classe di problemi di combi-natoria legati all’enumerazione di strutture etichettate, tipicamente gra-fi e colorazioni dei loro vertici o lati. Nel corso della tesi indicheremocon D un insieme finito di cardinalita d su cui agisce il gruppo di per-mutazione G, e con R un insieme finito di cardinalita r (da pensare co-me l’insieme dei colori); ci occuperemo delle colorazioni di D: le funzioniin RD = {γ : D −→ R}. Considereremo solo azioni fedeli, e dicendoche G e un gruppo di permutazioni intendiamo identificare il gruppo conl’immagine dell’azione trattandolo come un sottogruppo di S(D).

Sfruttando l’azione di G su D possiamo definire un’azione di G su RD

tramiteσγ = γ ◦ σ−1.

Chiamiamo ∆ un insieme di rappresentanti per le orbite di questa azione.Introduciamo ora i seguenti polinomi:

Definizione (Pattern inventory). Il pattern inventory dell’azione di G su RD eil polinomio

∑

γ∈∆

yγ(1) · · · yγ(d) ∈ Z[y1, . . . , yr].

In questo polinomio il coefficiente di ogni monomio yα11 · · · yαr

r e il nume-ro di colorazioni distinte sotto l’azione del gruppo nelle quali αi elementiassumono il colore i per ogni i = 1, . . . , r.

2

1. IL TEOREMA DI POLYA

Ad esempio se prendiamo comeD l’insieme delle facce di un cubo, comeGil gruppo delle rotazioni del cubo e come R l’insieme composto dai coloribianco e nero, il pattern inventory e il polinomio

b6 + b5n+ 2b4n2 + 2b3n3 + 2b2n4 + bn5 + n6.

Infatti, ad esempio, esistono due modi distinti per rotazioni di colorare trefacce di un cubo di bianco e le altre di nero: la colorazione in cui le faccebianche hanno un vertice in comune e quella in cui questo non avviene.

Definizione (Cycle index). Il cycle index del gruppo di permutazioni G e ilpolinomio

ZG(x1, . . . , xd) =1

|G|

∑

σ∈G

xkσ1

1 · · · xkσ

d

d ∈ Q[x1, . . . , xd].

Dove kσi e il numero di cicli di lunghezza i nella decomposizione in cicli disgiunti

di σ.

Calcoliamo il cycle index per il gruppo ciclico con n elementi Cn generatodalla permutazione σ = (1, 2, . . . , n).L’elemento del gruppo σi si decompone in (n, i) cicli disgiunti di lunghezzapari a n

(n,i) ; se d non e un divisore di n non esiste alcun i tale chen

(n,i) = d,

altrimenti esistono ϕ(d) di tali i, dove ϕ e la funzione phi di Eulero.Pertanto

ZCn =1

n

∑

d|n

ϕ(d)xn/dd . (1.1)

In modo simile si puo calcolare anche il cycle index del gruppo diedrale

ZDn =1

2ZCn +

1

2x1x

(n−1)/22 per n dispari

1

4(x

n/22 + x2

1x(n−2)/22 ) per n pari.

Possiamo ora dimostrare il

Teorema 1.3 (di Polya). Con le notazioni introdotte fin ora, il pattern inventorydell’azione di G su RD e dato da

ZG

(∑

i∈R

yi,∑

i∈R

y2i , . . . ,

∑

i∈R

ydi

)

.

3


Dimostrazione. L’idea per dimostrare il teorema e quella di restringere l’a-zione alle sole colorazioni che usano αi volte il colore i per ogni i, e contar-ne il numero singolarmente applicando il lemma di Burnside.Per il lemma il numero di tali colorazioni a meno dell’azione (che e il coef-ficiente di ya1

1 · · · yarr nel pattern inventory) e pari alla media sul gruppo del

numero di punti fissi di ogni permutazione. Poiche scelto un σ nel gruppole colorazioni che lascia fisse sono tutte e sole quelle che sono costanti suicicli di σ, tali colorazioni corrispondono al numero di modi in cui possiamoraggruppare una somma

kσ1

︷︸︸︷

1 + · · · + 1 +

kσ2

︷︸︸︷

2 + · · · + 2+ · · · +

kσd

︷︸︸︷

d+ · · · + d

nella forma

(α1) + (α2) + · · · + (αd).

Il numero di modi in cui si puo far questo e pari al coefficiente di yα11 · · · yαr

r

nello sviluppo di

(y11 + · · · + y1

r)kσ1 × (y2

1 + · · · + y2r)

kσ2 × · · · × (yd

1 + · · · + ydr )

kσd .

La media di questi fattori su tutto il gruppo e proprio il cycle index calco-lato in

∑

i∈R yi,∑

i∈R y2i , . . . ,

∑

i∈R ydi .

1.3 Esempi

Consideriamo nuovamente le facce di un cubo e facciamo agire su esso ilgruppo delle rotazioni.

1+1+1+1+1+1 11+1+2+2 31+1+4 62+2+2 63+3 8

La tabella riporta la frequenza di ogni decomposizione in cicli tra gli ele-menti del gruppo, e ci permette di calcolare esplicitamente il cycle index

Z(x1, x2, x3, x4, x5, x6) =1

24(x6

1 + 3x21x

22 + 6x2

1x4 + 6x32 + 8x2

3).

Da questo possiamo ritrovare il pattern inventory con due colori ottenutoprecedentemente

b6 + b5n+ 2b4n2 + 2b3n3 + 2b2n4 + bn5 + n6.

4

1. IL TEOREMA DI POLYA

Poiche il numero totale di colorazioni distinte a meno di rotazioni e parialla somma dei coefficienti del pattern inventory, cioe al pattern invento-ry calcolato in 1, 1, . . . , 1, il teorema di Polya ci permette di ottenere que-sto numero calcolando il cycle index in r, r, . . . , r. In questo modo e facilecalcolare ad esempio il numero di colorazioni con r colori delle facce deipoliedri regolari distinte a meno di rotazioni.

Tetraedro 112(r4 + 11r2)

Cubo 124(r6 + 3r4 + 12r3 + 8r2)

Ottaedro 124(r8 + 17r2 + 6r2)

Dodecaedro 160(r12 + 15r6 + 44r4)

Icosaedro 160(r20 + 15r10 + 20r8 + 24r4)

Si noti come, pur essendo il gruppo delle rotazioni del cubo e quello dellerotazioni dell’ottaedro isomorfi, il cycle index e quindi il numero di co-lorazioni distinte sono diversi; cio e dovuto al fatto che sono distinte leimmersioni di tale gruppo in S6 edS8 rispettivamente.

Questo teorema ha avuto una grande importanza nel trasformare la com-binatoria in una seria materia di studio ed e stato ampiamente applicatoalla teoria dei grafi negli anni successivi all’articolo di Polya.Molte generalizzazioni del teorema di Polya sono raccolte nel survey di DeBruijn [DB71].Nei capitoli successivi tratteremo alcuni teoremi ottenuti da Williamsonnegli anni ’70 utilizzando strumenti dell’algebra multilineare; altre genera-lizzazioni piu recenti sono quelle di Bekes [Bek92] che considera l’azionedi un gruppo discreto infinito, o quella di Iliev [Ili00] che utilizza la teoriadelle matrici inverianti di Schur-Macdonald.

5


6

Capitolo 2

Generalizzazioni multilineari

Una caratteristica del teorema di Polya e quella di trasferire la difficoltadi un problema di enumerazione dalla struttura delle orbite alla strutturadel gruppo che agisce; la possibilita di ottenere informazioni sulle orbitetramire calcoli di routine come manipolazioni algebriche di polinomi haacceso l’interesse per l’aspetto computazionale del teorema e i risultati diWilliamson vanno in questa direzione ottenendo formule analoghe a quelledel teorema di Polya nel caso in cui le colorazioni siano non omogenee.

2.1 I risultati di De Bruijn

Se H e un gruppo finito che agisce su R e G come prima un gruppo cheagisce su D, il prodottoH ×G agisce su RD con (τ, σ)γ = τγσ−1, e a que-sta azione che siamo interessati.Sia V uno spazio vettoriale di dimensione r su un campo K di caratteri-

stica 0, e U =⊗d V il prodotto tensore di d copie di V ; una base di U

e data da β = {eγ | γ ∈ RD}, dove abbiamo indicato con eγ l’elementoeγ(1) ⊗ · · · ⊗ eγ(d).

In qualche senso abbiamo sostituito i colori con lo spazio vettoriale da lorogenerato e una colorazione con un elemento della base canonica del pro-dotto tensore; in questo formalismo l’azione del gruppo tramite permuta-zioni di D ed R si traduce in una rappresentazione come trasformazionilineari, che ora definiamo.

Per ogni (τ, σ) ∈ H ×G definiamo un operatore P (τ, σ) : U → U tramite

P (τ, σ)eγ = eτγσ−1

che permuta tra loro gli elementi della base β; gli operatori cosı definiti co-stituiscono una rappresentazione diH ×G.

7


Se λ e un carattere diH ×G, definiamo l’operatore di simmetria

T λH×G =

1

|H||G|

∑

(τ,σ)∈H×G

λ(τ, σ)P (τ, σ).

Per ora considereremo solo il caso λ ≡ 1, piu avanti vedremo come sfrut-tare λ non banali per escludere dal conteggio colorazioni dotate di alcunesimmetrie.Come notazione, ometteremo il λ da un simbolo quando λ ≡ 1, e scrive-remo soltanto G quando il gruppo H che permuta i colori e banale, comenella formulazione originale del teorema di Polya.

Osservazione 2.1. Vale la formula

P (σ)x1 ⊗ · · · ⊗ xd = xσ−1(1) ⊗ · · · ⊗ xσ−1(d).

Dimostrazione. Siano xi =∑r

j=1 ai jej per i = 1, . . . , d.

P (σ)x1 ⊗ · · · ⊗ xd =∑

γ∈RD

∏

t∈D

atγ(t)eγ◦σ−1 =

∑

γ∈RD

∏

t∈D

atγ(σ(t))eγ =∑

γ∈RD

∏

t∈D

aσ−1(t)γ(t)eγ =

xσ−1(1) ⊗ · · · ⊗ xσ−1(d).

Osservazione 2.2.

T λH×G ◦ T λ

H×G = T λH×G.

Sia ora W : RD → K una funzione costante sulle orbite (che quindi puoassume al piu |∆| valori distinti); tramite questa funzione ridefiniremo ilpattern inventory e piu avanti, abbandonando la richiesta che sia costantesulle orbite, tratteremo il caso non omogeneo.

Lemma 2.3. Sia Uα il sottospazio generato dai tensori {eγ |W (γ) = α}.

Allora U =⊕

α∈K

Uα e gli spazi Uα sono invarianti per tutti gli operatori P (τ, σ) e

per TH×G.

Dimostrazione. PoicheW (γ1) 6= W (γ2) =⇒ γ1 6= γ2 gli insiemi di generato-ri dei sottospazi Uα sono disgiunti, e dal momento che β = {eγ | γ ∈ RD}

8

2. GENERALIZZAZIONI MULTILINEARI

e una base e chiaro che U =⊕

α∈K

Uα.

PoicheW e costante sulle orbite diH ×G abbiamo che

eγ ∈ Uα =⇒ P (τ, σ)eγ ∈ Uα,

e pertanto gli spazi Uα sono invarianti per gli operatori P (τ, σ) e quindianche per TH×G.

Definiamo ora TαH×G(τ, σ) e Pα(τ, σ) le restrizioni a Uα di TH×G(τ, σ) e

P (τ, σ) rispettivamente, e

PW (τ, σ) =⊕

α∈K

αPα(τ, σ)

eTW

H×G =⊕

α∈K

αTαH×G.

Lemma 2.4. La traccia di PW (τ, σ) e data da

∑

γ∈Fix(τ,σ)

W (γ).

Dimostrazione. SiaM la matrice che rappresenta PW (τ, σ) nella base β.M ha un coefficiente diverso da zero sulla diagonale in corrispondenzadel vettore della base eγ se e solo se PW (τ, σ)eγ ha una componente nonzero lungo eγ ; ma PW (τ, σ)eγ = W (γ)P (τ, σ)eγ = W (γ)eτγσ−1 e quindi ilcoefficiente e diverso da zero se e solo se (τ, σ)eγ = eγ eW (γ) 6= 0, nel qualcaso e pari a W (γ). Quindi i coefficienti diversi da zero sulla diagonaledi M corrispondono ai γ fissati da (τ, σ) ed hanno come valori i W (γ).

Pertanto TrM =∑

γ∈Fix(τ,σ)

W (γ).

Siano

e♯γ =1

|H||G|

∑

(τ,σ)∈H×G

P (τ, σ)eγ

le immagini dei vettori della base tramite TH×G.

Teorema 2.5.

TWH×G =

1

|H||G|

∑

(τ,σ)∈H×G

PW (τ, σ). (2.1)

Inoltre l’insieme β♯ = {e♯γ | γ ∈ ∆} forma una base di autovettori per l’immaginedi TW

H×G corrispondenti agli autovalori {W (γ) | γ ∈ ∆}.

9


Dimostrazione. Poiche Uα e invariante rispetto a P (τ, σ), abbiamo

TαH×G =

1

|H||G|

∑

(τ,σ)∈H×G

Pα(τ, σ)

e quindi⊕

α∈K

αTαH×G =

1

|H||G|

∑

(τ,σ)∈H×G

⊕

α∈K

αPα(τ, σ)

che dimostra l’identita.

Ovviamente β♯ genera l’immagine di TWH×G, verifichiamo che e costituito

da vettori linearmente indipendenti.Sia ∑

γ∈∆

dγTH×G(eγ) = 0 (2.2)

una combinazione lineare pari a zero, e sia {h1, . . . , hr} la base di V∗ duale

di {e1, . . . , er}. Sia hγ il prodotto tensore hγ(1) ⊗ · · · ⊗ hγ(d) in⊗d V ∗, per

cui valehγ(eη) =

∏

t∈D

hγ(t)(eη(t)).

Osserviamo che

hη(TH×G(eγ)) =|Stab(η)|

|H||G|

se γ ed η sono nella stessa orbita e 0 altrimenti.Fissiamo ora η ∈ ∆ e valutiamo hη su (2.2) ottenendo

hη

∑

γ∈∆

dγTH×G(eγ)

=dη|Stab(η)|

|H||G|= 0

e quindi dη = 0 per ogni η ∈ ∆ e β♯ e una base per l’immagine di TWH×G.

Infine per mostrare che β♯ e composta da autovettori osserviamo che

W (γ) = α⇒ TWH×G(eγ) ∈ Uα

e quindi

TWH×G(TH×G(eγ)) = W (γ)T 2

H×G(eγ) = W (γ)TH×G(eγ)

per l’osservazione (2.2).

Corollario 2.6.∑

γ∈∆

W (γ) =1

|H||G|

∑

(τ,σ)∈H×G

∑

γ∈Fix(τ,σ)

W (γ).

10


Dimostrazione. Basta prendere la traccia di ambo i membri dell’identita(2.1) ed applicare il lemma (2.4).

Quest’identita dovuta a De Bruijn e una generalizzazione del teorema diPolya. Per ritrovarlo consideriamo il caso di H = {e} banale e W della

forma W (γ) =∏

t∈D

ω(γ(t)) per una certa funzione ω : R −→ K; in questo

modo il lato sinistro dell’uguaglianza e esattamente il pattern inventory ei valori ω(j) sono le indeterminate yj .Chiaramente W e costante sulle orbite dell’azione e quindi se γ e fissatada σ e t e un elemento di D in un ciclo di lunghezza i di σ, ω(γ(d))i e unfattore diW (γ); inoltre per ogni colore u ∈ R per qualche γ ∈ RD γ(t) = u.Pertanto considerando tutte le γ fissate da σ e raccogliendo dalla somma ifattori dovuti ad ogni ciclo di σ otteniamo

∑

γ∈Fix σ

W (γ) =

(∑

u∈R

ω(u)

)kσ1(∑

u∈R

ω(u)2

)kσ2

· · ·

(∑

u∈R

ω(u)d

)kσd

.

Questa formula, sostituita nel corollario (2.6), ci da il teorema di Polya.

2.2 La generalizzazione di Williamson

Nella notazione della sezione precedente consideriamo il caso in cui vi siasolo un gruppo G ad agire su D, ma il carattere λ di G in K sia diverso da1. In questo caso definiamo un sistema parziale di rappresentanti per leorbite

∆ =

{

γ ∈ ∆ |∑

σ∈Stabγ

λ(σ) 6= 0

}

ed indichiamo con e∗γ l’espressione

e∗γ =∑

σ∈G

λ(σ)P (σ)eγ .

Allora una formula dovuta a Marcus afferma che

1

|G|

∑

σ∈G

λ(σ)xσ−1(1) ⊗ · · · ⊗ xσ−1(d) =∑

γ∈∆

A(γ)e∗γ , (2.3)

dove xi =

r∑

j=1

ai jej i = 1, . . . , d

A(γ) =∑

σ∈Sγ

λ(σ)∏

t∈D

at γσ(t)

11


(ai,j) e una matrice d× r assegnata e Sγ e un sistema di rappresentanti perle classi laterali di Stabγ in G.Proporremo piu avanti un’interpretazione combinatoria di questa identita,per ora vogliamo ricavare una formula simile che ci permetta di affrontareproblemi ai quali il teorema di Polya non e applicabile.

Per γ ∈ RD e σ ∈ G, definiamo

fσ(eγ) =

{

eγ se σ ∈ Stab(γ)

0 altrimenti

e

QλG =

1

|G|

∑

σ∈G

λ(σ)fσ

ovvero

QλG(eγ) =

1

|G|

∑

σ∈Stabγ

λ(σ)eγ .

Sia anche

a(γ) =1

|G|

∑

σ∈G

∏

t∈D

at γσ(t) =1

|Sγ |

∑

σ∈Sγ

∏

t∈D

at γσ(t)

siano Dσk le orbite in cui viene decomposto D all’azione del sottogruppo

generato da σ e Dσ = {Dσk | k = 1, . . . , p} l’insieme di tali orbite.

Teorema 2.7. Vale la formula

QλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

=∑

γ∈∆

a(γ)e♯γ . (2.4)

Inoltre se l = l1 ⊗ · · · ⊗ ld e un funzionale lineare omogeneo in U∗ vale

lfσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d)) =∏

k∈Dσ

∑

u∈R

∏

j∈Dσk

aφ−1(j) u lj(eu). (2.5)

Dimostrazione. Osserviamo che

hγfσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d)) = hγfσ

∑

α∈RD

(∏

t∈D

aφ−1(t) α(t)

)

eα

= hγ

∑

α∈Fixσ

(∏

t∈D

aφ−1(t) α(t)

)

eα =

∏

t∈D

aφ−1(t)γ(t) se σ ∈ Stabγ

0 altrimenti.

12


Inoltre per definizione

QλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

=

1

|G|2

∑

σ∈G

∑

φ∈G

λ(σ)fσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d))

e quindi

hγQλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

=1

|G|2

∑

φ∈G

∑

σ∈Stabγ

λ(σ)∏

t∈D

aφ−1(t) γ(t)

=1

|G|2

∑

σ∈Stabγ

λ(σ)

∑

φ∈G

∏

t∈D

aφ−1(t) γ(t)

=

|Stabγ |

|G|a(γ) se Stabγ ⊂ ker λ

0 altrimenti.

Calcoliamo ora hγ su∑

γ∈∆

a(γ)e♯γ e mostriamo che e uguale a

hγQλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

.

Sia α0 ∈ ∆ il rappresentante dell’orbita di γ, e γ = α0 ◦ σ−1. Se α0 6∈ ∆abbiamo che

hγ

∑

γ∈∆

a(γ)e♯γ

= 0,

se invece α0 ∈ ∆

hγ

∑

γ∈∆

a(γ)e♯γ

= a(α0)hγ(e♯α0) = a(α0)

|Stabα0 |

|G|= a(γ)

|Stabγ |

|G|.

Inoltre si ha che α0 ∈ ∆ ⇔ Stabα0 ⊂ ker λ e, dal momento che Stabγ eStabα0 sono coniugati e kerλ e un sottogruppo normale di G,

Stabα0 ⊂ kerλ⇔ Stabγ ⊂ ker λ.

13


Essendo {h1, . . . , hr} la base duale di {e1, . . . , er} la formula (2.4) rimanequindi dimostrata.Per dimostrare (2.5) notiamo che

lfσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d)) =∑

α∈Fixσ

(∏

t∈D

aφ−1(t) α(t)

)

l(eα) =

∑

α∈Fixσ

∏

t∈D

aφ−1(t) α(t)lt(eα(t)). (2.6)

Sia

Ak i =∏

j∈Dσk

aφ−1(j) ilj(ei) k = 1, . . . , p; i ∈ R.

Per ogni γ ∈ Fixσ, cioe per ogni funzione costante sulle orbite di una per-mutazione σ fissata, definiamo γ : [1, . . . , p] −→ R con γ(k) = γ(j) per unqualsiasi j ∈ Dσ

k .

Quindi

∏

t∈D

aφ−1(t) γ(t)lt(eγ(t)) =

p∏

k=1

∏

j∈Dσk

aφ−1(j) γ(j)lt(eγ(j)) =

p∏

k=1

Ak γ(k)

e

∑

γ∈Fixσ

∏

t∈D

aφ−1(t) γ(t)lt(eγ(t)) =∑

γ∈RDσ

p∏

k=1

Ak γ(k) =

p∏

k=1

∑

u∈R

Ak u.

Questa formula, insieme alla (2.6) completa la dimostrazione del teorema.

Di nuovo vediamo come ricavare il teorema di Polya dal teorema (2.7).

Prendiamo lj(ei) = ω(i) indipendentemente da j e ai j = 1 (in questo sensoil teorema di Polya e omogeneo); allora la (2.5) diventa

lfσ(xφ−1(1)⊗· · ·⊗xφ−1(d)) =

(∑

u∈R

ω(u)

)kσ1(∑

u∈R

ω(u)2

)kσ2

· · ·

(∑

u∈R

ω(u)d

)kσd

che e una scrittura indipendente da φ.Quindi

14


lQλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

=1

|G|2

∑

σ∈G

∑

φ∈G

λ(σ)lfσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d))

=1

|G|

∑

σ∈G

λ(σ)lfσ(x1 ⊗ · · · ⊗ xd).

Se definiamo un cycle index generalizzato

ZλG(z1, . . . , zd) =

1

|G|

∑

σ∈G

λ(σ)zkσ1

1 · · · zkσ

d

d ∈ K[x1, . . . , xd]

allora

lQλG

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

= ZλG

(∑

u∈R

ω(u), . . . ,∑

u∈R

ω(u)d

)

.

Notiamo che poiche ai j = 1 per ogni i, j si ha che a(γ) = 1 per ogni γ;

inoltre l(e♯γ) = W (γ) e quindi usando la (2.4) l’ultima formula diventa

∑

γ∈∆

W (γ) = ZλG

(∑

u∈R

ω(u), . . . ,∑

u∈R

ω(u)d

)

. (2.7)

Questa formula e il teorema di Polya quando λ ≡ 1, e ne e un perfetto ana-logo se siamo interessati ai rappresentanti di ∆.

Quando il gruppoG e abeliano il teorema (2.7) si puo semplificare ottenen-do il seguente

Corollario 2.8. Per ogni φ, σ ∈ G si ha che fσP (φ) = P (φ)fφ−1σφ. Quindi seG e abeliano i due operatori P (φ) e fσ commutano e la (2.4) diventa

1

|G|2

∑

σ∈G

∑

φ∈G

λ(σ)P (φ)fσ(x1 ⊗ · · · ⊗ xd) =∑

γ∈∆

a(γ)e♯γ . (2.8)

Se inoltre l e un funzionale lineare su U e tale che lP (φ) = l per ogni φ ∈ G valela formula

1

|G|

∑

σ∈G

λ(σ)lfσ(x1 ⊗ · · · ⊗ xd) =∑

γ∈∆

a(γ)l(e♯γ). (2.9)

15


Dimostrazione.

fσP (φ)(eγ) = fσ(eγφ−1) =

{

eγφ−1 se σ ∈ Stabγφ−1

0 altrimenti

e

P (φ)fφ−1σφ(eγ) =

{

P (φ)eγ se φ−1σφ ∈ Stabγ

0 altrimenti

=

{

eγφ−1 se φ−1σφ ∈ Stabγ

0 altrimenti.

σ ∈ Stabγφ−1 ⇔ γφ−1σ = γφ−1 ⇔ γφ−1σφ = γ ⇔ φ−1σφ ∈ Stabγ .Quindi fσP (φ) = P (φ)fφ−1σφ e se G e abeliano fσP (φ) = P (φ)fσ e l’iden-tita (2.8) si ottiene dalla (2.4) scrivendo per esteso

Qλ

1

|G|

∑

φ∈G

xφ−1(1) ⊗ · · · ⊗ xφ−1(d)

e sostituendo

fσP (φ)x1 ⊗ · · · ⊗ xd = fσ(xφ−1(1) ⊗ · · · ⊗ xφ−1(d))

conP (φ)fσ(x1 ⊗ · · · ⊗ xd).

Per ottenere la (2.9) basta ora applicare l ad ambo i membri dell’uguaglian-za (2.8)

2.3 Il registro di shift

Per illustrare come applicare le formule ricavate fino ad ora consideria-mo un registro di shift; con questo termine in elettronica si intende unamacchina a stati finiti in grado di contenere n bit e di operare su di essipermutazioni cicliche.Si tratta quindi di una n-upla considerata a meno dell’azione di Cn, ilgruppo ciclico con n elementi; R = {0, 1} e l’insieme dei possibili colorieD = {1, 2, . . . , n} e l’insieme su cui il gruppo agisce.Consideriamo un registro di shift con 6 bit, ed indichiamo con

σ = (1, 2, 3, 4, 5, 6)

la permutazione che genera C6.Come abbiamo visto in (1.1) il cycle index e

ZC6 =1

6(x6

1 + x32 + 2x2

3 + 2x6).

16


Il numero dei possibili stati del registro e pari al numero di orbite dell’a-zione, che puo essere calcolato col teorema di Polya ed e

|∆| = ZC6(2, 2, 2, 2, 2, 2) = 14.

Sia ora ζ una radice sesta primitiva dell’unita, e consideriamo il caratteredi C6 definito da λ(σi) = ζi. Se uno stato del registro ha uno stabilizzatore

non banale, questo deve essere un gruppo ciclico e∑

σi∈Stabγ

λ(σi) = 0; il

sistema parziale di rappresentanti ∆ consiste quindi degli stati del registroche non sono fissati da nessuna rotazione, e la (2.7) ci permette di calcolareil numero di tali stati. Infatti

ZλC6

=1

6(x6

1 − x32 − x2

3 + x6)

|∆| = ZλC6

(2, 2, 2, 2, 2, 2) = 9.

Supponiamo ora di eseguire un campionamento del registro, che ogni sta-to sia equiprobabile e che ogni rappresentazione dello stato abbia ugualiprobabilita di comparire; cerchiamo, ad esempio, la probabilita che i primitre elementi del registro contengano tre zeri.Prendendo λ ≡ 1 e il funzionale ℓ(eγ) = 1 per ogni γ ∈ RD siamo nelleipotesi per applicare il corollario (2.8). Se scegliamo come matrice

(ai j) =

1 01 01 01 11 11 1

abbiamo che

∏

t∈D

atγσk(t) =

{

1 se γσk(t) = 0, 1 ≤ t ≤ 3

0 altrimenti

e quindi a(γ) e la probabilita che lo stato γ abbia una rappresentazione checominci con 3 zeri.Quello che stiamo cercando e l’espressione 1

|∆|

∑

γ∈∆ a(γ), che puo essere

calcolato valutando esplicitamente il membro di sinistra dell’identita (2.5).Infatti x1 = x2 = x3 = ( 1

0 ) e x4 = x5 = x6 = ( 11 ), e le decomposizioni in

cicli disgiunti delle potenze di σ sono

e {1} ∪ {2} ∪ · · · ∪ {6}σ, σ−1 {1, 2, . . . , 6}σ2, σ4 {1, 3, 5} ∪ {2, 4, 6}σ3 {1, 4} ∪ {2, 5} ∪ {3, 6}

17


Si vede facilmente che

ℓfe(x1 ⊗ · · · ⊗ x6) = ℓfe (( 10 ) ⊗ ( 1

0 ) ⊗ ( 10 ) ⊗ ( 1

1 ) ⊗ ( 11 ) ⊗ ( 1

1 )) = 23

ℓfσ(x1 ⊗ · · · ⊗ x6) = ℓfσ−1(x1 ⊗ · · · ⊗ x6) = 1ℓfσ2(x1 ⊗ · · · ⊗ x6) = ℓfσ4(x1 ⊗ · · · ⊗ x6) = 1

ℓfσ3(x1 ⊗ · · · ⊗ x6) = 1.

La probabilita cercata quindi e 114

16 (8 + 1 + 1 + 1 + 1 + 1) = 13

84 .

18

Capitolo 3

Versione probabilistica

L’approccio multilineare si presta ad interpretazioni probabilistiche che so-no state indagate daWilliamson eWhite [Whi79, WW76]; usando il forma-lismo mostrato fin ora si possono ricavare formule per i momenti di varia-bili aleatorie legate all’azione del gruppoG.

3.1 I momenti di una variabile aleatoria

Consideriamo una misura di probabilita P e una variabile aleatoria realeXsu RD.

Definiamo una famiglia di funzionali lineari sp, p = 1, 2, . . .

speγ = X(γ)pP(γ)|Oγ |

e indichiamo sempre con ℓ il funzionale ℓeγ = 1.

Sia anche J =∑

γ∈RD

eγ .

Osservazione 3.1. Con queste notazioni abbiamo un’identita che costituisce unariformulazione vettoriale del lemma di Burnside

TG

∑

γ∈∆

eγ = QGJ

Il punto centrale dell’interpretazione probabilistica e costituito dal

Teorema 3.2.

E(Xp) = spQGJ.

19


Dimostrazione.

spQGJ =1

|G|

∑

γ∈RD

|Stabγ |speγ =1

|G|

∑

γ∈RD

|Stabγ ||Oγ |X(γ)pP(γ) =

∑

γ∈RD

X(γ)pP(γ) = E(Xp). (3.1)

Vediamo come applicarlo quando la variabile aleatoria e di forma partico-lare.

Sia

X(γ) =1

|Oγ |=

|Stabγ |

|G|.

X misura la simmetria della colorazione γ tramite la dimensione del suostabilizzatore. Allora abbiamo il

Teorema 3.3. Se P(γ) =∏

t∈D

at γ(t) dove (ai j) e una matrice di probabilita d× r

assegnata e xi =∑

j∈R

ai jej , si ha che

E(Xp) = ℓQpGx1 ⊗ · · · ⊗ xd. (3.2)

Dimostrazione. Osserviamo che

speγ = Xp(γ)P(γ)|Oγ | =1

|Oγ |p−1

∏

t∈D

at γ(t) = ℓQp−1G

∏

t∈D

at γ(t)eγ

e quindi usando il teorema (3.1) si ha

E(Xp) = ℓQpGx1 ⊗ · · · ⊗ xd.

Un’altra distribuzione di probabilita molto naturale su RD e che abbiamogia incontrato alla fine del secondo capitolo e quella definita da

P(γ) =1

|∆||Oγ |,

che corrisponde a scegliere un’orbita con probabilita uniforme, e all’internodell’orbita scegliere un elemento che vi appartiene, ancora con probabilitauniforme; in questo caso vale il

20

3. VERSIONE PROBABILISTICA

Teorema 3.4. Se P(γ) = 1|∆||Oγ|

, abbiamo che

E(Xp) =1

|∆|ℓQ

p+1G J.

Dimostrazione.

speγ =1

|Oγ |p1

|∆||Oγ ||Oγ | =

1

|∆||Oγ |p

cioe

sp =1

|∆|ℓQ

pG

e quindi applicando il teorema (3.1) si ha la tesi.

3.2 La formula di Marcus

Vediamo ora un’interpretazione probabilistica della formula (2.3) al regi-stro di shift quando il carattere λ e costantemente 1. Supponiamo che sia-no assegnate le probabilita ai j che l’i-esimo posto del registro contenga ilcolore j e fissiamo un intero positivo q < d.Sia l = l1 ⊗ · · · ⊗ ld il funzionale definito da li(ej) = x se j = 0, li(ej) = 0 sej = 1 e i ≤ q, e li(ej) = 1 se j = 1 e i > q. Quindi

l(e∗γ) =1

|G|

∑

σ∈G

∏

t∈D

lt(eγσ(t)) =1

|Sγ |

∑

σ∈Sγ

∏

t∈D

lt(eγσ(t)),

dove Sγ e un insieme di rappresentanti per le classi laterali di Stabγ . Per-tanto

l(e∗γ) =bγ

|Sγ |xn

dove n = |γ−1(0)| e bγ e il numero di elementi σ in Sγ tali che γσ(t) = 0 perogni t ≤ q.

L’espressione A(γ)bγ

|Sγ |quindi e la probabilita che venga letto lo stato de-

finito da γ e la sua rappresentazione abbia degli zeri nei primi q posti delregistro, mentre

∑

γ∈∆

A(γ)l(e∗γ)

e un polinomio in x dove il coefficiente di xk e la probabilita che il registrocontenga k zeri e i primi q posti siano degli zeri.Per l’identita (2.3) questo polinomio e pari a

1

|G|

∑

σ∈G

l(xσ−1(1) ⊗ · · · ⊗ xσ−1(d)) =1

|G|

∑

σ∈G

∏

t∈D

lt(xσ−1(t)),

21


che e facilmente e calcolabile perche richiede solo manipolazioni algebri-che dei polinomi di primo grado lt(xσ−1(t)).

Nel caso del registro con 6 posti, se prendiamo come matrice degli (ai j)

(ai j) =

34

14

34

14

34

14

12

12

12

12

12

12

e fissiamo q = 3 abbiamo con semplici calcoli che

l(x1 ⊗ · · · ⊗ x6) =

(1

2

)3

x3

(3

4

)3

(1 + x)3

l(xσ(1) ⊗ · · · ⊗ xσ(6)) = l(xσ5(1) ⊗ · · · ⊗ xσ5(6))

=

(1

2

)3

x3

(3

4

)2(1

4

)

(1 + x)2(1 + 3x)

l(xσ2(1) ⊗ · · · ⊗ xσ2(6)) = l(xσ4(1) ⊗ · · · ⊗ xσ4(6))

=

(1

2

)3

x3

(3

4

)(1

4

)2

(1 + x)(1 + 3x)4

l(xσ3(1) ⊗ · · · ⊗ xσ3(6)) =

(1

2

)3

x3

(1

4

)3

(1 + 3x)3,

ed il polinomo desiderato e

26

1536x3 +

111

1536x4 +

162

1536x5 +

81

1536x6.

Il coefficiente del termine xi e la probabilita che, selezionando a caso unostato del registro secondo la matrice assegnata e scegliendo un rappresen-tante casuale di questo stato (considerando i possibili rappresentanti comeequiprobabili), il registro contenga i zeri, di cui 3 nelle prime 3 posizioni.

22

Appendice A

L’enumerazione degli alcani

A.1 Un’applicazione tipica

Presentiamo ora un’applicazione del teorema di Polya all’enumerazionedegli isomeri degli alcani, una questione che ha una traduzione immediatain termini di teoria dei grafi ed e un perfetto esempio del genere di pro-blemi per i quali e stato concepito il teorema (che ha fatto la sua primacomparsa su una rivista di chimica).Dato un insieme A ed una funzione peso ω : A −→ N, diciamo che una

serie f =∑

n≥0

anxn enumera gli elementi di A se

an = |{a ∈ A | ω(a) = n}| ∀n ≥ 0;

ad esempio possiamo pensare ad A come l’insieme di tutti i grafi, ω comela funzione che restituisce il numero dei vertici, e an il numero di grafi conn vertici.

Lemma A.1. Sia A un insieme finito e ω : A −→ N una funzione peso; se f(x)e il polinomio che enumera gli elementi di A, allora ZSk

(f(x), f(x2), · · · , f(xk))enumera le k-uple non ordinate di elementi di A rispetto alla funzione peso

W (x1, . . . , xk) =

k∑

i=1

ω(xi).

Dimostrazione. Consideriamo l’azione di Sk su D = {1, 2, . . . , k} e comeinsiemeR dei colori prendiamoA. Allora gli elementi diRD sono le k-upleordinate di elementi di A, mentre ∆ rappresenta le k-uple non ordinate;inoltre per ogni i ∈ A, sia yi = xω(i) la corrispondente indeterminata nelpattern inventory.Si ha che ∑

i∈A

yji =

∑

i∈A

xjω(i) =∑

n≥0

anxjn = f(xj)

23


e che

∑

γ∈∆

yγ(1)yγ(2) · · · yγ(k) =∑

γ∈∆

xω(1)+ω(2)+···+ω(k) =∑

γ∈∆

xW (γ).

Il teorema di Polya quindi ci da subito la tesi.

Definiamo alcuni termini di teoria dei grafi:

Definizione. Un albero e un grafo connesso che non contiene percorsi chiusi, inparticolare dati due vertici distinti esiste uno ed un solo percorso che li congiunge.Il diametro di un albero e la massima distanza possibile tra due coppie di vertici.Un albero si dice tetravalente se da ogni vertice escono al piu 4 archi.Un albero si dice con radice se ha un vertice distinto agli altri, in questo caso chia-miamo altezza di un vertice la sua distanza dalla radice.Un albero con radice si dice ternario se da ogni vertice escono al piu 3 rami, esclusoquello che lo collega alla radice.

Gli alcani sono composti chimici formati da atomi di carbonio e idrogenocon formula CnH2n+2 e possono essere rappresentati come alberi tetrava-lenti con n vertici.

Useremo questi polinomi, che sono i cycle index dei gruppi simmetrici su2, 3 e 4 elementi

Z2(x1, x2) =1

2(x2

1 + x2)

Z3(x1, x2, x3) =1

6(x3

1 + 3x1x2 + 2x3)

Z4(x1, x2, x3, x4) =1

24(x4

1 + 6x21x2 + 3x2

2 + 8x1x3 + 6x4).

Con abuso di notazione scriveremo Zk(f(x)) invece di

Zk(f(x), f(x2), · · · , f(xk)).

Consideriamo intanto l’insieme degli alberi con radice ternari di altezza alpiu h, e come peso di un tale albero prendiamo il numero dei suoi vertici.Allora chiamando th,n il numero di alberi con radice ternari di altezza al

24

A. L’ENUMERAZIONE DEGLI ALCANI

piu h e con n vertici, definiamo Th(x) =∑

n≥0

th,nxn il polinomio enumera-

tore.Il lemma (A.1) ci dice che Z3(Th(x), Th(x2), Th(x3)) enumera le terne nonordinate di alberi piantati ternari con altezza al piu h e possiamo usare que-sta informazione per ricavare una ricorrenza per il calcolo dei Th(x).Se da un albero con radice ternario di altezza al piu h + 1 cancelliamo laradice e tutti gli archi che escono da essa infatti, rimaniamo con una ter-na non ordinata di alberi con radice ternari di altezza al piu h; pertantopossiamo scrivere la relazione Th+1(x) = 1 + xZ3(Th(x)), dove il termine+1 tiene conto dell’albero vuoto (privo di vertici), l’unico non ottenibile dauna terna di alberi col procedimento descritto.

Tornando agli alcani, conteremo separatamente quelli che in letteratura so-no chiamati centrati e bicentrati.Sono detti centrati gli alcani con diametro pari, che possiedono un elemen-to (il centro) che si trova a meta di un percorso di lunghezza massima,mentre quelli di diametro dispari, detti bicentrati, possiedono due elemen-ti a meta di un percorso di lunghezza massima.

Consideriamo gli alcani bicentrati di diametro 2h + 1; cancellando l’arcoche congiunge i due centri possiamo metterli in corrispondenza biunivocacon le coppie non ordinate di alberi con radice ternari di altezza esatta-mente h, i quali sono enumerati da Th(x) − Th−1(x), quindi gli alcani bi-centrati di diametro h sono enumerati da B2h+1(x) = Z2(Th(x)− Th−1(x)).Sommando sui diametri troviamo la serie generatrice degli alcani bicentra-

ti B(x) =∑

h≥0

B2h+1(x).

Gli alcani centrati sono piu faticosi da contare, infatti se ne prendiamo unodi diametro 2h e cancelliamo il centro, otteniamo una quaterna non ordi-nata di alberi con radice ternari di altezza al piu h−1 e tali che almeno duedi essi hanno altezza esattamente h− 1. Queste sono enumerate da

(1+xZ4(Th−1(x)))−(1+xZ4(Th−2(x)))−(Th−1(x)−Th−2(x))(Th−1(x)−1).

Chiamiamo C2h(x) questa espressione. I primi due termini della sommatengono conto delle quaterne costituite da alberi di altezza al piu h−1 e al-beri di altezza al piu h−2, la loro differenza quindi enumera le quaterne dialberi di altezza al piu h−1 tali che almeno uno di essi ha esattamente quel-l’altezza; per ottenere gli alcani che cerchiamo dobbiamo ancora togliere glialberi con radice con esattamente un sottoalbero con altezza h−1, che sonoenumerati dal prodotto (Th−1(x) − Th−2(x))(Th−1(x) − 1).

Come prima, sommando sui diametri otteniamo la serie che enumera gli

25


alcani centrati C(x) =∑

h≥0 C2h(x).

La somma delle due serie B(x) e C(x) e la serie che enumera gli alcani, edil coefficiente del suo termine xl e il numero di alcani con l atomi di carbo-nio.Sebbene, come spesso accade in questi casi, non si e ottenuta una formulaesplicita, abbiamo ricondotto il calcolo del numero di alcani a manipola-zioni algebriche di polinomi facilmente trattabili. Come esempio abbiamoscritto un programma in C++ che ha generato i primi 100 termini dellasuccessione (il centesimo e un numero di 40 cifre) in circa 1.7s .

n alcani n alcani

1 1 26 938394122 1 27 2402158033 1 28 6171056144 2 29 15905071215 3 30 41118467636 5 31 106603077917 9 32 277112537698 18 33 722140886609 35 34 18862623613910 75 35 49378295290211 159 36 129529758812812 355 37 340449078016113 802 38 896474747459514 1858 39 2364747893396915 4347 40 6248180114734116 10359 41 16535145553578217 24894 42 43824289476922618 60523 43 116316970788642719 148284 44 309146101183685620 366319 45 822716237222120321 910726 46 2192183408668341822 2278658 47 5848180662198701023 5731580 48 15619236647459063924 14490245 49 41761240076538227225 36797588 50 1117743651746953270

26

Appendice B

Notazioni e definizioni

D insieme finito di cardinalita d

R insieme finito di cardinalita r (colori)

RD colorazioni diD

G gruppo finito che agisce su D e su RD

Oγ orbita della colorazione γ

Stabγ stabilizzatore della colorazione γ

Fixσ punti fissi della permutazione σ

∆ insieme di rappresentanti per le orbite dell’azione di G su RD

Sγ e un insieme di rappresentanti per le classi laterali di Stabγ

K campo di caratteristica 0

V spazio vettoriale su K di dimensione r su K

U =⊗d V prodotto tensore di d copie di V

eγ = eγ(1) ⊗ · · · ⊗ eγ(d) base canonica del prodotto tensore

P (σ)eγ = eγσ−1 operatore di permutazione

λ : G −→ K∗ un carattere di G in K

27


T λG = 1

|G|

∑

σ∈G

λ(σ)P (σ) operatore di simmetria

W : RD → K funzione peso

Uα = Span{eγ |W (γ) = α}

Pα(σ) = P (σ)|Uαla restrizione di P (σ) a Uα

TαG = TG|Uα

la restrizione di TG a Uα

PW (σ) =⊕

α∈K

αPα(σ) operatore di permutazione pesato

TWG =

⊕

α∈K

αTαG operatore di simmetria pesato

e♯γ = 1

|G|

∑

σ∈G

P (σ)eγ

∆ = {γ ∈ ∆ |∑

σ∈Stabγ

λ(σ) 6= 0} sistema parziale di rappresentanti per le

orbite dell’azione di G su RD

e∗γ =∑

σ∈G

λ(σ)P (σ)eγ

(aij) una matrice d× r

xi =∑

j∈R

ai jej

A(γ) =∑

σ∈Sγ

λ(σ)∏

t∈D

at γσ(t)

fσ(eγ) =

{

eγ se σ ∈ Stab γ

0 altrimenti

Qλ = 1|G|

∑

σ∈G

λ(σ)fσ

a(γ) = 1|Sγ |

∑

σ∈Sγ

∏

t∈D

at γσ(t)

Dσ1 ∪ · · · ∪ Dσ

p = D la decomposizione in orbite di D data dall’azione delgruppo ciclico 〈σ〉

l = l1 ⊗ · · · ⊗ ld e un funzionale lineare omogeneo in U∗

28

B. NOTAZIONI E DEFINIZIONI

Ak i =∏

j∈Dσk

aφ−1(j) i lj(ei) k = 1, . . . , p; i ∈ R

speγ = X(γ)pP(γ)|Oγ |

ℓeγ = 1

J =∑

γ∈RD

eγ

29


30

Bibliografia

[Bek92] R. A. BEKES, An infinite version of the Polya enumeration theorem,Internat. J. Math. & Math. Sci. 15(4) (1992), 697–700.

[DB71] N. G. DE BRUIJN, A survey of generalizations of Polya’s enumerationtheory, Nieuw Archief voor Wiskunde 19(2) (1971), 89–112.

[Ili00] V. V. ILIEV, On a new approach to Williamson’s generalization ofPolya’s enumeration theorem, Serdica Math. J. 26 (2000), 155–166.

[Pol37] G. POLYA, Kombinatorische Anzahlbestimmungen fur Gruppen,Graphen und Chemische Verbindungen, Acta Math. 68 (1937),145–254.

[RS99] E. M. RAINS E N. J. SLOANE, On Cayley’s enumeration of al-kanes (or 4-valent trees), Journal of integer sequences 2 (1999),www.cs.uwaterloo.ca/journals/JIS/.

[Tan] T. TAN, A simple proof of Polya’s theorem of counting,http://www.comp.nus.edu.sg/∼tantony/.

[Tuc74] A. TUCKER, Polya’s enumeration formula by example, Mathematicsmagazine 47(5) (1974), 248–256.

[Whi79] D. E. WHITE, Multilinear techniques in Polya enumeration theory,Linear and Multilinear Algebra 7 (1979), 299–315.

[Wil70] S. G. WILLIAMSON, Operator theoretic invarians and the enumera-tion theory of Polya ad De Bruijn, Journal of combinatorial theory 8(1970), 162–169.

[Wil71a] S. G. WILLIAMSON, Polya’s counting theorem and a class of tensoridentities, J. London Math. Soc. 3 (1971), 411–421.

[Wil71b] S. G. WILLIAMSON, Symmetry operators of Kranz products, Journalof combinatorial theory 11 (1971), 122–138.

31


[Wil72] S. G. WILLIAMSON, The combinatorial analysis of patterns and theprinciple of inclusion-exclusione, Discrete mathematics 1(4) (1972),357–388.

[WW76] D. E. WHITE E S. G. WILLIAMSON, Probabilistic analogs of Polya’senumeration theory, Linear and Multilinear Algebra 4 (1976), 21–30.

32

Il teorema di Polya ed alcune generalizzazioni - uz.sns.ituz.sns.it/~fvenez/tesi.pdf · ro di...

Documents

Transcript of Il teorema di Polya ed alcune generalizzazioni - uz.sns.ituz.sns.it/~fvenez/tesi.pdf · ro di...