Ingegneria Energetica - Analisi e Geometria 1

Completed notes of the course

Complete course

Matematica Discreta basato sull'omonimo corso tenuto dai proff. Roberto Dvornicich e Giovanni Gaif Anno Accademico 2014/15 - II semestre Oscar Papini ii Indice Simboli e notazioni utilizzativ Introduzionevii 1 Funzioni generatrici11.1 Primi esempi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.1 I numeri di Fibonacci. . . . . . . . . . . . . . . . . . . . . .4 1.1.2 Partizioni. . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 1.1.3 Parentesi di Catalan. . . . . . . . . . . . . . . . . . . . . . .9 1.2 Serie formali. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 1.3 Proprietà delle funzioni generatrici ordinarie. . . . . . . . . . . . .141.3.1 Somme parziali. . . . . . . . . . . . . . . . . . . . . . . . . .16 1.3.2 Fontana di monete. . . . . . . . . . . . . . . . . . . . . . . .19 1.4 Proprietà delle funzioni generatrici esponenziali. . . . . . . . . . .211.4.1 Numeri di Bell. . . . . . . . . . . . . . . . . . . . . . . . . .22 1.4.2 Permutazioni senza punti ssi. . . . . . . . . . . . . . . . .24 1.5 Serie di Dirichlet. . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 1.6 Carte, mani e mazzi (versione etichettata). . . . . . . . . . . . . . .301.6.1 Sottoclassi di permutazioni. . . . . . . . . . . . . . . . . . .35 1.6.2 Esempi sui gra. . . . . . . . . . . . . . . . . . . . . . . . . .37 1.7 Carte, mani e mazzi (versione non etichettata). . . . . . . . . . . .461.7.1 Partizioni di interi. . . . . . . . . . . . . . . . . . . . . . . .50 1.7.2 Problema di Frobenius. . . . . . . . . . . . . . . . . . . . . .52 1.8 Funzioni simmetriche. . . . . . . . . . . . . . . . . . . . . . . . . .56 2 Poset632.1 Prime denizioni. . . . . . . . . . . . . . . . . . . . . . . . . . . . .63 2.2 L'algebra di incidenza. . . . . . . . . . . . . . . . . . . . . . . . . .66 2.3 La funzione di Möbius. . . . . . . . . . . . . . . . . . . . . . . . . .73 2.4 Complessi simpliciali astratti. . . . . . . . . . . . . . . . . . . . . .79 iii iv Indice 2.5 Reticoli. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86 2.6 Arrangiamenti di iperpiani. . . . . . . . . . . . . . . . . . . . . . .952.6.1 Il polinomio caratteristico. . . . . . . . . . . . . . . . . . . .96 2.6.2 Regioni. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103 2.6.3 Combinatoria “quantizzata”. . . . . . . . . . . . . . . . . .110 2.6.4 Arrangiamenti e gra. . . . . . . . . . . . . . . . . . . . . .113 3 Teoria di Pólya-Redeld1193.1 Il Teorema di Pólya-Redeld. . . . . . . . . . . . . . . . . . . . . .119 3.2 Il polinomio indice dei cicli. . . . . . . . . . . . . . . . . . . . . . .127 3.3 Altri esempi di applicazione del Teorema di Pólya-Redeld. . . .132 3.4 Una versione più sottile del Teorema di Pólya-Redeld. . . . . . .136 4q-analoghi ecyclic sieving phenomenon141 4.1q-numero eq-fattoriale. . . . . . . . . . . . . . . . . . . . . . . . . .141 4.2 Ancora partizioni di interi. . . . . . . . . . . . . . . . . . . . . . . .143 4.3 Introduzione alcyclic sieving phenomenon. . . . . . . . . . . . . . .147 4.4 Cenni di teoria delle rappresentazioni. . . . . . . . . . . . . . . . .150 4.4.1 Denizione e primi risultati. . . . . . . . . . . . . . . . . . .150 4.4.2 Costruire nuove rappresentazioni. . . . . . . . . . . . . . .153 4.4.3 Il Lemma di Schur. . . . . . . . . . . . . . . . . . . . . . . .154 4.4.4 Caratteri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154 4.5 Ilcyclic sieving phenomenon. . . . . . . . . . . . . . . . . . . . . . . .159 4.6 Altri esempi dicyclic sieving phenomenon. . . . . . . . . . . . . . . .167 4.6.1 CSP e poligoni. . . . . . . . . . . . . . . . . . . . . . . . . .167 4.6.2 Permutazioni regolari. . . . . . . . . . . . . . . . . . . . . .169 5 Teoria di Ramsey1715.1 I Teoremi di Ramsey. . . . . . . . . . . . . . . . . . . . . . . . . . .171 5.2 Congurazioni geometriche con la teoria di Ramsey. . . . . . . .178 5.3 Il Teorema di van der Waerden. . . . . . . . . . . . . . . . . . . . .185 5.4 Cenni di ultraltri. . . . . . . . . . . . . . . . . . . . . . . . . . . . .190 A Ulteriori dimostrazioni193 B Numeri di Kirkman-Cayley203 C Svolgimento dell'Esercizio di pagina167213 Bibliograa217 Simboli e notazioni utilizzati NInsieme dei numeri naturali (02N) K;F qCampo, campo nito con qelementi Mmn( R) Spazio delle matricimna coefcienti inR Sn, A nGruppo simmetrico, gruppo alterno su nelementi Sn ,Dn Sfera, disco (chiuso)n-dimensionali R[X],R(X) ,Rv Xw Polinomi, funzioni razionali, serie formali a coefcienti in R (Xpuò essere un insieme arbitrario di indeterminate) Hom(V; W)Spazio degli omomorsmi daVinW End(V) =Hom(V; V), spazio degli endomorsmi diV GL(V) Gruppo generale lineare di V (gruppo degli automorsmi lineari diV) GLn( K) =GL(Kn )visto come sottogruppo diM n( K) rk(A)Rango diA tr(A)Traccia diA sp(A)Spettro diA, cioèfjautovalore perAg sgn()Segno di #( V) Cardinalità dell'insiemeV P(V),P k( V) Insieme delle parti di V, insieme delle parti di V di cardinalitàk AtBUnione disgiunta diAeB hViStruttura generata dall'insiemeV(dipende dal contesto) Prodotto scalare traaeb GCD(a; b)Massimo comun divisore fraaeb o,ONotazione o-piccolo, o-grande v vi Simboli e notazioni utilizzatiNota. Le variabili indicate in corsivo (come x) indicano oggetti con una sola componente, quelle in grassetto (come x) indicano oggetti con più componenti, come vettori o n-uple. Incognite o valori precisi sono generalmente indicati in minuscolo, mentre le indeterminate dei polinomi sono sempre indicate in maiuscolo. Una versione duale di un teorema ha lo stesso numero del teorema a cui si riferisce, seguito da un asterisco. Le versioni duali non sono dimostrate. IntroduzioneQuesto testo è basato sul corso di Matematica Discreta tenuto dai proff. Roberto Dvornicich e Giovanni Gaif durante il secondo semestre dell'anno accademico 2014/2015. Esso ripercorre quanto svolto durante il corso, seguendo la traccia degli appunti presi in classe. Purtroppo per problemi di sovrapposizione di orario non mi è stato possibile seguire tutte le lezioni del corso; ringrazio perciò tutti coloro che mi hanno permesso di usare i loro appunti per completare il lavoro, in ordine rigorosamente alfabetico: Elena, Francesca, Gianluca, Giulio, Pia e Sabino. Ovviamente mi assumo ogni responsabilità per gli eventuali errori presenti nel testo: invito chiunque ne trovi, sia di natura concettuale che ortograca, a segnalarmeli. Oscar Papini [email protected] Ultima revisione: 24 luglio 2015vii viii Introduzione Capitolo 1 Funzioni generatriciIn questo capitolo ci occuperemo di funzioni generatrici associate a una successione ›23/02/2015 (che nel nostro caso sarà denita da un qualche problema combinatorio). Le funzioni generatrici sono un modo condensato di rappresentare l'informazione combinatoria contenuta in una successione numerica; tuttavia la loro forma permette, attraverso opportune manipolazioni algebriche, di studiare le proprietà della successione pur non avendo necessariamente, ad esempio, una formula chiusa per l'n-esimo termine. Nonostante la prima sezione rappresenti solo un'infarinatura di quello che studieremo, per comprenderla meglio introduciamo subito gli oggetti protagonisti del capitolo. Denizione 1.1. Sia a= (a n) n2N una successione. Deniamo funzione generatrice (ordinaria)diala serie formale A(X) :=1 X n=0a nXn :(1.1) Denizione 1.2. Sia b= (b n) n2N una successione. Deniamo funzione generatrice esponenzialedibla serie formale B(X) :=1 X n=0b nn !X n :(1.2) 1.1 Primi esempi In questa sezione presenteremo una breve carrellata di esempi che useranno tecniche descritte più avanti. È utile comunque iniziare in questo modo per avere già in partenza un'idea di ciò che affronteremo.1 2 Capitolo 1. Funzioni generatriciEsempio 1.1 (Successioni ricorrenti I) .Vediamo un primo esempio di successione denita per ricorrenza. a0= 0 an+1= 2a n+ 1pern2N: Calcoliamo un po' di termini: a 0= 0 ,a 1= 1 ,a 2= 3 ,a 3= 7 ,a 4= 15 . . . Ci sembra di riconoscere unpattern: an= 2n -1:(1.3) Come possiamo dimostrare che la formula chiusa (1.3) è corretta? In questo caso è facile per induzione; vediamo invece come usare le funzioni generatrici. Dalla formula ricorsiva otteniamo 1 X n=0a n+1Xn =21 X n=0a nXn +1 X n=0X n cioè (osservando che la prima sommatoria è A (X) traslata, mentre la terza è una serie geometrica formale) A(X) -a 0X = 2A(X) +11 -X da cui (ricordando chea 0= 0) A(X) =X( 1-X)(1-2X): Ora imponiamo cheX( 1-X)(1-2X)= 1 -X+ 1 -2X per qualche,. Un semplice conto mostra che A(X) =X( 1-X)(1-2X)= 11 -2X- 11 -X=1 X n=02 n Xn -1 X n=0X n =1 X n=0( 2n -1)Xn e possiamo dunque concludere che la formula (1.3) è corretta. Esempio 1.2 (Successioni ricorrenti II) .Nell'esempio precedente la formula chiusa già si intuiva dopo pochi termini. Vediamone un altro meno evidente.a0= 1 an+1= 2a n+ npern2N: 1.1. Primi esempi 3 Sostituendo la denizione per ricorrenza nella funzione generatrice abbiamo 1 X n=0a n+1Xn =21 X n=0a nXn +1 X n=0nX n : A questo punto ci accorgiamo chenXn =X
nXn -1 =X
dd X( Xn ) dunqueA(X) -1X = 2A(X) +Xdd X11 -X= 2A(X) +X( 1-X)2; da cui con pochi conti A(X) =1 -2X+2X2( 1-X)2 (1-2X)= 21 -2X- 1( 1-X)2: Ricordiamo che la serie binomiale è (1+X) =1 X n=0  n Xn ; dove compare il coefciente binomiale generalizzato n := (-1)


(-n+1)n ! in cuiè un qualsiasi numero complesso. Nel nostro caso abbiamo (1-X)- 2 =1 X n=0 -2 n (-1)n Xn ed esplicitando il coefciente binomiale-2 n =(- 2)(-3)


(-n-1)n != (- 1)n (n+1) arriviamo inne a A(X) =21 X n=02 n Xn -1 X n=0( n+1)Xn : Il generico termine della successione è alloraa n= 2n +1 -n-1. 4 Capitolo 1. Funzioni generatrici 1.1.1 I numeri di Fibonacci La successione di Fibonacci è denita da8 > > < > > :f 0= 0 f1= 1 fn+2= f n+1+ f nper n2N: La funzione generatriceF(X)si ottiene facilmente dalla terza equazione: 1 X n=0f n+2Xn =1 X n=0f n+1Xn +1 X n=0f nXn cioèF(X) -f 1X -f 0X 2=F (X) -f 0X + F(X) da cui concludiamoF(X) =X1 -X-X2:La successione di Fibonacci è un caso particolare di ricorrenza lineare , cioè una successione denita da 8 > > > > > > > < > > > > > > > :a 0=  0 . . . ak-1=  k-1 aj+k=k -1 X i=0r ia j+iper j2N(1.4) in cui sono ssate le condizioni iniziali  0; : : : ;  k-1 . Vediamo solo un accenno di questa teoria, dal momento che anche per lo studio delle ricorrenze lineari useremo le funzioni generatrici. Denizione 1.3. Data una ricorrenza lineare della forma (1.4) , deniamo polino- mio caratteristicoil polinomio p(X) :=Xk - (r k-1Xk -1 +


+r 0) : Proposizione 1.4. Se il polinomio caratteristico ha kradici distinte 1; : : : ; k , allora il termine generale della successione per ricorrenza lineare è an= c 1 1n +


+c k kn dove i coefcientic 1; : : : ; c ksono determinati dalle condizioni iniziali. 1.1. Primi esempi 5La proposizione precedente non è più vera nel caso in cui p (X) abbia radici multiple. Ad esempio, è possibile dimostrare che se p(X) = (X-2)2 (X-3) , il termine generale è a n= c 12n +nc 22n +c 33n . In effetti, se t è una radice di molteplicitàm t, abbiamo an=


+ mt- 1( n) tn +


in cui mt- 1( n)è un polinomio di gradom t- 1inn. 1.1.2 Partizioni In questa sezione ci poniamo la seguente domanda: ssati n ek, in quanti modi è possibile partizionare l'insieme f1; : : : ; ng in esattamente k sottoinsiemi non vuoti? Indichiamo con  n k questo numero, e poniamo per convenzione0 0 =1; n 0 =0pern > 0; 0 k =0perk > 0: Ad esempio: in quanti modi possiamo spezzare in due parti un insieme di 5 elementi? Possiamo separaref1; : : : ; 5gin 1+4elementi in 5 1 =5modi; 2+3elementi in 5 2 =10modi; per un totale di 5 2 =15: In generale è un calcolo abbastanza complicato, inoltre questi numeri crescono molto velocemente al crescere di n ek. Tuttavia soddisfano una relazione per ricorrenza abbastanza semplice. In effetti, possiamo considerare f1; : : : ; ng= f1; : : : ; n-1g[fng ; di conseguenza, le partizioni di n elementi in kclassi sono date dalla somma di: 1. le partizioni in cui fng è una classe, che sono tante quante le partizioni di n-1ink-1classi; 2. le partizioni di n-1 in kclassi, in cui ne scegliamo una in cui mettere n (ed abbiamokpossibili scelte). 6 Capitolo 1. Funzioni generatrici In altre parole, vale che n k = n-1 k-1 +k n-1 k (si veda anche la Figura1.1).n n-1 k -1classi(a) fngè una classe a sé stante.n n-1 k classi(b) nè messo in una classe già esistente. Figura 1.1: I due casi per passare dan-1an. Abbiamo allora una successione che dipende da due parametri, n e k: ssandone uno per volta, otteniamo due funzioni generatrici An( Y) :=1 X k=0 n k Yk eB k( X) :=1 X n=0 n k Xn : Usando la formula ricorsivaBk( X) =1 X n=0 n-1 k-1 Xn +k1 X n=0 n-1 k Xn = =X
B k-1( X) +kX
B k( X) cioè otteniamo8 < :B k( X) =X1 -kXB k-1( X) B0( X) =1 da cui, induttivamente, Bk( X) =X k( 1-X)(1-2X)


(1-kX): Come nell'esempio precedente, vorremmo usare le funzioni razionali; quindi cerchiamo  1; : : : ;  ktali che 1( 1-X)(1-2X)


(1-kX)=k X j=1 j( 1-jX): (1.5) 1.1. Primi esempi 7Per determinare  r moltiplichiamo ambo i membri di (1.5) per (1-rX) e poi valutiamo in X=1=r . Così, nella sommatoria a destra, tutti gli addendi sono nulli tranne l' r-esimo (perché (1-rX) si è semplicato), lasciando solo  r . Di conseguenza r=1 1-1r  1-2r 


 1-r -1r  1-r +1r 


 1-kr  = = (-1)k -r1( r-1)!r k -1( k-r)!: Ora,  n k è il coefciente di X n in B k( X) =Xkk X j=1 j1 -jX , che è il coefciente di Xn -k ink X j=1 j1 -jX. Esplicitando la serie geometrica otteniamo k X r=1 r1 -rX=k X r=1 r1 X i=0r i Xi ed il coefciente cercato èk X r=1 rrn -k =k X r=1(- 1)k -rrnr !(k-r)!: A questo punto ci dedichiamo a contare le partizioni totali di f 1; : : : ; ng , cioè vogliamo sapere in quanti modi possiamo partizionare n elementi. Ovviamente tale numero è b(n) :=n X k=1 n k =n X k=1k X r=1(- 1)k -rrnr !(k-r)!: Sek > n, il numero di partizioni è 0; di conseguenza, possiamo scrivere b(n) =N X k=1k X r=1(- 1)k -rrnr !(k-r)! per ogni N>n , e potremo eventualmente estendere questa somma all'innito, dopo averla manipolata. Per prima cosa scambiamo gli ordini delle sommatorie, cambiando gli indici. La Figura1.2ci aiuta a visualizzare la situazione: in un caso si sommano prima 8 Capitolo 1. Funzioni generatrici krr =k1: : : N Figura 1.2: Coppie (k; r)interessate dalla sommatoria. le coppie in verticale, nell'altro prima le coppie in orizzontale. Si ottieneb(n) =N X k=1k X r=1(- 1)k -rrnr !(k-r)!= =N X r=1N X k=r(- 1)k -rrnr !(k-r)!= =N X r=1r nr !N X k=r(- 1)k -r( k-r)!= =N X r=1r nr !N -r X h=0(- 1)hh !dove nell'ultimo passaggio abbiamo cambiato la variabile in h:=k-r . A questo punto mandiamo N!1 : è noto che la serie P (-1)h =h !converge a 1= e. Il risultato nale è b(n) =1e 1 X r=1r nr !: (1.6) Vediamo cosa succede provando a calcolare la funzione generatrice esponen- zialeB(X)per la successioneb(n), usando il risultato (1.6): B(X) =1e 1 X n=0X nn !1 X r=1r nr !: L'addendo conn=0dà 1e 1 X r=11r != 1e
e=1; 1.1. Primi esempi 9 mentre il resto della serie può essere scritto come 1e 1 X n=1X nn !1 X r=1r nr != 1e 1 X r=11r !1 X n=1X nn !r n = =1e 1 X r=11r ! erX -1
= =1e 1 X r=1 eX
rr !- 1r !! = =1e  ee X -e =ee X -1 -1: In conclusione possiamo scrivereB(X) =ee X -1che è una formula estremamente compatta rispetto all'informazione contenuta in essa (ricordiamo che il coefciente dell' n-esimo termine nella sua espansione in serie esponenziale è il numero di partizioni totali din). 1.1.3 Parentesi di Catalan Studiamo ora un esempio classico di combinatoria. Supponiamo di avere un prodotto non associativo; se per esempio abbiamo cinque simboli x1; : : : ; x 5 possiamo calcolare (((x 1x 2) x 3) x 4) x 5 ((x 1x 2) x 3)( x 4x 5) ((x 1x 2)( x 3x 4)) x 5 . . . e ottenere risultati diversi. La domanda è: in quanti modi possiamo disporre delle parentesi (bilanciate) su n simboli? Denoteremo questo numero con cn , per n>1 .Ÿ1 I primi casi sono ovvi: c 1= c 2= 1 , infatti gli unici modi sono rispettivamente(x 1) e(x 1x 2) .Ÿ 2 Esiste una formula ricorsiva: pern>2 cn= c 1c n-1+ c 2c n-2+


+c n-1c 1: (1.7) In effetti, nel calcolo del prodotto nale, l'ultimo passaggio consiste nell'effettuare l'operazione sugli ultimi due prodotti parziali, in qualunque modo essi sianoŸ 1 Normalmente, in letteratura c n denota il numero di modi in cui si possono disporre parentesi intorno an+1simboli. Il lettore presti attenzione a questa piccola discrepanza. Ÿ2 Consideriamo uguali due modi che nel prodotto portano allo stesso risultato, ad esempio (x 1) x 2e (x 1x 2) . 10 Capitolo 1. Funzioni generatricistati ottenuti: il primo con i simboli x 1; : : : ; x i , il secondo con xi+1; : : : ; x n . In termini di parentesi questo vuol dire patternconnsimboli= (patternconisimboli)(patternconn-isimboli) per ognii=1; : : : ; n-1. Per calcolarec ndeniamo la funzione generatrice della successione C(T) :=1 X n=1c nTn che, sostituita nella relazione (1.7), soddisfa l'equazioneC(T) =c 1T + (C(T))2 ottenuta dall'espressione del prodotto di serie formali. Ricordando che c 1= 1 abbiamo(C(T))2 -C(T) +T=0 che ha per soluzioni (sceglieremo il segno più avanti) C(T) =1 p1 -4T2 : (1.8) Espandiamo in serie di potenze la radice:p1 -4T= (1-4T)1=2 =1 X n=0 1=2 n (-4)n Tn : Il coefciente diTn in questa espressione è 12
 -12 


 -2n -32 n !
(-4)n (1.9) che è negativo (se n è pari ho un numero dispari di segni meno nel binomiale generalizzato; viceversa se n è dispari, il segno meno è dato da (-4)n ). Quindi scegliamo il segno meno nella formula (1.8) , in modo da avere C (T) a termini positivi. Ora, si verica che il prodotto dei primin-1dispari (1compreso) è n-1 Y k=1( 2k-1) =1
3


(2n-3) =( 2n-2)!2 n -1 (n-1)!; quindi in denitiva c n , che in base alla Formula (1.8) è dato da (1.9) moltiplicando per-1=2, vale cn=12
12 n
( 2n-2)!2 n -1 (n-1)!
4 nn != 1n
( 2n-2)!( n-1)!(n-1)!= 1n  2n-2 n-1 : 1.2. Serie formali 11È facile mostrare che c n , nonostante la presenza di 1=n , è un numero intero: abbiamo ncn= 2n-2 n-1 2Z e dalle proprietà dei coefcienti binomiali (n-1)c n= 2n-2 n 2Z; quindi anchec n= nc n- ( n-1)c n2 Z. Osservazione. I numeri di Catalan emergono in molti contesti combinatori. Ad esempio: supponiamo di avere un poligono convesso di n+1 lati e di volerlo suddividere in triangoli tracciandone le diagonali (senza che esse si intersechino). Il numero di possibili suddivisioniŸ 3 è proprioc n.Figura 1.3: Le 5 possibili suddivisioni in triangoli di un pentagono. 1.2 Serie formali Ricordiamo in questa sezione la denizione e alcune proprietà dell'anello delle ›04/03/2015 serie formali in una indeterminata. Denizione 1.5. Sia R un anello (commutativo con identità). Si denisce serie formalea coefcienti inRuna scrittura del tipo 1 X n=0a nXn ; dovea n2 Rper ognin2NeXè un simbolo di indeterminata. L'insieme delle serie formali a coefcienti in R è indicato con Rv Xw .Ÿ 4 Su tale insieme si può mettere una struttura di anello (commutativo con identità) denendo la somma puntualmente 1 X n=0a nXn! + 1 X n=0b nXn! :=1 X n=0( a n+ b n) XnŸ 3 Attenzione! Due suddivisioni che differiscono per una rotazione o una simmetria sono considerate diverse! Ÿ4 Noi tratteremo sempre le serie a coefcienti inC, se non diversamente specicato. 12 Capitolo 1. Funzioni generatrici e il prodotto alla Cauchy 1 X n=0a nXn!
1 X n=0b nXn! :=1 X n=00 @n X j=0a jb n-j1 AXn :Rispetto a queste operazioni, l'elemento neutro della somma è la serie con tutti i coefcienti uguali a 0, mentre quello del prodotto è la serie 1, cioè quella con an= 0pern6 =0ea 0= 1. Proposizione 1.6. In Rv Xw , la serie P anXn è invertibile se e solo se a 0 è invertibile inR. Dimostrazione.) Supponiamo che P bnXn sia l'inversa di P anXn . Dalla denizione di prodotto di serie si ha a 0b 0= 1, quindia 0è invertibile. ( Supponendo che a0 sia invertibile, si possono costruire i coefcienti bn dell'inversa. Infatti, ammettendo che la serie inversa P bnXn esista e imponendo (P anXn )(P bnXn )=1, si ottengono le relazioni 8 > > < > > :a 0b 0= 1 n X j=0a n-jb j= 0pern > 0 da cui si ricava b 0= a 0- 1 e, supponendo di aver costruito induttivamente b 0; : : : ; b n-1, bn= a 0- 10 @-n -1 X j=0a n-jb j1 A: Questo dimostra la tesi. Sulle serie formali è possibile denire anche un'operazione di composizione: sef(X) =P anXn eg(X) =P bnXn , poniamo (fg)(X) :=f(g(X)) =1 X n=0a n( g(X))n : Questa operazione, tuttavia, non è sempre ben denita: se b06 =0 , infatti, il termine noto difgè (fg) 0=1 X n=0a n( b 0)n che non è una quantità ben denita. D'altra parte, se b 0= 0 , la composizione è ben denita: in tal caso il primo termine di (g(X))n ha grado n, quindi tale serie 1.2. Serie formali 13non contribuisce ai termini di grado inferiore nella composizione f g , i quali dunque sono il risultato di una somma nita. Esiste un'identità per il prodotto di composizione, che è chiaramente la “serie” id(X) =X . D'altra parte, l'insieme delle serie formali con la somma usuale e il prodotto di composizione non è un anello: in generale non vale la proprietà distributiva, cioè esistono serief,gehtali chef(g+h)6 =fg+fh. Proposizione 1.7. Sia f(X) =P anXn 2Cv Xw con a 0= 0 . La serie fè invertibile rispetto alla composizione se e solo sea 16 =0. Dimostrazione.) Supponiamo che g(X) :=P bnXn sia tale che ( fg)(X) =X e sianor>1,s>1i più piccoli indici per i quali rispettivamentea r6 =0eb s6 =0. Scrivendo esplicitamente la composizione fg osserviamo che il termine di grado minimo èa rb sXrs . Imponendo chefg=id si ha rs=1 r; s2Nrf0g arb s= 1; da cui otteniamor=s=1ea 16 =0(e ancheb 16 =0). ( Si procede in modo simile alla dimostrazione della Proposizione1.6. Abbia- mo visto nella prima parte della dimostrazione che, se esiste l'inversa compositivaPbnXn , dev'essere b 1:= a 1- 1 . A questo punto ci chiediamo: chi è il generico termine di gradokinfg? Un semplice conto mostra che (fg) k= a 1b k+ polinomio ina ie b jcon j < k: Imponendo che tale coefciente sia nullo si ricava b k in funzione di b1; : : : ; b k-1 . Terminiamo questa breve presentazione delle serie formali con un'operazione unaria: la derivata formale. Se f(X) =1 X n=0a nXn è una serie, deniamo la sua derivata comedd Xf (X) =f0 (X) :=1 X n=1na nXn -1 : È immediato osservare che1.f0 =0se e solo sef=a 0; 14 Capitolo 1. Funzioni generatrici 2. f0 =fse e solo sef=ceX , dovecè una costante e eX :=1 X n=0X nn !:In effetti, da f 0 =f si ha che (n+1)a n+1= a n , da cui a n+1= a n= (n+1) ; ssato a 0= c, induttivamente si ricavaa n= c=n!. 1.3 Proprietà delle funzioni generatrici ordinarie Abbiamo visto la denizione di funzione generatrice ordinaria (Denizione1.1a pagina1). Per noi an sarà il valore della soluzione di un problema combinatorio nel caso n. In questa sezione esporremo qualche proprietà che ci permette di calcolare funzioni generatrici di successioni più complicate a partire da mattoncini semplici. In ogni proprietà, a= (a n) n2N sarà una successione e f(X) :=P anXn la corrispondente funzione generatrice. Proprietà 1 (shift ).Se a= (a n) n2N è una successione, deniamo shiftata la successione Sa il cui termine n-esimo è (Sa) n:= a n+1 per ogni n2N . La funzione generatrice associata aSaè f(X) -f(0)X : Dimostrazione.Naturalmentef(X) -f(0) =1 X n=0a n+1Xn +1 , da cui la tesi.Proprietà 2 (shift iterato) .Se a = (a n) n2N è una successione e h2N , deniamo shiftata di hla successione S ha il cui termine n-esimo è ( S ha ) n:= a n+h per ogni n2N. La funzione generatrice associata aS ha è 1X h0 @f(X) -h -1 X j=0a jXj1 A: Dimostrazione. È un'applicazione iterata della Proprietà1. Più esplicitamente, si haf(X) -h -1 X j=0a jXj =1 X n=0a n+hXn +h da cui la tesi. 1.3. Proprietà delle funzioni generatrici ordinarie 15 Proprietà 3(moltiplicazione per n).Alla successione ( na n) n2N è associata la funzione generatrice X
dd Xf (X): Dimostrazione.Per il terminen-esimo vale X
dd X( a nXn )=X
na nXn -1 =na nXn :Proprietà 4 (moltiplicazione per un polinomio in n).Se p (T)2C[T] è un polinomio, allora alla successione (p(n)a n) n2N è associata la funzione generatrice p X
dd X f(X): Dimostrazione. È un'applicazione iterata della Proprietà3. Attenzione! In questo caso X
dd X 2 f(X) =X
dd X X
dd X( f(X)) cioè è una potenza di composizione dell'operatoreX
d=dX.Esempio 1.3.Sia data la successione a0= 1 (n+1)a n+1= 3a n+ 1pern2N: Notiamo che (n+1)a n+1 è il termine n-esimo di S((na n) n2N) . Se f (X) = P anXn è la funzione generatrice per ( a n) , applicando prima la Proprietà3e poi la Proprietà1abbiamo che la funzione generatrice per S((na n) n2N) è g(X) -g(0)X ; dove g (X) =X
dd Xf (X) . Esplicitando i conti risulta che tale funzione generatrice non è altro che f0 (X) , quindi per trovare fè sufciente risolvere l'equazione differenziale f0 (X) =3f(X) +11 -X in cui la serie geometrica è data dal contributo del termine +1 . Se per esempio so- stituiamo tale termine con +1=n !nella formula ricorsiva, l'equazione differenziale da risolvere diventa f0 (X) =3f(X) +eX : 16 Capitolo 1. Funzioni generatrici Esempio 1.4.Vogliamo calcolare 1 X n=0n 2 +4n+9n !: Lavoriamo per gradi:1.sappiamo che la serie eX corrisponde alla successione(1=n!); 2.dalle Proprietà3e4abbiamo che a (n=n !)corrisponde X
eX, mentre a (n2 =n!)corrisponde(X+X2 )
eX ; 3. di conseguenza alla successione ((n2 +4n+9)=n !)corrisponde (X2 +5X+ 9)
eX . Notiamo ora che, sef(X) =P anXn , 1 X n=0a n= f(1): Quindi la somma richiesta è15e. 1.3.1 Somme parziali Studieremo qui ulteriori proprietà che legano le funzioni generatrici di una successione con quelle delle loro somme parziali. Iniziamo con un esempio: al primo anno di matematica generalmente viene data una formula che esprime “la somma delle prime N potenze k-esime” e viene richiesto di dimostrare la formula per induzione. Ma come si fa a trovare la formula?Sappiamo cheN X n=0X n =X N +1 -1X -1 e la prima è la serie generatrice per la successione che vale 1per n6N e0altrove. Allora possiamo moltiplicare la successione per nk (Proprietà4) e ottenere la serie N X n=0n k Xn = X
dd X k XN +1 -1X -1 : Un computer è in grado di calcolare l'espressione sulla destra e valutarla in X=1 per ottenere la formula chiusa richiesta. 1.3. Proprietà delle funzioni generatrici ordinarie 17 Proprietà 5(Prodotto di serie) .Se f (X) è la funzione generatrice della successione (a n) eg(X)è quella per(b n) , alloraf(X)
g(X)è la funzione generatrice per n X k=0a kb n-k! n2N Dimostrazione. Discende immediatamente dalla denizione di prodotto tra serie formali.Proprietà 6 (Potenza di serie).Alla serief(X)k è associata la successione 0 B B @X i1;:::;i k2 N i1+


+i k= na i1


a ik1 C C A n2N Dimostrazione.È un'applicazione iterata della Proprietà5. Esempio 1.5 .Se f(X) =1=(1-X) =P Xn , allora il termine di grado n in f (X)k = 1=(1-X)k è il numero di modi in cui si può scrivere n come somma di knumeri naturali. Ma noi sappiamo chi è il coefciente del termine di grado nin ( 1-X)- k : è  -k n (-1)n =(- k)(-k-1)


(-k-n+1)n !(- 1)n = k+n-1 n : Proprietà 7 (Prodotto per la serie geometrica) .Se f(X) è la funzione generatrice per(a n) , allora 11 -X
f(X) è quella associata alla successione di somme parziali0 @n X j=0a j1 An2N Dimostrazione.Dalla Proprietà5, il termine di gradokin(P Xn )(P anXn )è 1
a 0+ 1
a 1+


+1
a k: Esempio 1.6 .Ricaviamo la nota formula per la somma dei primi n quadrati. Iniziamo dalla successione costante ( 1) n2N , cui è associata la serie geometrica. Dalla Proprietà4ricaviamo la serie associata a(n2 ), che è X
dd X 2 11 -X : 18 Capitolo 1. Funzioni generatriciQuindi per la Proprietà7alla successione delle somme ( P j2 ) è associata la serie 11 -X
 X
dd X 2 11 -X ; la quale si può riscrivere dopo qualche conto comeX(1+X)( 1-X)4: (1.10) Ora, il coefciente diXn in(1-X)- 4 è -4 n (-1)n =4
5


(n+3)n != n+3 n : Riscrivendo (1.10) comeX( 1-X)4+X 2( 1-X)4 ci accorgiamo che il coefciente di Xn in (1.10) è dato dalla somma di uno shift di 1(moltiplicazione per X) e uno shift di 2(moltiplicazione per X2 ) rispetto a quello nella serie (1-X)- 4 . In denitiva, dunque, la formula chiusa è n+2 3 + n+1 3 =n (n+1)(2n+1)6 : Esempio 1.7 .Vediamo qual è la funzione generatrice associata alla serie armonica troncata, ovvero alla successione Hn:= 1+12 +


+1n : Il termine n-esimo di questa successione è asintotico a ln n :Ÿ5 questo fatto discende dal criterio del confronto integrale, in quantoH nsi stima con Zn 11t d t: In effetti, la successione(1=n)ha come funzione generatrice 1 X n=1X nn = - ln(1-X) da cui ricaviamo che la funzione generatrice per(H n) è -ln(1-X)1 -X:Ÿ 5 In effetti, possiamo scrivere Hn= lnn+ +o 1n  dove 0:577 è la costante di Eulero-Mascheroni . Si suppone che sia un numero trascendente; al momento non sappiamo nemmeno se sia razionale. 1.3. Proprietà delle funzioni generatrici ordinarie 19 1.3.2 Fontana di moneteLa fontana di monete è un gioco combinatorio che consiste nell'impilare delle monete seguendo alcune regole. Si comincia con n monete; si sceglie un numero 0 6k6n-1 e si dispongono kmonete consecutivamente sopra le prime n monete; quindi si sceglie un numero 06m6k-1 di monete da disporre sul secondo piano e così via (si veda la Figura1.4). La domanda è: quante fontane distinte si possono costruire se al piano terra ci sononmonete?Figura 1.4: Una possibile fontana di monete. Sia f (n) il numero di fontane costruibili a partire da n monete. Per conven- zione poniamo f(0) :=1 (la “fontana vuota”). Esiste una relazione di ricorrenza perf: sek > 0vale chef (k) =1+k -1 X j=1( k-j)f(j)1. Fermiamo la fontana oppure. . .2. . . . scegliamo j>1monete per il piano successivo.3. Abbiamo k-jscelte per il punto di partenza.4. Costruiamo iterativamente una fontana partendo dajmonete. Chiamiamo F(X) la funzione generatrice associata a (f(n)) . Notiamo che, se calcoliamo il prodotto di serie 1 X n=0f (n)Xn!
1 X n=0nX n! ; 20 Capitolo 1. Funzioni generatrici il termine n-esimo risulta cn:=n X j=0( n-j)f(j) =0
f(n) +n
f(0) +n -1 X j=1( n-j)f(j) =n+n -1 X j=1( n-j)f(j): Quindif(n) =1-n+c ne F(X) =1 X n=0( 1-n+c n) Xn =1 X n=0( 1-n)Xn +F(X)
1 X n=0nX n! = =1 -2X( 1-X)2+ F(X)X( 1-X)2: Con pochi passaggi si arriva inne aF(X) =1 -2X1 -3X+X2:Proviamo a calcolare f (n) per qualche valore di n (Tabella1.1). Si riconosce una certa regolarità? In effetti, sono tutti numeri di Fibonacci, e precisamenten 0 1 2 3 4 5 6 f (n)1 1 2 5 13 34 89Tabella 1.1: Valori di f(n)pern66. quelli di indice dispari. Congetturiamo alloraf(n) =F 2n-1 (ponendoF -1= 1per convenzione, in modo cheF -1+ F 0= F 1). Proviamo a dimostrarlo con le funzioni generatrici. Se F(X) =X1 -X-X2 è la funzione generatrice per i numeri di Fibonacci (vedi Sezione1.1.1), allora la sua parte dispari è F(X) -F(-X)2 =1 X n=0F 2n+1X2n +1 : QuindiXF (X) -F(-X)2 + F -1= F -1+1 X n=0F 2n+1X2n +2 =1 X k=0F 2k-1X2k 1.4. Proprietà delle funzioni generatrici esponenziali 21 Figura 1.5: Le 13 possibili fontane a partire da 4 monete.dove nell'ultimo passaggio abbiamo posto k :=n+1 . Per avere la tesi è sufciente vericare che quest'ultima espressione sia uguale a F(X2 ) . Proviamo a calcolarla: XF (X) -F(-X)2 + F -1=X2  X1 -X-X2+X1 +X-X2 +1=1 -2X21 -3X2 +X4 che è proprioF(X2 ). La congettura è dunque dimostrata. 1.4 Proprietà delle funzioni generatrici esponenziali Vediamo quali sono le proprietà analoghe a quelle della Sezione1.3per le ›09/03/2015 funzioni generatrici esponenziali, denite a pagina1. Al solito, supporremo che a= (a n) n2N sia una successione e f(X) :=P anXn =n !la corrispondente funzione generatrice esponenziale. Proprietà E1(shift).La funzione generatrice esponenziale associata aSaè f0 (X) =dd Xf (X): Dimostrazione.Basta vericarlo sui monomi: dd X anX nn ! =a n( n-1)!X n -1 :Proprietà E2 (shift iterato) .La funzione generatrice esponenziale associata a S ha è f( h) (X) = dd X h f(X): Dimostrazione.È un'applicazione iterata della ProprietàE1. 22 Capitolo 1. Funzioni generatrici Proprietà E3(moltiplicazione per n).Alla successione ( na n) n2N è associata la funzione generatrice esponenziale X
dd Xf (X): Dimostrazione.Per il terminen-esimo vale X
dd X anX nn ! =X
a n( n-1)!X n -1 =na nX nn !:Proprietà E4 (moltiplicazione per un polinomio in n).Se p (T)2C[T] è un polinomio, allora alla successione (p(n)a n) n2N è associata la funzione generatrice esponenziale p X
dd X f(X): Dimostrazione.È un'applicazione iterata della ProprietàE3.Proprietà E5 (Prodotto di serie) .Se f (X) è la funzione generatrice esponenziale della successione (a n) eg (X) è quella per (b n) , allora f (X)
g(X) è la funzione generatrice esponenziale per n X k=0 n k akb n-k! n2N Dimostrazione.Per la denizione di prodotto di serie, il terminen-esimo è n X k=0a kk !b n-k( n-k)!X n =n X k=0n !k !(n-k)!a kb n-kX nn !:1.4.1 Numeri di Bell Nella Sezione1.1.2abbiamo calcolato il numero b (n) di partizioni totali di un insieme di n elementi. Tali numeri sono detti numeri di Bell . Ora che abbiamo un po' più di teoria, proviamo a calcolare direttamente la funzione generatrice esponenziale. Per i numerib(n)vale una formula ricorrente: pern2N, b(n+1) =n X k=0 n k b(k)(1.11) e per convenzione b(0) =1 (la “partizione vuota”). Infatti, per contare le partizioni basta: 1.4. Proprietà delle funzioni generatrici esponenziali 23 1.isolare un sottoinsieme appartenente alla partizione; 2.considerare ricorsivamente le partizioni del complementare di quel sottoin- sieme. Al variare dei possibili sottoinsiemi isolati si hanno tutte le partizioni. Attenzione, però: in questo modo si conta la stessa partizione più volte prendendo sottoin- siemi isolati disgiunti (se A,B sono sottoinsiemi disgiunti, le due partizioni A[fpartizione diAc che contieneBg eB[fpartizione diBc che contieneAg in realtà sono la stessa). Il trucco è ssare un elemento di f1; : : : ; n+1g e isolare solo sottoinsiemi che contengono quell'elemento. In questo modo siamo sicuri di contare le partizioni una sola volta. Dunque, ssiamo a2f1; : : : ; n+1g e consideriamo i sottoinsiemi di f1; : : : ; n+1g di cardinalità hche contengono a. Il loro numero è  n h-1 eh varia tra 1(avi appartiene sempre) e n +1 . Per ognuno di essi, il complementare ha cardinalitàn+1-he può essere partizionato inb(n+1-h)modi. Quindi b(n+1) =n +1 X h=1 n h-1 b(n+1-h) = =n +1 X h=1 n n-h+1 b(n+1-h) =n X k=0 n k b(k) in cui nell'ultimo passaggio si è postok:=n-h+1. A questo punto calcoliamo la funzione generatrice esponenziale per entrambi i membri dell'Equazione (1.11): detta B(X) =1 X n=0b (n)X nn !; a sinistra abbiamoB0 (X)per la ProprietàE1, mentre a destra 1 X n=0n X k=0 n k b(k)X nn !=1 X n=0n X k=01k !(n-k!)b (k)Xn = = 1 X n=0b (n)X nn !!
1 X n=0X nn !! =B(X)eX per la ProprietàE5. Abbiamo dunque l'equazione differenzialeB0 (X) =B(X)eX (1.12a) B(0) =b 0= 1:(1.12b) 24 Capitolo 1. Funzioni generatriciDall'Equazione (1.12a) si ha B 0 (X)=B(X) = eX, da cui integrando otteniamo lnB(X) = eX +c (con c costante che determineremo fra poco) e nalmente B(X) = eeX +c . Imponendo le condizioni (1.12b) troviamo c= -1 e possiamo scrivere inne B(X) =ee X -1 in accordo con quanto visto nella Sezione1.1.2. 1.4.2 Permutazioni senza punti ssi Sia Sn il gruppo simmetrico su n elementi, cioè il gruppo delle permutazioni di f1; : : : ; ng . Vogliamo contare le dismutazioni all'interno di S n , cioè le permutazioni senza punti ssi. Chiamiamo dn:= #f2S nj 8k=1; : : : ; n (k)6 =kg:Ÿ 6 I valori iniziali sono d 0= 1 (la permutazione su 0elementi, in effetti, non ha punti ssi. . . ) e d 1= 0 (l'unica permutazione di un elemento lo lascia ovviamente sso). Anche in questo caso esiste una formula ricorrente: n!=n X k=0 n k dn-k: Infatti il numero totale di permutazioni (che è # ( S n) =n !) è la somma dei numeri di permutazioni che lasciano ssi esattamente kelementi, per k=0; : : : ; n . Questi sono dati dalla scelta dei kpunti da ssare (in  n k modi) e, una volta scelti, da d n-kmodi di permutare i restanti elementi (senza lasciarne alcuno sso). Detta D (X) la funzione generatrice esponenziale per i d n , dalla formula ricorrente si ha 11 -X= eX D(X) perché a sinistra il fattoriale si semplica e resta una serie geometrica, mentre a destra riconosciamo ancora una volta un prodotto di serie. In denitiva D(X) =e - X1 -X: Quest'espressione, unitamente all'espansione di e- X e alla Proprietà7sul pro- dotto per una serie geometrica, ci permette di calcolare una formula chiusa per d n: dnn !=n X k=0(- 1)kk !:Ÿ 6 Questo numero è a volte chiamatosubfattorialedined indicato con !n. 1.5. Serie di Dirichlet 25 1.5 Serie di DirichletEsistono altri modi per associare una serie a una successione di valori, alcuni migliori di altri a seconda del contesto. Vediamone uno usato particolarmente in Teoria Analitica dei Numeri. Denizione 1.8. Data una successione (a n) n2Nrf0g , deniamo serie di Dirichlet la serie formale A(s) :=1 X n=1a nn s: La serie di Dirichlet più famosa è probabilmente quella associata alla succes- sione che vale costantemente 1ed è nota comefunzione zeta di Riemann: (s) :=1 X n=11n s: Proprio come succedeva con le serie di potenze, in cui trattando l'indetermi- nata X come numero complesso aveva senso porsi domande sulla convergenza della serie, possiamo chiederci cosa succede se il parametro formale sè visto come numero complesso. A differenza delle serie di potenze, in questo caso non c'è un raggio di convergenza, ma una retta di convergenza : in particolare la serie converge per il semipiano r per un certo valore rche naturalmente dipende dalla serie. Ad esempio,(s)converge per 1. Ci piacerebbe ora che il prodotto di due serie di Dirichlet sia ancora una serie di Dirichlet. In effetti, così è: moltiplicando tra loro il generico termine h-esimo diP an=ns e quellok-esimo diP bn=ns si ottiene ahh sb kk s=a hb k( hk)s che è una parte del termine ( hk) -esimo. Osserviamo dunque che i contributi al termine n-esimo del prodotto sono dati dai termini h-esimi della prima serie e k-esimi della seconda per ognih,ktali chehk=n. In altre parole, se 1 X n=1a nn s!
1 X n=1b nn s! =1 X n=1c nn s; alloracn=X hk=na hb k=X djna db n=d: (1.13) Questo è chiamatoprodotto di convoluzione di Dirichlet. Le serie di Dirichlet sono importanti soprattutto per lo studio di un tipo di successioni che si incontra spesso in Teoria dei Numeri. 26 Capitolo 1. Funzioni generatrici Denizione 1.9.La successione f (n) è detta moltiplicativa se f(mn) =f(m)f(n) ogni volta che GCD(m; n) =1 ;completamente moltiplicativa se f(mn) =f(m)f(n) per ognim; n2N. Ovviamente le successioni moltiplicative sono univocamente determinate dal valore che assumono sulle potenze dei primi, in virtù del Teorema Fondamentale dell'Aritmetica. Ci aspettiamo che anche le serie di Dirichlet associate a una successione moltiplicativa abbia un comportamento analogo. Teorema 1.10.Siaf(n)una successione moltiplicativa. Allora 1 X n=1f (n)n s=Y pprimo 1+f (p)p s+f (p2 )p 2s+f (p3 )p 3s+ : : : :(1.14) L'idea è che tutti i termini nella serie a sinistra di (1.14) si ottengono in modo unico scegliendo uno e un solo termine da ciascun fattore sulla destra, proprio grazie all'unicità della fattorizzazione in primi. Se inoltre f(n) è completamente moltiplicativa, possiamo scrivere f(pm ) = f(p)m per ogni pprimo e per ogni m, ottenendo serie geometriche nei fattori a destra in (1.14). Corollario 1.11.Sef(n)è completamente moltiplicativa, allora 1 X n=1f (n)n s=Y pprimo 1-f (p)p s -1 : Ad esempio, per la zeta di Riemann vale(s) =Y pprimo 1-1p s -1 :(1.15) Notiamo che, poiché GCD(n; 1) =1 per ogni n, afnché f(n) =f(n
1) = f(n)f(1) dev'essere f(1) =1 . L'insieme delle funzioni moltiplicative dotato del prodotto di convoluzione, denito in (1.13) ed indicato con f?g , formano un gruppo in cui l'elemento neutro è "(n) := 1sen=1 0sen > 1: Se chiamiamo 1(n) la successione associata a (z) , cioè 1(n) =1 per ogni n, allora possiamo calcolare1- 1 grazie alla Formula (1.15): infatti (s)- 1 =Y pprimo 1-1p s =1 X n=1 (n)n s; 1.5. Serie di Dirichlet 27 in cui (n)è lafunzione di Möbiusdenita sulle potenze dei primi da (pa ) :=8 > > < > > :1 sea=0 -1sea=1 0sea>2ed estesa per moltiplicatività. In altre parole, (1) =1 ,(n) = (-1)k se n è libero da quadrati e prodotto di kprimi, e  (n) =0 se n non è libero da quadrati. Quindi vale 1?=?1=":(1.16) Dalla relazione precedente otteniamo che per f; g funzioni aritmetiche Ÿ7 vale che g=f?1 se e solo se f=g? ; questo risultato è noto come formula di inversione di Möbius. Proposizione 1.12 (Formula di Inversione di Möbius) .Siano f(n) eg(n) funzioni aritmetiche. Allora si ha g(n) =X djnf (d) per ognin>1se e solo se f(n) =X djn (d)g nd  sempre per ognin>1. Ad esempio, se '(n) è la funzione di Eulero (cioè '(n) := #fk6nj GCD(n; k) =1g), è un risultato noto che n=X djn' (d); quindi, posto Id(n) :=n per ogni n, in termini di prodotto di convoluzione vale che Id=1?' . Convolvendo ambo i membri di quest'espressione per 1- 1 = si ottiene?Id=', da cui '(n) =X djn (d)nd : Esempio 1.8 (Stringhe binarie primitive) .Vediamo un esempio di applicazione delle serie di Dirichlet. Consideriamo l'insieme delle stringhe binarie, cioè sequenze di 0e1. Deniamo primitiva una stringa che non è esprimibile come concatenazione di una stringa più piccola ripetuta più volte (e periodica una stringa non primitiva). Ad esempio, 10100 è primitiva, mentre 001001 no. La domanda è: quante stringhe binarie di lunghezza nsono primitive?Ÿ 7 Nonnecessariamente moltiplicative. 28 Capitolo 1. Funzioni generatriciIl numero totale di stringhe binarie di lunghezza n è naturalmente 2 n . Sia f (n) il numero di stringhe primitive. Ogni stringa di lunghezza n è esprimibile in modo unico come concatenazione di un certo numero n=d di stringhe primitive di lunghezza d (eventualmente d=n se la stringa è già primitiva), con d un divisore din. Quindi 2n =X djnf (d) = (1?f)(n): Dalla relazione (1.16) ricaviamo allora?(2n ) =f, cioè f(n) =X djn  nd  2d : Esempio 1.9 (Parole circolari) .In questo esempio parliamo ancora di stringhe, ma stavolta scegliamo un alfabeto con m simboli. Siamo interessati alle cosiddette parole circolari , cioè alle classi di equivalenza in cui consideriamo uguali due parole se si possono ottenere una dall'altra applicando uno shift delle lettere. La Figura1.6illustra il motivo per cui queste classi sono dette “circolari”.par o la Figura 1.6: Esempio di parola circolare: è la classe di equivalenza delle parole lineari “parola”, “arolap”, “rolapa”, “olapar ”, “laparo”, “aparol”. Ci chiediamo: quante parole circolari di lunghezza n ci sono? Innanzitutto osserviamo che nel caso di lettere ripetute è possibile che non ci siano esattamente n parole lineari in una parola circolare: ad esempio, la classe di equivalenza di “papa” contiene in più solamente “apap”. Diciamo che una parola circolare di lunghezza n ha periodo p 6n se si ripete uguale a sé stessa dopo pshift , cioè se la sua classe di equivalenza hapelementi. Notiamo chepjn. Detto M(p) il numero di parole circolari di lunghezza n e periodo p, si ha che ciascuna di esse dà origine a pstringhe ordinarie. Dato che a ogni stringa è associata almeno una parola circolare, dev'essere mn =X pjnpM (p): Analogamente a quanto fatto precedentemente, possiamo invertire la formula convolvendo con : detta m (k) :=mk si ha che nM (n) = (?m )(n) ; prendendo 1.5. Serie di Dirichlet 29 il p-esimo termine otteniamo M(p) =1p X djp  pd  md :Possiamo allora ricavare il numero totale di parole circolari di lunghezza n: basta sommare su tutti i possibili periodi. Tale numero è X pjnM (p) =1n X pjnnp ( ?m )(p) =1n ( Id??m )(n) =1n ( '?m )(n) =1n X djn' (d)mn=d : Esempio 1.10 (Polinomi ciclotomici) .Le serie di Dirichlet e le loro proprietà non sono utili solo per contare. Ad esempio, permettono di ricavare una formula più o meno esplicita per l'n-esimo polinomio ciclotomico. Ricordiamo che l' n-esimo polinomio ciclotomico  n( X) è il polinomio di grado '(n) le cui radici sono tutte e sole le radici primitive n-esime dell'unità. Ÿ8 La formula che ci interessa qui èY djn d( X) =Xn -1: In effetti, le radici di Xn -1 sono tutte le radici n-esime dell'unità e ciascuna di esse è una radice primitivad-esima per esattamente und6ntale chedjn. Passando ai logaritmi trasformiamo il prodotto in somma: X djnln ( d( X)) =ln(Xn -1) e la formula di inversione ci dà dunqueln( n( X)) =X djn  nd  ln(Xd -1) da cui, esponenziando,n( X) =Y djn( Xd -1) (n=d) :Ÿ 8 Cioè le radici di Xn -1 che non sono radici di Xm -1 se m < n ; sono della forma e2ir=n , per 06r6n-1con GCD(r; n) =1. 30 Capitolo 1. Funzioni generatrici 1.6 Carte, mani e mazzi (versione etichettata)Introduciamo in questa sezione alcuni strumenti che, usati in combinazione con le funzioni generatrici esponenziali, permettono di risolvere una grande quantità di problemi combinatori. Deniremo un modello che, nella più ampia generalità, ci permette di rispondere alla seguente domanda: abbiamo una struttura fatta con dei mattoncini semplici; quante sono le possibili strutture che è possibile assemblare, supponendo di saper contare quanti sono i mattoncini di ciascun tipo? Per essere più concreti, iniziamo con un esempio. Sappiamo che ogni grafo è unione di gra connessi; in questo caso la struttura è il grafo e i mattoncini sono i gra connessi. Di gra etichettati connessi ne esistono esattamente 1 con un vertice, 1 con due vertici e 4 con tre vertici. D'altra parte esistono 8 possibili gra etichettati con tre vertici (connessi e non). Come possiamo legare tra loro questi numeri? In partenza è dato un insieme astratto Pdi congurazioni (pictures ). Cosa siano effettivamente queste congurazioni, dipende dal problema specico: per una maggiore chiarezza, si rimanda agli esempi. Denizione 1.13. Una carta (card ) è una coppia C(S; p) , dove S€Nrf0g è un insieme nito di etichette (labels ) e p2P è una congurazione. Il peso di una carta è #( S) , e la carta è dettastandardseS=f1; : : : ; ng. Denizione 1.14. Una mano (hand ) è un insieme nito di carte in cui gli insiemi di etichette formano una partizione di f1; : : : ; ng per qualche n. Il peso di una mano è la somma dei pesi delle carte di cui è composta (cioèn). Denizione 1.15. Una rietichettatura (relabeling ) di una carta C(S; p) è una carta C(S0 ; p) con la stessa congurazione e #( S0 )=#( S) . Se S0 =f1; : : : ;#( S) g la rietichettatura è dettastandard. Denizione 1.16. Un mazzo (deck )D è un insieme nito di carte con lo stesso peso e congurazioni distinte. Il peso di un mazzo è il peso comune delle sue carte. Denizione 1.17. Una famiglia esponenziale F è una collezione (eventualmente innita) di mazziD 1; D 2; : : : tale che ogni mazzoD iha peso i. Denizione 1.18. Siano F=fD 1; D 2; : : : g una famiglia esponenziale e d n:= #( D n) . Deniamo contatore dei mazzi (deck enumerator ) la funzione generatrice esponenziale D(X)della successione(d n) n2Nrf0g, cioè D(X) :=1 X n=1d nX nn !: 1.6. Carte, mani e mazzi (versione etichettata) 31Vediamo subito un esempio. Consideriamo le permutazioni di f 1; : : : ; ng : come è noto esse si scrivono in modo unico come prodotto di cicli disgiunti. Proviamo allora a rappresentare le permutazioni in termini di carte e mani. L'insieme delle congurazioni è formato daicicli standard, cioè è P=[ n2Nrf0gf 2S nj è unn-ciclog: Una carta di peso n è un n-ciclo non necessariamente etichettato con i numeri 1; : : : ; n: ad esempio (2 5 3 17 9): Questo ciclo è rappresentato come una carta di peso 5che ha S=f2; 3; 5; 9; 17g e p= (1 3 2 5 4) . Osserviamo che la rietichettatura del ciclo standard per ottenere il ciclo particolarepreserva l'ordine delle etichette. A questo punto è facile vedere che una mano rappresenta una generica per- mutazione: si ha corrispondenza tra le carte nella mano e i cicli che compongono la permutazione. Un altro esempio è quello con cui abbiamo aperto questa sezione: i gra etichettati. Ricordiamo che il numero di gra etichettati connvertici è 2(n 2) perché assegnare un grafo equivale a dare una funzione denita sulle coppie (che sono n 2
) che dica se esiste un arco tra i due vertici oppure no. Ogni grafo si può ottenere come unione di sottogra connessi; l'idea allora è di rappresentare i gra connessi con le carte e quelli generici con le mani.f 2; 6; 14g123 2614 Figura 1.7: Esempio di carta per rappresentare un grafo etichettato connesso. A sinistra la carta, a destra l'oggetto che rappresenta. Denizione 1.19. Sia F una famiglia esponenziale. Indichiamo con h(n; k) il numero di mani di peso n formate da kcarte, tali che ciascuna carta sia una 32 Capitolo 1. Funzioni generatricirietichettatura di una qualche carta in un qualche mazzo di F. Sono ammesse ripetizioni, nel senso che possiamo prendere più copie della stessa carta, purché ciascuna copia sia rietichettata in modi diversi. L'obiettivo nale è determinare h (n; k) in funzione della successione (d n) . Per fare ciò, si usa una funzione generatrice in due variabili “mista”, in parte ordinaria e in parte esponenziale: H(X; Y) :=1 X n;k=0h (n; k)X nn !Y k : Chiamiamo questa funzione contatore delle mani (hand enumerator ). Denendo inoltre h(n) :=1 X k=0h (n; k) come il numero delle mani di peso n, indipendentemente dal numero di carte di cui sono formate, indicheremo con H(X) la funzione generatrice esponenziale per(h(n)), cioè H(X) :=H(X; 1) =1 X n=0h (n)X nn !: Il seguente teorema ci permette di collegare i due contatori D (X) eH(X; Y) . È un teorema di fondamentale importanza per raggiungere il nostro obiettivo. Teorema 1.20(Formula esponenziale).Vale che H(X; Y) =eY D(X) :(1.17) Corollario 1.21.Valutando(1.17)perY=1otteniamo H(X) =eD (X) Esempio 1.11 .Riprendiamo la rappresentazione delle permutazioni in cicli. Il numero di n-cicli in S n èdn:= ( n-1) !(ssato il primo elemento, ho n-1 scelte per il secondo,n-2per il terzo e così via). Quindi D(X) =1 X n=1X nn = - ln(1-X): Per il Teorema1.20dunqueH(X; Y) =e- Yln(1-X) =1( 1-X)Y: 1.6. Carte, mani e mazzi (versione etichettata) 33Esempio 1.12 .Contiamo ancora una volta il numero di partizioni di f 1; : : : ; ng . In questo caso possiamo prendere un insieme di congurazioni P=fg , perché tutta l'informazione è contenuta nelle etichette. Ora, d n= 1 per ogni n (l'unica carta di peso n è quella etichettata con f1; : : : ; ng) e una mano rappresenta una partizione. Quindi D(X) =1 X n=1X nn != eX -1 da cui ricaviamoH(X) =ee X -1 che è lo stesso risultato delle Sezioni1.1.2e1.4.1. Prima di procedere con la dimostrazione del Teorema1.20occorre enunciare ›11/03/2015 un lemma. Lemma 1.22 (Lemma fondamentale, versione etichettata) .Siano F0 ,F00 due famiglie esponenziali. Deniamo una nuova famiglia F :=F0 F00 ,fusione (merge ) di F0 e F00 , come unione disgiunta di F0 eF00 (cioè D n= D0 nt D00 n per ogni n: si può fare ridenendo eventualmente l'insieme delle congurazioni in modo che carte provenienti da famiglie diverse siano diverse fra loro; naturalmente dn= d0 n+ d00 n ). Detti H,H0 , H00 i contatori delle mani rispettivamente diF,F0 ,F00 , si ha H=H0 H00 : Dimostrazione. In una mano di F di peso ncon kcarte, alcune di esse provengono da F0 e altre da F00 . Le carte di F0 formano una “sottomano” di peso n0 con k0 carte (eventualmente rietichettate con un certo sottoinsieme S €f1; : : : ; ng ). Quindi una mano diFdi pesonconkcarte è univocamente determinata da: una mano diF0 di peson0 conk0 carte; una rietichettatura conS€f1; : : : ; ng;  la rimanente mano di F00 di peso n00 =n-n0 con k00 =k-k0 carte, rietichettata con f1; : : : ; ngrS. Quindih(n; k) =X n0 6nX k0 6k n n0 h0 (n0 ; k0 )h00 (n00 ; k00 ): Ma ora calcoliamo il prodotto H0 H00 = 1 X n0 ;k0 =0h 0 (n0 ; k0 )X n 0n 0 !Y k 0!
1 X n00 ;k00 =0h 00 (n00 ; k00 )X n 00n 00 !Y k 00! : 34 Capitolo 1. Funzioni generatrici Il coefciente di Xn Yk è X n0 +n00 =n k0 +k00 =k1n 0 !1n 00 !h 0 (n0 ; k0 )h00 (n00 ; k00 )e notiamo che 1n 0 !1n 00 != 1n ! n n0 . Questo termina la dimostrazione del lemma.Dimostrazione del Teorema1.20. Dividiamo la dimostrazione in tre casi. Caso 1. Consideriamo la famiglia F0 in cui tutti i mazzi sono vuoti, tranne l'r-esimo che consta di una sola carta. Cioè dn= 1sen=r 0sen6 =r;D (X) =X rr !: Quante mani è possibile creare con questa famiglia? Abbiamo a disposizione una sola carta, che eventualmente può essere ripetuta kvolte. In particolare le mani possono avere solamente peso kr , quindi h (n; k) =0 se n6 =kr . Se invece n=kr , il numero di mani coincide con il numero di partizioni di n elementi in ksottoinsiemi di cardinalità r: per la prima carta della mano abbiamo  n r scelte, per la seconda ne abbiamo  n-r r e così via no alla k-esima per la quale abbiamo  n- (k-1)r r = r r =1 scelta. Visto che l'ordine delle carte in una mano non conta, dobbiamo dividere il tutto perk!. In denitiva, sen=kr h(n; k) =1k ! n r
 n-r r


 n- (k-1)r r =n !k !(r!)k: Per vedere quest'ultima uguaglianza, notiamo che sviluppando i coefcienti binomiali si hanno cancellazioni: n!r !(n-r)!( n-r)!r !(n-2r)!( n-2r)!r !(n-3r)!


Ricapitolando H(X; Y) =1 X k=01k !(r!)kXkr Yk =1 X k=01k ! Xr Yr ! k =eX r Y=r! =eY D(X) : Caso 2. C'è sempre un solo mazzo non vuoto (supponiamo Dr ), ma con un numero di carte dr qualsiasi. La tesi discende abbastanza velocemente dal 1.6. Carte, mani e mazzi (versione etichettata) 35Lemma1.22: in questo caso F è la fusione di d r copie della famiglia F 0 introdotta nel Caso 1, quindi H(X; Y) = (H 0( X; Y))d r = eX r Y=r! dr =ed rXr Y=r! =eY D(X) : Caso 3. Una famiglia arbitraria F formata da mazzi con dr carte può essere sempre vista come fusione delle famiglie F 1; F 2; : : : tali che F r ha un solo mazzo non vuoto di peso rcon dr carte. Dal Lemma1.22e dal Caso 2 otteniamo dunque H(X; Y) =Y rH r( X; Y) =Y re Y D r( X) =eYP Dr( X) =eY D(X) : Esempio 1.13 (Esempio1.11, parte II) .Abbiamo visto che, costruendo le mani- permutazioni a partire dalle carte-cicli, si ottiene H(X; Y) = (1-X)- Y : Il coefciente h(n; k) rappresenta il numero di permutazioni su n che si scrivono con esattamente k cicli. Per trovare questo coefciente applichiamo l'usuale regola della potenza di binomio: (1-X)- Y =1 X n=0 -Y n (-1)n Xn =1 X n=0Y
(Y+1)


(Y+n-1)X nn !: Quindih(n; k)è il coefciente diYk nel polinomioY
(Y+1)


(Y+n-1). Verichiamo di aver fatto i conti giusti: il coefciente di Xn =n !in H(X; 1) dovrebbe essere il numero di permutazioni su n elementi che si scrivono come prodotto di cicli (e quindi dovrebbero esseren!, cioè tutte. . . ). In effetti H(X; 1) = (1-X)- 1 =1 X n=0X n =1 X n=0n !X nn !: 1.6.1 Sottoclassi di permutazioni Forti del risultato dell'esempio precedente, possiamo chiederci quante permuta- zioni abbiano delle determinate proprietà. Ad esempio: quante permutazioni si possono scrivere usando solamente cicli di lunghezza dispari? Possiamo risolvere questo problema cambiando di poco la famiglia esponen- ziale. Infatti le limitazioni del testo ci impongono di poter pescare una carta solo da un mazzoD ncon ndispari. In altre parole dn= (n-1)! senè dispari 0senè pari: 36 Capitolo 1. Funzioni generatrici In questo contesto D(X) =X ndispari( n-1)!n !X n =1 X k=0X 2k +12k +1: Questa è la parte dispari di-ln(1-X), dunque possiamo scrivere D(X) =- ln(1-X) - (-ln(1+X))2 = lnr1 +X1 -X da cui ricaviamoH(X; Y)senza problemi.Ci spingiamo ora un pochino oltre: vogliamo contare quante permutazioni hanno tutti cicli di lunghezza dispari e sono formate da un numero pari di cicli. Ÿ9 In questo caso stiamo limitando i possibili valori k, cioè il numero di carte presenti nella mano: possiamo prendere solokpari. Proposizione 1.23.SiaT„N. Deniamo expT( X) :=X k2TX kk !: Detto h n( T) il numero di mani di peso n che hanno un numero di carte k2T , allora la funzione generatrice esponenziale per la successione(h n( T))èexp T( D(X)). Dimostrazione. È un corollario del Teorema1.20. Infatti esplicitando l'Equazio- ne (1.17):1 X k=0D (X)kk !Y k =1 X n;k=0h (n; k)X nn !Y k e in particolareD(X)kk !=1 X n=0h (n; k)X nn ! quindi h(n; k) è il coefciente di Xn =n !in D(X)k =k !. Sommando solamente sui k2Tsi ha la tesi. Nel nostro caso T=fparig , ed exp T( X) è la parte pari di eX, che risulta essere exp T( X) =e X +e- X2 = cosh(X): Riutilizzando il risultato dell'esempio precedente si ha H(X) =12 r1 +X1 -X+r1 -X1 +X! =1p 1 -X2Ÿ 9 Osserviamo chendeve essere necessariamente pari. 1.6. Carte, mani e mazzi (versione etichettata) 37 che è un binomio; possiamo sviluppare ulteriormente il calcolo: (1-X2 )- 1=2 =1 X m=0 -1=2 m (-1)m Xm =1 X m=0 2m m (2m!)2 2mX 2m( 2m!): In altre parole, il numero di permutazioni sunelementi formate da un numero pari di cicli tutti di lunghezza dispari è0senè dispari e n n=2 n!2 nse n è pari. Visto che tutte le permutazioni sono n!, la probabilità di sceglierne una con queste caratteristiche è n n=2 12 n che è uguale alla probabilità di ottenere esattamente n=2 “testa” e n=2 “croce” lanciando una moneta non truccata nvolte. Un ultimo esempio sulle permutazioni: quante sono le involuzioni su n elementi, cioè permutazioni tali che 2 =Id ? Più in generale, ssato m, quante sono le permutazioni tali chem =Id? È un risultato noto che m =Id se e solo se tutte le lunghezze dei cicli di  sono divisori di m. In altre parole, possiamo pescare carte solo dai mazzi dei cicliD rtali che rjm. Il contatore dei mazzi per questa famiglia è D(X) =X rjmX rr : Come caso speciale,m=2dà D(X) =X+X 22 ; H(X) =eX +X2 =2 : 1.6.2 Esempi sui gra Studiamo alcuni esempi sui gra. Ricordiamo che in questo caso i gra si intendono con vertici etichettati e le carte sono i gra connessi. Quanti sono i gra 2-regolari, cioè i gra per cui da ogni vertice partono esattamente due archi? Per un grafo 2-regolare connesso non c'è molta scelta: è costretto ad essere un poligono, cioè un ciclo. Quindi ogni grafo 2-regolare è unione disgiunta di cicli.Ora,d n= 0pern=1; 2, mentre pern>3 dn=( n-1)!2 : 38 Capitolo 1. Funzioni generatriciLa differenza con i cicli delle permutazioni è la non-orientazione dei gra: un ciclo di grafo percorso in senso orario o antiorario è lo stesso. Questa è l'origine del 2a denominatore. A questo punto i conti sono facili: D(X) =1 X n=3( n-1)!2 X nn != 12 1 X n=3X nn = 12  -ln(1-X) -X-X 22  ; da cuiH(X) =1p 1 -Xe ( 1=2)(-X-X2 =2) : Analizziamo ora un caso a rovescio: abbiamo i numeri hn e vogliamo trovare id k. La domanda è: quanti gra connessiconnvertici ci sono? È facile contare la totalità dei gra: sono hn:= 2(n 2) da cuiH(X) =1 X n=02 (n 2)n !X n : Ora, la Formula (1.17) permette di ricavare i numeri hn in funzione dei d k o viceversa. Infatti vale il seguente lemma. Lemma 1.24. Per hn numero di mani di peso n ed k numero di carte nel mazzo Dk vale nhn=n X k=0 n k kdkh n-k: Dimostrazione. A partire da H(X) = eD(X) , si applicano ad ambo i membri in ordine gli operatori di logaritmo, derivata e moltiplicazione perX: si arriva a XH 0 (X)H (X)= XD0 (X): Per le varie proprietà delle funzioni generatrici esponenziali1 X n=0nh nX nn !1 X n=0h nX nn != 1 X n=0nd nX nn !: Moltiplicando per togliere il denominatore e ricordando la formula di prodotto di serie si ha la tesi. 1.6. Carte, mani e mazzi (versione etichettata) 39Applicando il lemma precedente al nostro caso otteniamo una formula ricorsiva per i d k: n2(n 2) =n X k=0 n k kdk2(n -k 2) : I primi valori did ksono 1; 1; 4; 38; 728 : : : Passiamo ad analizzare alcune strutture di grafo più particolari rispetto a ›16/03/2015 quelle viste nora. Ad esempio: quanti sono i gra (etichettati) bipartiti con n vertici? Un grafo bipartito è un grafo in cui l'insieme dei vertici V può essere partizio- nato come V=A[B in modo che gli archi connettano solamente vertici in A con quelli in B (cioè non ci sono archi che uniscano due vertici di A o due vertici diBtra loro).1 23 45 6 7 Figura 1.8: Esempio di grafo bipartito. Qui A=f1; 2; 4; 7geB=f3; 5; 6g. Un grafo bipartito è unione disgiunta di gra bipartiti connessi (in cui la partizione è data dall'unione delle partizioni). È naturale allora rappresentare i gra bipartiti come mani e quelli connessi come carte. Il problema è che in questo caso non c'è un modo ovvio per contare né le carte dei mazzi né le mani possibili. Una prima idea è: ssiamo una partizione V=A[B e per ogni (a; b)2AB possiamo scegliere se mettere un arco tra a eb, quindi il numero di gra bipartiti in totale sarebbe 2# ( AB) =2# ( A)
#( B) : In questo ragionamento c'è un intoppo: si conta più volte lo stesso oggetto. Si pensi anche solo al fatto che un grafo viene contato due volte scambiando tra loroAeB. In generale, un grafo bipartito con ccomponenti connesse viene contato 2c volte con questo metodo; questo perché per ogni componente connessa idel grafo possiamo scegliere quale dei due insiemi della partizione A i oBi mettere inAoppure inBnella partizione totale dei vertici (si veda anche la Figura1.9). 40 Capitolo 1. Funzioni generatrici Y 1Y 2Y 3Y 4Figura 1.9: Scegliendo A=Y 1[ Y 3 eB=Y 2[ Y 4 oppure A=Y 1[ Y 4 eB=Y 2[ Y 3 si conta più volte lo stesso grafo. Per rimediare a questo problema aggiungiamo informazioni che ci permettono di distinguere gra diversi e che poi trascureremo quando andremo a tirare le somme. Deniamo grafo bipartito 2-colorato un grafo bipartito con una 2- colorazione dei vertici (supponiamo in “rosso” e “verde”) tale che se esiste un arco tra i vertici vew, allora essi hanno colore diverso. Osserviamo che per ogni grafo bipartito connesso ne esistono due 2-colorati (prima assegno ad A un colore e a B l'altro, poi li scambio) e in generale per un grafo con ccomponenti connesse abbiamo2c gra2-colorati. Ora che i nostri gra sono colorati è facile contarli: infatti il numero di mani di peson(cioè il numero di gra bipartiti2-colorati) è n:=n X k=0 n k 2k (n-k) : Infatti per ogni ktra 0en scegliamo kvertici a cui assegnare il colore “rosso” (e di conseguenza gli n-k “verdi”) e solo a quel punto stabiliamo quali siano gli archi. A questo punto la Formula (1.17) ci permette di ricavare la funzione ge- neratrice esponenziale per i mazzi (cioè otteniamo i gra bipartiti 2-colorati connessi): D(X) =ln 1 X n=0 nX nn !! : Ma ora sappiamo che il numero dei gra bipartiti connessi non colorati è esat- tamente la metà di quelli colorati, quindi abbiamo la funzione generatrice esponenziale dei mazzi per il nostro problema originale: è esattamente D(X)2 = ln0 @v u u t1 X n=0 nX nn !1 A: Applicando ancora una volta la Formula (1.17) possiamo dunque trovare la funzione generatrice esponenziale delle mani, che ci dice quanti gra bipartiti 1.6. Carte, mani e mazzi (versione etichettata) 41 con nvertici ci sono: tale numero è il coefciente diXn =n! in v u u t1 X n=0 nX nn !:Ci dedicheremo ora agli alberi (etichettati), cioè a gra connessi etichettati senza cicli. Il risultato a cui vogliamo arrivare è: il numero di alberi etichettati con nvertici ènn -2 .Figura 1.10: Il grafo a sinistra nonè un albero, quello a destra sì. In realtà conteremo i cosiddetti alberi con radice , cioè alberi in cui è selezionato un vertice (la radice, appunto). Dato che la radice può essere uno qualsiasi degli nvertici, abbiamo che #falberi sunvertici con radiceg=n
#falberi sunverticig quindi ci basta dimostrare che il numero di alberi con radice ènn -1 .R Figura 1.11: Un albero con radice R. Ora, se le carte della nostra famiglia rappresentano gli alberi con radice, una mano corrisponde a