Non mi torna la dimostrazione che è sulle mie dispense, spero che qualcuno possa darmi una mano.
Su di un albero, sia v(i) la valenza del vertice i e consideriamo l'applicazione che associa a ciascun albero il monomio formale $ t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $. Consideriamo adesso la funzione generatrice $ A(t_1,t_2,...,t_n)=\sum t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $, dove la somma si intende estesa a tutti i possibili monomi ottenuti dall'applicazione suddetta. Allora $ A(t_1,t_2,...,t_n)=t_1t_2...t_n\sum t_{1}^{v(1)-1}t_{2}^{v(2)-1}... t_{n}^{v(n)-1} $, dove la somma è estesa a tutte le v(i) tali che $ \sum_{i=1}^{n}(v(i)-1)=n-2 $, $ v(i)-1 \ge 0 $ per la formula di Eulero. Fin qui ok. E' la conclusione che non capisco. Questa somma per il teorema multinomiale è $ (t_1+t_2+...t_n)^{n-2} $. Per applicare il teorema non dovrei conoscere prima i coefficienti dei monomi? Tra l'altro la dimostrazione si conclude dicendo: inoltre, sempre per lo stesso teorema, troviamo che il coefficiente del generico monomio è $ \binom{n-2}{v(1)-1,v(2)-1,...,v(n)-1} $. Non ci ho capito niente!
formula di Cayley per gli alberi
formula di Cayley per gli alberi
Ultima modifica di uchiak il 05 mag 2008, 17:09, modificato 1 volta in totale.
Modifico!-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Che dispense sono?
E' ragionevole che non ti torni, perché c'è un errore (o per lo meno una cosa detta malissimo): la sommatoria non è estesa a tutte le v la cui somma sia n-2 e basta, ma i monomi devono avere le molteplicità giuste, che sono appunto quelle che hai scritto alla fine.
Quando dici "formula di Eulero", senza di fatto citare alcuna formula di Eulero (
), mi fai venire in mente una cosa: prova a "sdoppiare" ogni arco dell'albero, e costruisci un circuito Euleriano su quella specie di grafo che viene fuori. Da lì, vedi se riesci a trovare la bigezione giusta tra alberi e monomi.
In qualsiasi altro modo veda quella dimostrazione, si morde inevitabilmente la coda. Anche nell'ipotesi di arrivare in fondo, però, l'uso delle funzioni generatrici è completamente inutile (se ho capito bene l'approccio).
E' ragionevole che non ti torni, perché c'è un errore (o per lo meno una cosa detta malissimo): la sommatoria non è estesa a tutte le v la cui somma sia n-2 e basta, ma i monomi devono avere le molteplicità giuste, che sono appunto quelle che hai scritto alla fine.
Quando dici "formula di Eulero", senza di fatto citare alcuna formula di Eulero (
), mi fai venire in mente una cosa: prova a "sdoppiare" ogni arco dell'albero, e costruisci un circuito Euleriano su quella specie di grafo che viene fuori. Da lì, vedi se riesci a trovare la bigezione giusta tra alberi e monomi.In qualsiasi altro modo veda quella dimostrazione, si morde inevitabilmente la coda. Anche nell'ipotesi di arrivare in fondo, però, l'uso delle funzioni generatrici è completamente inutile (se ho capito bene l'approccio).
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
D'accordo.
"Ricordiamo che un albero è un grafo connesso senza circuiti. Dimostreremo che $ T_n=n^{n-2} $, dove $ T_n $ è il numero di alberi su n vertici.
Sia I l'insieme dei vertici da cui si formano gli alberi e v(i) la valenza del vertice i. Consideriamo l'applicazione che associa a ciascun albero il monomio formale $ t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $, dove $ t_1,t_2,...,t_n $ sono indeterminate. Si noti che ad alberi distinti può associarsi lo stesso monomio. Consideriamo adesso la funzione generatrice in n variabili $ A(t_1,t_2,...,t_n)=\sum t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $, dove la somma si intende estesa a tutti i possibili monomi ottenuti dall'applicazione suddetta. Il coefficiente $ T(v(1),...,v(n)) $ del monomio $ t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $ nella funzione $ A(t_1,t_2,...,t_n) $ è il numero di alberi su n vertici con la condizione che il vertice i abbia valenza v(i), per ogni i appartenente ad I.
La formula di Eulero afferma che la somma delle valenze dei vertici di un grafo è uguale al doppio del numero dei lati. Dunque, per un albero i cui vertici hanno valenze v(1),...,v(n) possiamo scrivere la relazione v(1)+...+v(n) = 2(n-1)
in quanto si dimostra facilmente che un albero di n vertici ha n-1 lati.
Scriviamo la funzione generatrice nella forma $ A(t_1,t_2,...,t_n)=t_1t_2...t_n\sum t_{1}^{v(1)-1}t_{2}^{v(2)-1}... t_{n}^{v(n)-1} $, dove la somma è estesa a tutte le v(i) tali che $ \sum_{i=1}^{n}(v(i)-1)=n-2 $, $ v(i)-1 \ge 0 $.
Ma allora questa somma per il teorema multinomiale non è altro che $ (t_1+t_2+...t_n)^{n-2} $. Inoltre, sempre per lo stesso teorema, troviamo che $ T(v(1),...,v(n))=\binom{n-2}{v(1)-1,v(2)-1,...,v(n)-1} $.
La formula di Cayley segue ora facilmente ponendo nella funzione generatrice $ t_1=...=t_n=1 $."
Questo è quanto.
Domani comunque vado in biblioteca a consultare il libro A Course in Enumeration di Martin Aigner, speriamo che sia spiegata meglio. Da questo libro devo studiare il lemma di Gessel-Viennot e la teoria delle funzioni simmetriche... speriamo bene!
"Ricordiamo che un albero è un grafo connesso senza circuiti. Dimostreremo che $ T_n=n^{n-2} $, dove $ T_n $ è il numero di alberi su n vertici.
Sia I l'insieme dei vertici da cui si formano gli alberi e v(i) la valenza del vertice i. Consideriamo l'applicazione che associa a ciascun albero il monomio formale $ t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $, dove $ t_1,t_2,...,t_n $ sono indeterminate. Si noti che ad alberi distinti può associarsi lo stesso monomio. Consideriamo adesso la funzione generatrice in n variabili $ A(t_1,t_2,...,t_n)=\sum t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $, dove la somma si intende estesa a tutti i possibili monomi ottenuti dall'applicazione suddetta. Il coefficiente $ T(v(1),...,v(n)) $ del monomio $ t_{1}^{v(1)}t_{2}^{v(2)}... t_{n}^{v(n)} $ nella funzione $ A(t_1,t_2,...,t_n) $ è il numero di alberi su n vertici con la condizione che il vertice i abbia valenza v(i), per ogni i appartenente ad I.
La formula di Eulero afferma che la somma delle valenze dei vertici di un grafo è uguale al doppio del numero dei lati. Dunque, per un albero i cui vertici hanno valenze v(1),...,v(n) possiamo scrivere la relazione v(1)+...+v(n) = 2(n-1)
in quanto si dimostra facilmente che un albero di n vertici ha n-1 lati.
Scriviamo la funzione generatrice nella forma $ A(t_1,t_2,...,t_n)=t_1t_2...t_n\sum t_{1}^{v(1)-1}t_{2}^{v(2)-1}... t_{n}^{v(n)-1} $, dove la somma è estesa a tutte le v(i) tali che $ \sum_{i=1}^{n}(v(i)-1)=n-2 $, $ v(i)-1 \ge 0 $.
Ma allora questa somma per il teorema multinomiale non è altro che $ (t_1+t_2+...t_n)^{n-2} $. Inoltre, sempre per lo stesso teorema, troviamo che $ T(v(1),...,v(n))=\binom{n-2}{v(1)-1,v(2)-1,...,v(n)-1} $.
La formula di Cayley segue ora facilmente ponendo nella funzione generatrice $ t_1=...=t_n=1 $."
Questo è quanto.
Domani comunque vado in biblioteca a consultare il libro A Course in Enumeration di Martin Aigner, speriamo che sia spiegata meglio. Da questo libro devo studiare il lemma di Gessel-Viennot e la teoria delle funzioni simmetriche... speriamo bene!
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Penso che la dimostrazione sia fallata.
C'è un passaggio non esplicitato, che è quello dove ti sei bloccato tu. A giudicare dal dettaglio maniacale ed "esagerato" con cui giustifica tutti gli altri passaggi, mi sembra strano che proprio nel punto "cruciale" dia tutto per scontato e faccia un salto logico così grande.
Se il problema è solo capire perché gli alberi sono n^(n-2), usa un qualunque altro libro, preferibilmente non scritto in Italiano, e men che meno di autori Italiani... Le dimostrazioni di quel fatto sono varie, sia combinatorie "pure", che con le serie generatrici. Purtroppo quella che cerca di dimostrare Cerasoli non l'ho mai vista, e non saprei come aggiustarla senza stravolgerla.
C'è un passaggio non esplicitato, che è quello dove ti sei bloccato tu. A giudicare dal dettaglio maniacale ed "esagerato" con cui giustifica tutti gli altri passaggi, mi sembra strano che proprio nel punto "cruciale" dia tutto per scontato e faccia un salto logico così grande.
Se il problema è solo capire perché gli alberi sono n^(n-2), usa un qualunque altro libro, preferibilmente non scritto in Italiano, e men che meno di autori Italiani... Le dimostrazioni di quel fatto sono varie, sia combinatorie "pure", che con le serie generatrici. Purtroppo quella che cerca di dimostrare Cerasoli non l'ho mai vista, e non saprei come aggiustarla senza stravolgerla.
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
In genere adoro le dimostrazioni che usano le funzioni generatrici, ma per dimostrare la formula di Cayley raccomando questa dimostrazione che costruisce direttamente una biezione tra gli alberi con n vertici e le parole lunghe n-2 su un alfabeto di n simboli.
Wir müssen wissen. Wir werden wissen.
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Il Wilf (pag. 163) suggerisce un approccio simile a quello del Cerasoli, ma come passo preliminare chiede di dimostrare che gli alberi con le valenze fissate sono enumerati da quei coefficienti binomiali estesi (ovvero, ciò che il Cerasoli sembra dedurre alla fine, mordendosi la coda). Il suggerimento è di dimostrarlo per induzione sul numero di vertici, partendo dall'osservazione che almeno una delle valenze dev'essere 1.
Poi, se vi garba ho un'altra dimostrazione con le serie generatrici, del tutto diversa.
Detta $ T(x) $ la serie generatrice esponenziale che enumera rispetto al numero di nodi gli alberi radicati, vale l'equazione
$ \displaystyle T(x) = x e^{T(x)} $,
che si dimostra facilmente considerando che ogni albero radicato si decompone in una radice ed un insieme di alberi radicati.
Per il Teorema d'inversione di Lagrange,
$ \displaystyle [x^n] T(x) = \frac{1}{n} [x^{n-1}] e^{nx} = \frac{n^{n-1}}{n!} $,
da cui è immediato verificare che gli alberi radicati con $ n $ nodi sono $ n^{n-1} $, e quelli non radicati sono $ n^{n-2} $.
Poi, se vi garba ho un'altra dimostrazione con le serie generatrici, del tutto diversa.
Detta $ T(x) $ la serie generatrice esponenziale che enumera rispetto al numero di nodi gli alberi radicati, vale l'equazione
$ \displaystyle T(x) = x e^{T(x)} $,
che si dimostra facilmente considerando che ogni albero radicato si decompone in una radice ed un insieme di alberi radicati.
Per il Teorema d'inversione di Lagrange,
$ \displaystyle [x^n] T(x) = \frac{1}{n} [x^{n-1}] e^{nx} = \frac{n^{n-1}}{n!} $,
da cui è immediato verificare che gli alberi radicati con $ n $ nodi sono $ n^{n-1} $, e quelli non radicati sono $ n^{n-2} $.