Non ho parlato di disegnare, ho usato operazioni ben definite del lambda-calcolo. Quindi, oltre ad ever esplicitato la vostra funzione scrivendone la formula, vi ho dimostrato che è una funzione calcolabile.aursic ha scritto:Ho l'impressione che quello che Mind ci ha dato non è altro che l'algoritmo che una persona userebbe per cercare "a mano" il risultato:
si disegnano tutte le possibili strutture "sensate" e poi si cancellano i doppioni...
Isomeri degli alcani
-
MindFlyer
Polya
A prima vista, il problema proposto si risolve mediante la teoria ideata da Burnside-Polya.
ATTENZIONE: INIZIO DELLA PARTE TECNICA
Non ho intenzione di postare la risposta, poiche' si tratterebbe di trascivere parti di articoli di Polya e non ne ho tempo. Essenzialmente la dimostrazione si basa sull'azione di sottogruppi del gruppo simmetrico sull'insieme dei grafi non quozientato rispetto alla relazione di isomorfismo (ovvero i grafi vengono considerati differenti anche se tra essi esiste un isomorfismo completo). Dopoche' basta creare il cycle index sui generatori del gruppo ed ottenere il polinomio multivariabile nell'anello degli interi associato ed estrarre il coefficiente del monomio che ci interessa.
FINE DELLA PARTE TECNICA
Vedro' di semplificare il piu' possibile la dimostrazione, soprattutto evitando la teoria di Polya... ma non penso sia fattibile tanto facilmente (soprattuto dato che in questo periodo ho esami...).
Ciao!
-------------
Nessun uomo puo' sopravvivere in condizioni di pura realta'.
ATTENZIONE: INIZIO DELLA PARTE TECNICA
Non ho intenzione di postare la risposta, poiche' si tratterebbe di trascivere parti di articoli di Polya e non ne ho tempo. Essenzialmente la dimostrazione si basa sull'azione di sottogruppi del gruppo simmetrico sull'insieme dei grafi non quozientato rispetto alla relazione di isomorfismo (ovvero i grafi vengono considerati differenti anche se tra essi esiste un isomorfismo completo). Dopoche' basta creare il cycle index sui generatori del gruppo ed ottenere il polinomio multivariabile nell'anello degli interi associato ed estrarre il coefficiente del monomio che ci interessa.
FINE DELLA PARTE TECNICA
Vedro' di semplificare il piu' possibile la dimostrazione, soprattutto evitando la teoria di Polya... ma non penso sia fattibile tanto facilmente (soprattuto dato che in questo periodo ho esami...).
Ciao!
-------------
Nessun uomo puo' sopravvivere in condizioni di pura realta'.
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
AURSIC(100) = 5921072038125809849884993369103538010139
Sebbene non esista una formula chiusa per calcolare questa funzione, si può comunque dir molto sulla successione AURSIC(n).
Un po' di terminologia:
un grafo è un insieme di "vertici" e di "archi" che li uniscono; può essere utile rappresentare un grafo con un disegnino, ma un grafo è un oggetto astratto, i vertici non devono essere punti del piano e ogni arco non è altro che una coppia di vertici distinti.
Un grafo si dice connesso se è possibile raggiungere ogni vertice da ogni altro vertice muovendosi lungo gli archi.
Un albero è un grafo conneso che non contiene percorsi chiusi, in particolare dati due vertici distinti esiste uno ed un solo percorso che li congiunge.
Il diametro di un albero è la massima distanza possibile tra due coppie di vertici.
Un albero si dice tetravalente se da ogni vertice escono al più 4 archi.
Un albero si dice "piantato" se ha un vertice distinto la "radice", in questo caso chiamiano altezza di un vertice la sua distanza dalla radice.
Un albero piantato si dice ternario se da ogni vertice escono al più 3 rami, escluso quello che lo collega alla radice.
Ciò che cerchiamo di contare sono gli alberi tetravalenti con n vertici, dove intendiamo che due grafi sono uguali se esiste una corrispondenza tra i loro vertici che preserva gli archi (cioè, se due vertici sono uniti da un arco, anche i vertici corrispondenti devono esserlo, e viceversa).
Il mio chimico di fiducia mi ha informato che questo enumera gli alcani a meno di stereoisomeri, ma non saprei come formulare il problema altrimenti.
Come affermato da Catraga, si devono usare alcuni risultati di Polya, in particolare:
Se $ f(x)=\sum_{n\geq 0}a_n x^n $ è il polinomio enumeratore di certi oggetti "pesati", allora $ Z_k(f(x),f(x^2),\cdots,f(x^k)) $ è il polinomio enumeratore delle k-uple non ordinate di oggetti, pesate con la somma dei pesi delle componenti, dove $ Z_k(x_1,\cdots,x_k) $ è un certo polinomio (il cycle index di $ S_k $) fissato.
Facciamo un esempio per capirci.
Consideriamo l'insieme degli alberi piantati ternari con altezza al più $ h $, e diciamo che il peso di un tale albero è il numero dei suoi vertici. Allora se chiamiamo $ t_{h,n} $ il numero di alberi piantati ternari di altezza al più $ h $ e con $ n $ vertici, possiamo definire $ T_h(x)=\sum_{n\geq 0}t_{h,n}x^n $ il polinomio enumeratore degli alberi piantati ternari con altezza al più $ h $.
Il teorema allora ci dice che esiste un certo polinomio in tre variabili $ Z_3(x_1,x_2,x_3) $ tale che $ Z_3(T_h(x),T_h(x^2),T_h(x^3)) $ enumera le terne non ordinate di alberi piantati ternari con altezza al più $ h $, nel senso che il coefficiente di $ x^l $ in quel polinomio è proprio il numero di terne tali che la somma del numero di vertici dei tre alberi che le compongono sia $ l $.
Come nota di cronaca, riporto i tre polinomi che userò:
$ Z_2(x_1,x_2)=\frac{1}{2}(x_1^2+x_2) $
$ Z_3(x_1,x_2,x_3)=\frac{1}{6}(x_1^3+3x_1x_2+2x_3) $
$ Z_4(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4+6x_1^2x_2+3x_2^2+8x_1x_3+6x_4) $
[per comodità di lettura e di digitazione, scriverò $ Z_k(f(x)) $ invece che $ Z_k(f(x),f(x^2),\cdots,f(x^k)) $]
Proviamo ad usare questo teorema per ricavare qualche informazione sui $ T_h(x) $.
Se da un albero piantato ternario con altezza al più $ h+1 $ cancelliamo la radice e tutti gli archi che escono da essa, rimaniamo con una terna non ordinata di alberi piantati ternari con altezza al più $ h $, pertanto possiamo scrivere la relazione di ricorrenza
$ T_{h+1}(x)=1+xZ_3(T_h(x)) $, dove il termine +1 è dovuto all'albero vuoto (privo di vertici), non ottenibile da una terna di alberi aggiungendo la radice.
Tornando agli alcani, dividiamoli in "centrati" e "bicentrati" in base al loro diametro: gli alcani con diametro pari, che possiedono un elemento (il "centro") che si trova a metà di un percorso di lunghezza massima, mentre quelli di diametro dispari possiedono due elementi a metà di un percorso di lunghezza massima.
Consideriamo un alcano bicentrato di diametro $ 2h+1 $ e cancelliamo l'arco che congiunge i due centri, quello che ci rimane è una coppia non ordinata di alberi piantati ternari di altezza esattamente $ h $, i quali sono enumerati da $ T_h(x)-T_{h-1}(x) $, quindi gli alcani bicentrati di diametro $ h $ sono enumerati da $ B_{2h+1}(x)=Z_2(T_h(x)-T_{h-1}(x)) $.
Sommando sui diametri troviamo la serie generatrice degli alcani bicentrati $ B(x)=\sum_{h\geq 0}B_{2h+1}(x) $.
Gli alcani centrati sono più faticosi da contare, infatti se ne prendiamo uno di diametro $ 2h $e cancelliamo il centro, otteniamo una quaterna non ordinata di alberi piantati ternari di altezza al più $ h-1 $, tali che almeno due di essi hanno altezza esattamente $ h-1 $.
Questi alcani sono quindi enumerati da
$ C_{2h}(x) = (1+xZ_4(T_{h-1}(x))) -(1+xZ_4(T_{h-2}(x))) $$ -(T_{h-1}(x)-T_{h-2}(x)) (T_{h-1}(x)-1) $
I primi due termini considerano le quaterne costituite da alberi di altezza al più $ h-1 $ e alberi di altezza al più $ h-2 $, dalla loro differenza (che enumera le quaterne di alberi di altezza al più $ h-1 $ tali che almeno uno di essi ha esattamente quell'altezza) dobbiamo ancora togliere gli alberi piantati con esattamente un sottoalbero con altezza $ h-1 $.
Come prima, sommando sui diametri ci dà la serie che enumera gli alcani centrati $ C(x)=\sum_{h\geq 0}C_{2h}(x) $
La somma delle due serie ottenute fino ad ora è la serie che enumera gli alcani, e il coefficiente del suo termine in $ x^l $ è proprio AURSIC(l).
A questo punto probabilmente vi sembra di aver fatto una grande fatica per saperne tanto quanto prima, ma in realtà i polinomi e le serie che abbiamo definito sono oggetti molto maneggevoli e per calcolare AURSIC(100) il programmino che ho scritto ha impiegato appena 1.7 secondi, mentre un programma che opera come la funzione di MindFlyer, e quindi costruendo ogni alcano e confrontandoli tra loro per vedere se sono isomorfi, dovrebbe eseguire un numero troppo grande di operazioni per essere utile a qualcosa di diverso dal dimostrare che AURSIC(n) è calcolabile.
Spero di non essere stato troppo criptico.
CaO
Francesco
Sebbene non esista una formula chiusa per calcolare questa funzione, si può comunque dir molto sulla successione AURSIC(n).
Un po' di terminologia:
un grafo è un insieme di "vertici" e di "archi" che li uniscono; può essere utile rappresentare un grafo con un disegnino, ma un grafo è un oggetto astratto, i vertici non devono essere punti del piano e ogni arco non è altro che una coppia di vertici distinti.
Un grafo si dice connesso se è possibile raggiungere ogni vertice da ogni altro vertice muovendosi lungo gli archi.
Un albero è un grafo conneso che non contiene percorsi chiusi, in particolare dati due vertici distinti esiste uno ed un solo percorso che li congiunge.
Il diametro di un albero è la massima distanza possibile tra due coppie di vertici.
Un albero si dice tetravalente se da ogni vertice escono al più 4 archi.
Un albero si dice "piantato" se ha un vertice distinto la "radice", in questo caso chiamiano altezza di un vertice la sua distanza dalla radice.
Un albero piantato si dice ternario se da ogni vertice escono al più 3 rami, escluso quello che lo collega alla radice.
Ciò che cerchiamo di contare sono gli alberi tetravalenti con n vertici, dove intendiamo che due grafi sono uguali se esiste una corrispondenza tra i loro vertici che preserva gli archi (cioè, se due vertici sono uniti da un arco, anche i vertici corrispondenti devono esserlo, e viceversa).
Il mio chimico di fiducia mi ha informato che questo enumera gli alcani a meno di stereoisomeri, ma non saprei come formulare il problema altrimenti.
Come affermato da Catraga, si devono usare alcuni risultati di Polya, in particolare:
Se $ f(x)=\sum_{n\geq 0}a_n x^n $ è il polinomio enumeratore di certi oggetti "pesati", allora $ Z_k(f(x),f(x^2),\cdots,f(x^k)) $ è il polinomio enumeratore delle k-uple non ordinate di oggetti, pesate con la somma dei pesi delle componenti, dove $ Z_k(x_1,\cdots,x_k) $ è un certo polinomio (il cycle index di $ S_k $) fissato.
Facciamo un esempio per capirci.
Consideriamo l'insieme degli alberi piantati ternari con altezza al più $ h $, e diciamo che il peso di un tale albero è il numero dei suoi vertici. Allora se chiamiamo $ t_{h,n} $ il numero di alberi piantati ternari di altezza al più $ h $ e con $ n $ vertici, possiamo definire $ T_h(x)=\sum_{n\geq 0}t_{h,n}x^n $ il polinomio enumeratore degli alberi piantati ternari con altezza al più $ h $.
Il teorema allora ci dice che esiste un certo polinomio in tre variabili $ Z_3(x_1,x_2,x_3) $ tale che $ Z_3(T_h(x),T_h(x^2),T_h(x^3)) $ enumera le terne non ordinate di alberi piantati ternari con altezza al più $ h $, nel senso che il coefficiente di $ x^l $ in quel polinomio è proprio il numero di terne tali che la somma del numero di vertici dei tre alberi che le compongono sia $ l $.
Come nota di cronaca, riporto i tre polinomi che userò:
$ Z_2(x_1,x_2)=\frac{1}{2}(x_1^2+x_2) $
$ Z_3(x_1,x_2,x_3)=\frac{1}{6}(x_1^3+3x_1x_2+2x_3) $
$ Z_4(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4+6x_1^2x_2+3x_2^2+8x_1x_3+6x_4) $
[per comodità di lettura e di digitazione, scriverò $ Z_k(f(x)) $ invece che $ Z_k(f(x),f(x^2),\cdots,f(x^k)) $]
Proviamo ad usare questo teorema per ricavare qualche informazione sui $ T_h(x) $.
Se da un albero piantato ternario con altezza al più $ h+1 $ cancelliamo la radice e tutti gli archi che escono da essa, rimaniamo con una terna non ordinata di alberi piantati ternari con altezza al più $ h $, pertanto possiamo scrivere la relazione di ricorrenza
$ T_{h+1}(x)=1+xZ_3(T_h(x)) $, dove il termine +1 è dovuto all'albero vuoto (privo di vertici), non ottenibile da una terna di alberi aggiungendo la radice.
Tornando agli alcani, dividiamoli in "centrati" e "bicentrati" in base al loro diametro: gli alcani con diametro pari, che possiedono un elemento (il "centro") che si trova a metà di un percorso di lunghezza massima, mentre quelli di diametro dispari possiedono due elementi a metà di un percorso di lunghezza massima.
Consideriamo un alcano bicentrato di diametro $ 2h+1 $ e cancelliamo l'arco che congiunge i due centri, quello che ci rimane è una coppia non ordinata di alberi piantati ternari di altezza esattamente $ h $, i quali sono enumerati da $ T_h(x)-T_{h-1}(x) $, quindi gli alcani bicentrati di diametro $ h $ sono enumerati da $ B_{2h+1}(x)=Z_2(T_h(x)-T_{h-1}(x)) $.
Sommando sui diametri troviamo la serie generatrice degli alcani bicentrati $ B(x)=\sum_{h\geq 0}B_{2h+1}(x) $.
Gli alcani centrati sono più faticosi da contare, infatti se ne prendiamo uno di diametro $ 2h $e cancelliamo il centro, otteniamo una quaterna non ordinata di alberi piantati ternari di altezza al più $ h-1 $, tali che almeno due di essi hanno altezza esattamente $ h-1 $.
Questi alcani sono quindi enumerati da
$ C_{2h}(x) = (1+xZ_4(T_{h-1}(x))) -(1+xZ_4(T_{h-2}(x))) $$ -(T_{h-1}(x)-T_{h-2}(x)) (T_{h-1}(x)-1) $
I primi due termini considerano le quaterne costituite da alberi di altezza al più $ h-1 $ e alberi di altezza al più $ h-2 $, dalla loro differenza (che enumera le quaterne di alberi di altezza al più $ h-1 $ tali che almeno uno di essi ha esattamente quell'altezza) dobbiamo ancora togliere gli alberi piantati con esattamente un sottoalbero con altezza $ h-1 $.
Come prima, sommando sui diametri ci dà la serie che enumera gli alcani centrati $ C(x)=\sum_{h\geq 0}C_{2h}(x) $
La somma delle due serie ottenute fino ad ora è la serie che enumera gli alcani, e il coefficiente del suo termine in $ x^l $ è proprio AURSIC(l).
A questo punto probabilmente vi sembra di aver fatto una grande fatica per saperne tanto quanto prima, ma in realtà i polinomi e le serie che abbiamo definito sono oggetti molto maneggevoli e per calcolare AURSIC(100) il programmino che ho scritto ha impiegato appena 1.7 secondi, mentre un programma che opera come la funzione di MindFlyer, e quindi costruendo ogni alcano e confrontandoli tra loro per vedere se sono isomorfi, dovrebbe eseguire un numero troppo grande di operazioni per essere utile a qualcosa di diverso dal dimostrare che AURSIC(n) è calcolabile.
Spero di non essere stato troppo criptico.
CaO
Francesco
Ultima modifica di FrancescoVeneziano il 06 mar 2005, 15:05, modificato 1 volta in totale.
Wir müssen wissen. Wir werden wissen.
-
MindFlyer
-
Franchifis
- Messaggi: 149
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa
Non so se vi possa essere d'aiuto, la discussione supera di gran lunga le mie capacita' matematiche (lambda calcolo??? 
), ma vi riporto quello che dice il mio libro di chimica organica sull'argomento: "Ci sono formule matematiche, abbastanza complesse, che danno il numero di isomeri di struttura possibili di un alcano". Quindi il problema non e' aperto, giusto?
Il libro poi aggiunge che C10H22 ha 75 isomeri di struttura, C20H42 ne ha 366319 e infine C40H82 ne ha addirittura 62 481 801 147 341. Potreste usare questi numeri per controllare le vostre formule.
Comunque il problema e' di pura matematica e non di chimica perche' in ogni caso la maggior parte di quegli isomeri non possono esistere a causa dell'ingombro sterico degli atomi (il tetra-terz-butilmetano, per esempio, non e' mai stato sintetizzato).
Sarebbe interessante pero' estendere il problema a qualunque idrocarburo "teorico" formato da soli atomi di carbonio e idrogeno: quanti sono i grafi connessi tetravalenti di n vertici possibili?
), ma vi riporto quello che dice il mio libro di chimica organica sull'argomento: "Ci sono formule matematiche, abbastanza complesse, che danno il numero di isomeri di struttura possibili di un alcano". Quindi il problema non e' aperto, giusto?Il libro poi aggiunge che C10H22 ha 75 isomeri di struttura, C20H42 ne ha 366319 e infine C40H82 ne ha addirittura 62 481 801 147 341. Potreste usare questi numeri per controllare le vostre formule.
Comunque il problema e' di pura matematica e non di chimica perche' in ogni caso la maggior parte di quegli isomeri non possono esistere a causa dell'ingombro sterico degli atomi (il tetra-terz-butilmetano, per esempio, non e' mai stato sintetizzato).
Sarebbe interessante pero' estendere il problema a qualunque idrocarburo "teorico" formato da soli atomi di carbonio e idrogeno: quanti sono i grafi connessi tetravalenti di n vertici possibili?